Efficient Subgraph Search with Presorting and Indexing on Label Frequency
Haichuan Shang, Masaru Kitsuregawa · 2012
Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop ecient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of ltering-and-verication to reduce the precise computation costs; consequently various novel featurebased indexes have been developed. While the existing techniques work well for small query graphs, the verication phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we rstly propose a novel and ecient algorithm for testing subgraph isomorphism. Secondly, we develop a new feature-based index technique to accommodate the proposed algorithm in the ltering phase. Our extensive experiments on real and synthetic data demonstrate the eciency and scalability of the proposed techniques, which signicantly improve the existing techniques.