Index-based graph querying and matching in large graphs
Jiong Yang, Shijie Zhang · 2010
Currently, a huge amount data can be naturally represented by graphs, e.g., protein interaction networks, gene regulatory networks, etc. The size of an application graph may vary from tens of vertices to millions of vertices. Rich information may be retrieved if proper tools are provided. We are interested in applying index-based graph querying and matching techniques to both large and massive graphs. We use frequent subtrees for graph querying problem in a database composed of multiple small graphs. Subtree based indexing algorithms are efficient and effective in finding the supergraphs of any given query graph. For graph matching problem in a relatively large database graph, we proposed to use a distance based index structure. Optimized by a dynamic matching scheme, the algorithm can quickly find all the matches of any given query graph in the database graph. For graph matching in a massive database graph, we use a twofold index based on label combinations and shortest path trees. Last but not least, we discuss the future work of index-based graph querying and matching algorithms.