Free tree-featured graph indexing and query processing
Jeffrey Xu Yu, Peixiang Zhao · 2007
Scalable structural pattern mining and graph database management tools become increasingly crucial to applications with complex data in domains ranging from software engineering to computational biology. Due to their high complexity, it is often difficult, if not impossible, for human beings to manually analyze any reasonably large collection of graphs. In this dissertation, we investigate two fundamental problems in large scale graph databases: Given a graph database what are the hidden free tree patterns and how can we find them? And how can we index graphs based on free tree patterns and perform similarity search in large graph databases? In this dissertation, we develop frequent free tree mining systems, F3TM and CFFTree, to systematically discover the complete set of (closed) frequent free trees from a graph database. Graph indexing, another problem addressed in this dissertation, is of special interest both in academia and in industrial applications. The solutions, (Tree+Δ ) and SimTree, propose a free tree featured index, which is built on frequent free tree patterns discovered through a structural mining process. This mining-based indexing methodology leads to the development of a compact but effective graph index structure that is orders of magnitude smaller in size but an order of magnitude faster in performance than traditional approaches. The developed concepts, theories, and systems hence increase our understanding of data mining principles in structural pattern discovery, interpretation and search. The formulation of a general free tree featured graph information system through this study could provide fundamental supports to graph-intensive applications.