Database Seminar: Yinghui Wu
Simulation revised for graph pattern matching
What 


When 
Nov 10, 2010 from 05:00 PM to 06:00 PM 
Where  4.31/4.33 
Add event to calendar 
vCal iCal 
Traditional graph matching based on subgraph isomorphism and simulation may not capture the complex semantics in the queries in emerging applications, e.g., social networks.
(1) We propose bounded simulation, a revision for graph simulation, for graph pattern matching problem;
(2) We show how the bounded simulation can be used for computing the matches for a pattern in cubic time;
(3) We briefly introduce two extensions of the work above, namely, a generalization of the bounded simulation which considers edge types and regular expressions, as well as the incremental computation of the bounded simulation.