Feature-based similarity search in graph structures

Xifeng Yan, Feida Zhu, Gabrielle Dawn Allen, Jiawei Han

Research output: Contribution to journalArticlepeer-review


Similarity search of complex structures is an important operation in graph-related applications since exact matching is often too restrictive. In this article, we investigate the issues of substructure similarity search using indexed features in graph databases. By transforming the edge relaxation ratio of a query graph into the maximum allowed feature misses, our structural filtering algorithm can filter graphs without performing pairwise similarity computation. It is further shown that using either too few or too many features can result in poor filtering performance. Thus the challenge is to design an effective feature set selection strategy that could maximize the filtering capability. We prove that the complexity of optimal feature set selection is (2m) in the worst case, where m is the number of features for selection. In practice, we identify several criteria to build effective feature sets for filtering, and demonstrate that combining features with similar size and selectivity can improve the filtering and search performance significantly within a multifilter composition framework. The proposed feature-based filtering concept can be generalized and applied to searching approximate nonconsecutive sequences, trees, and other structured data as well.

Original languageEnglish (US)
Pages (from-to)1418-1453
Number of pages36
JournalACM Transactions on Database Systems
Issue number4
StatePublished - Dec 1 2006


  • Complexity
  • Graph database
  • Index
  • Similarity search

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Feature-based similarity search in graph structures'. Together they form a unique fingerprint.

Cite this