DBScholar

Back to papers

Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching

Summary: Introduces vertex-equivalence techniques to speed subgraph search and matching. Static equivalence among query-graph vertices yields a fixed, efficient matching order; dynamic equivalence among data-graph candidates prunes redundant search paths, delivering large speedups over state-of-the-art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
6218
Venue
SIGMOD
Year
2021
Pagerank
8.9804702e-05
Overall Rank
2,190 | 84.98%
DOI
10.1145/3448016.3457265

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kim_sigmod21,
        title = {{Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching}},
        author = {Kim, Hyunjoon and Choi, Yunyoung and Park, Kunsoo and Lin, Xuemin and Hong, Seok-Hee and Han, Wook-Shin},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457265},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457265},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 38 of 38 citing papers.

Rank Citing Paper Year Venue Pagerank
2,731 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1959181e-05
3,102 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7568687e-05
4,563 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.6291459e-05
4,983 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.4127092e-05
5,275 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.2873652e-05
5,758 Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach 2025 SIGMOD 6.0972035e-05
5,870 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 6.061038e-05
5,942 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.0334209e-05
6,149 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.9581422e-05
6,393 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8879832e-05
6,924 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.738697e-05
7,150 BSX : Subgraph Matching with Batch Backtracking Search 2025 SIGMOD 5.687428e-05
8,251 Fast Local Subgraph Counting 2024 VLDB 5.4574671e-05
8,586 A Framework for Privacy Preserving Localized Graph Pattern Query Processing 2023 SIGMOD 5.4073203e-05
8,871 MatCo: Computing Match Cover of Subgraph Query over Graph Data 2025 SIGMOD 5.35418e-05
9,617 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.2434488e-05
9,693 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2351259e-05
9,872 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.2043672e-05
10,084 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.1573064e-05
10,204 Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching 2026 SIGMOD 5.093636e-05
10,294 Sublime: Selecting Subgraph Matching Algorithms via Machine Learning 2026 SIGMOD 5.093636e-05
10,312 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.093636e-05
10,419 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,428 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,452 Enumerating Graph Pattern Matches with ML Oracles 2026 SIGMOD 5.093636e-05
10,488 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 5.093636e-05
10,524 A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs 2026 VLDB 5.093636e-05
10,552 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 5.093636e-05
10,558 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 5.093636e-05
10,564 gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs 2026 VLDB 5.093636e-05
10,590 Aquila: A High-Concurrency System for Incremental Graph Query 2026 VLDB 5.093636e-05
10,598 Scalable Approximate Biclique Counting over Large Bipartite Graphs 2026 VLDB 5.093636e-05
10,606 Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching 2026 VLDB 5.093636e-05
10,885 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 5.093636e-05
10,952 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 5.093636e-05
11,072 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.093636e-05
11,075 Mix & Match: Subgraph Matching for Absolute Coverage 2025 VLDB 5.093636e-05
11,502 Density Personalized Group Query 2023 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
177 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00027100548
211 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024797217
264 The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018 VLDB 0.00022980015
294 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022253507
352 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020375193
431 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018577017
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017717377
659 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00015214062
727 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00014565738
809 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00013874588
1,006 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012699518
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.0001179597
1,237 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011545768
1,487 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB 0.00010615297
2,182 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 9.010121e-05
2,187 Subgraph Matching: on Compression and Computation 2018 VLDB 8.9966682e-05
3,431 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 7.4189541e-05
3,477 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 7.3791229e-05
4,748 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 6.5251089e-05
Previous Page 1 / 1 Next

Semantically Similar Papers