Journal of Northeastern University:Natural Science ›› 2017, Vol. 38 ›› Issue (5): 625-629.DOI: 10.12068/j.issn.1005-3026.2017.05.004

• Information & Control • Previous Articles     Next Articles

A Similarity Search Technique for Graph Set

PANG Jun, GU Yu, YU Ge   

  1. School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China.
  • Received:2015-12-10 Revised:2015-12-10 Online:2017-05-15 Published:2017-05-11
  • Contact: YU Ge
  • About author:-
  • Supported by:

    -

Abstract:

Existing studies of graph similarity search mainly focus on the subgraph matching instead of the graph set matching. To tackle this issue, GSSS algorithm was proposed based on filtering-and-verify framework. A graph set distance was defined. In order to reduce the search space, Number filter, Size filter, Complete edge filter and Lower bound filter were proposed. Then, the computation of the graph set distance was optimized. An incremental multi-layer inverted index was designed to further improve the query efficiency. Extensive experiments on a real-world dataset show that GSSS algorithm is effective and efficient.

Key words: graph set, similarity, search, index, filter

CLC Number: