Graph indexing based on discriminative frequent structure analysis

Research output: Contribution to journalArticlepeer-review


Graphs have become increasingly important in modelling complicated structures and schemaless data such as chemical compounds, proteins, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via indices. In this article, we investigate the issues of indexing graphs and propose a novel indexing model based on discriminative frequent structures that are identified through a graph mining process. We show that the compact index built under this model can achieve better performance in processing graph queries. Since discriminative frequent structures capture the intrinsic characteristics of the data, they are relatively stable to database updates, thus facilitating sampling-based feature extraction and incremental index maintenance. Our approach not only provides an elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit from data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be generalized and applied to indexing sequences, trees, and other complicated structures as well.

Original languageEnglish (US)
Pages (from-to)960-993
Number of pages34
JournalACM Transactions on Database Systems
Issue number4
StatePublished - 2005


  • Frequent pattern
  • Graph database
  • Index

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Graph indexing based on discriminative frequent structure analysis'. Together they form a unique fingerprint.

Cite this