Database Seminar: Nan Tang
Graph Pattern Matching: From Intractable to Polynomial Time
What 


When 
Nov 17, 2010 from 05:00 PM to 06:00 PM 
Where  4.31/4.33 
Add event to calendar 
vCal iCal 
Graph pattern matching is typically defined in terms of subgraph isomorphism, which makes it an npcomplete problem. Moreover, it requires bijective functions, which are often too restrictive to characterize patterns in emerging applications.We propose a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, we define matching based on a notion of bounded simulation, an extension of graph simulation. We show that with this revision, graph pattern matching can be performed in cubictime, by providing such an algorithm. We also develop algorithms for incrementally finding matches when data graphs are updated, with performance guarantees for dag patterns. We also introduce the latest results for incremental graph simulation problem. We experimentally verify that these algorithms scale well, and that the revised notion of graph pattern matching allows us to identify communities commonly found in realworld networks.