SASUM: A Sharing-Based Approach to Fast Approximate Subgraph Matching for Large Graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 412
  • Download : 16
Subgraph matching is a fundamental operation for querying graph-structured data. Due to potential errors and noises in real-world graph data, exact subgraph matching is sometimes inappropriate in practice. In this paper we consider an approximate subgraph matching model that allows missing edges. Based on this model, approximate subgraph matching finds all occurrences of a given query graph in a database graph, allowing missing edges. A straightforward approach is to first generate query subgraphs of a given query graph by deleting edges and then perform exact subgraph matching for each query subgraph. In this paper we propose a sharing-based approach to approximate subgraph matching, called SASUM. Our method is based on the fact that query subgraphs are highly overlapped. Due to this overlapping nature of query subgraphs, the matches of a query subgraph can be computed from the matches of a smaller query subgraph, which results in reducing the number of query subgraphs that require expensive exact subgraph matching. Our method uses a lattice framework to identify sharing opportunities between query subgraphs. To further reduce the number of graphs that need exact subgraph matching, SASUM generates small base graphs that are shared by query subgraphs and chooses the minimum number of base graphs whose matches are used to derive the matching results of all query subgraphs. A comprehensive set of experiments shows that our approach outperforms the state-of-the-art approach by orders of magnitude in terms of query execution time.
Publisher
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
Issue Date
2013-03
Language
English
Article Type
Article
Keywords

ISOMORPHISM; FRAMEWORK; EFFICIENT; ALGORITHM

Citation

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, v.E96D, no.3, pp.624 - 633

ISSN
0916-8532
DOI
10.1587/transinf.E96.D.624
URI
http://hdl.handle.net/10203/174317
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
000320214300029.pdf(1.2 MB)Download

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0