Personal tools
You are here: Home Events Database Seminars Database Seminar: Nan Tang

Database Seminar: Nan Tang

— filed under:

Graph Pattern Matching: From Intractable to Polynomial Time

What
  • Database Seminar
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 np-complete 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 cubic-time, 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  real-world networks.

Document Actions