Proceedings of the ACM on Management of Data · 2023 · 28 citations · 35 references
ComputingComputer ScienceAlgorithmsData StructuresParallel AlgorithmsGraph AlgorithmsGraph AnalyticsGraph MiningGraph MatchingMatching AlgorithmsSubgraph ExtractionSubgraph IsomorphismSubgraph Mining
Subgraph matching is one of the most important problems in graph analytics. Many algorithms and systems have been proposed for subgraph matching. Most of these works follow Ullmann's backtracking approach as it is memory-efficient in handling an explosive number of intermediate matching results. However, they have largely overlooked an intrinsic problem of backtracking, namely repeated computation, which contributes to a large portion of the heavy computation in subgraph matching. This paper proposes a subgraph matching system, Circinus, which enables effective computation sharing by a new compression-based backtracking method. Our extensive experiments show that Circinus significantly reduces repeated computation, which transfers to up to several orders of magnitude performance improvement.
35
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
2017 USENIX Annual Technical Conference (USENIX ATC'17)
Do Le Quoc, Martin S. Beck, Pramod Bhatotia et al. · 2017 · 3.1K citations
An Algorithm for Subgraph Isomorphism
J. R. Ullmann · Journal of the ACM · 1976 · 2.3K citations · Full text
Xifeng Yan, Philip S. Yu, Jiawei Han · 2004 · 635 citations
Huahai He, Ambuj K. Singh · 2008 · 449 citations