場所：筑波大学 計算科学研究センター 会議室A
Subgraph Isomorphism Search: Overview and State-of-the-Art Approaches
Given data graph G and query graph P, subgraph isomorphism search is to find subgraphs of G that are isomorphic (i.e., structurally identical) to P. The problem finds numerous applications, but is computationally intractable. Over the years the problem has attracted researchers from different fields, and many algorithms have been proposed. Roughly, these algorithms can be grouped into three types: those based on Constraint Solving; those based on Depth-First Search and Backtracking; and those based on Relational Join. In this talk, I will first give a brief overview of each of these types of algorithms, and then provide the main ideas on the most recent Backtracking algorithms proposed by Database researchers (including our own work). I will also discuss some variations of problem.
John (Junhu) Wang received his PhD in Computer Science in 2003 from Griffith University, Australia. He is currently an associate professor at the same university. Before joining Griffith University as an academic staff, he worked as a lecturer at Monash University, Australia from September 2001 to February 2003. His current research interest is in Graph Query Processing, Knowledge Representation, Social Network Analysis, and Text Data Analysis. Previously, he worked on Constraint Reasoning, XML and Tree Pattern Query Processing. More details about Dr Wang can be found at http://www.ict.griffith.edu.au/~jw/.