Feature-Based Similarity Search in Graph Structures

Publication Type

Journal Article

Publication Date

12-2006

Abstract

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

ACM Transactions on Database Systems

Volume

31

Issue

4

First Page

1418

Last Page

1453

ISSN

0362-5915

Identifier

10.1145/1189769.1189777

Publisher

ACM

Additional URL

http://dx.doi.org/10.1145/1189769.1189777

Link to Full Text

Share

COinS