Publications
Detailed Information
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching
Cited 17 time in
Web of Science
Cited 21 time in Scopus
- Authors
- Issue Date
- 2021-01
- Publisher
- IEEE
- Citation
- Proceedings of the ACM SIGMOD International Conference on Management of Data, pp.925-937
- Abstract
- © 2021 ACM.Subgraph query processing (also known as subgraph search) and subgraph matching are fundamental graph problems in many application domains. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we propose a new subgraph search algorithm using equivalences of vertices in order to reduce search space: (1) static equivalence of vertices in a query graph that leads to an efficient matching order of the vertices, and (2) dynamic equivalence of candidate vertices in a data graph, which enables us to capture and remove redundancies in search space. These techniques for subgraph search also lead to an improved algorithm for subgraph matching. Experiments show that our approach outperforms state-of-the-art subgraph search and subgraph matching algorithms by up to several orders of magnitude with respect to query processing time.
- ISSN
- 0730-8078
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.