In-Memory Subgraph Matching: An In-depth Study
Authors:
Open Access
- 31 May 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1083-1098
Abstract
We study the performance of eight representative in-memory subgraph matching algorithms. Specifically, we put QuickSI, GraphQL, CFL, CECI, DP-iso, RI and VF2++ in a common framework to compare them on the following four aspects: (1) method of filtering candidate vertices in the data graph; (2) method of ordering query vertices; (3) method of enumerating partial results; and (4) other optimization techniques. Then, we compare the overall performance of these algorithms with Glasgow, an algorithm based on the constraint programming. Through experiments, we find that (1) the filtering method of GraphQL is competitive to that of the latest algorithms CFL, CECI and DP-iso in terms of pruning power; (2) the ordering methods in GraphQL and RI are usually the most effective; (3) the set intersection based local candidate computation in CECI and DP-iso performs the best in the enumeration; and (4) the failing sets pruning in DP-iso can significantly improve the performance when queries become large. Our source code is publicly available at https://github.com/RapidsAtHKUST/SubgraphMatching.Keywords
This publication has 33 references indexed in Scilit:
- Join Processing for Graph Patterns2015
- Design and Implementation of the LogicBlox System2015
- VF2 Plus: An Improved version of VF2 for Biological Graphs2015
- A subgraph isomorphism algorithm and its application to biochemical dataBMC Bioinformatics, 2013
- Efficient subgraph matching on billion node graphsProceedings of the VLDB Endowment, 2012
- AllDifferent-based filtering for subgraph isomorphismArtificial Intelligence, 2010
- Taming verification hardnessProceedings of the VLDB Endowment, 2008
- Hypertree Decompositions: Structure, Algorithms, and Applications2005
- R-MAT: A Recursive Model for Graph Mining2004
- An Algorithm for Subgraph IsomorphismJournal of the ACM, 1976