Back to papers
BSX : Subgraph Matching with Batch Backtracking Search
Summary: BSX proposes batch backtracking for subgraph matching, processing data-vertex batches per step to cut redundant search. A search-box model clusters similar search spaces with pruning and early homomorphism termination, plus embedding enumeration, yielding 1–2 orders of magnitude speedup on real graphs.
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
hac4a473b9bc41fed
Venue
SIGMOD
Year
2025
Pagerank
5.6328006e-05
Overall Rank
6,965 | 53.18%
DOI
10.1145/3709665
Incoming Non-self Citations Over Time
BibTeX Citation
@inproceedings{lu_sigmod25,
title = {{BSX : Subgraph Matching with Batch Backtracking Search}},
author = {Lu, Yujie and Zhang, Zhijie and Zheng, Weiguo},
series = {{SIGMOD} '25},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3709665},
url = {https://dl.acm.org/doi/10.1145/3709665},
year = {2025}
}
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
9,361
Subgraph Matching: A New Decomposition Based Approach 2025
VLDB
5.1868213e-05
10,254
A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026
SIGMOD
5.050482e-05
10,300
MAVIS: Materialized View for Subgraph Matching 2026
SIGMOD
5.0415903e-05
10,734
CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026
VLDB
4.9793485e-05
10,740
Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026
VLDB
4.9793485e-05
10,746
gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs 2026
VLDB
4.9793485e-05
10,788
Subgraph Enumeration: Beyond Tree Decomposition 2026
VLDB
4.9793485e-05
10,989
Aquila: A High-Concurrency System for Incremental Graph Query 2026
VLDB
4.9793485e-05
Outgoing Citations (Sorted by Pagerank)
Showing 27 of 27 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
208
EmptyHeaded: A Relational Engine for Graph Processing 2016
SIGMOD
0.00024884544
239
The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018
VLDB
0.000235107
288
Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008
SIGMOD
0.00021969641
490
TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013
SIGMOD
0.00017438618
605
Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask 2018
VLDB
0.00015647561
627
Rethinking SIMD Vectorization for In-Memory Databases 2015
SIGMOD
0.00015460957
657
Efficient Subgraph Matching by Postponing Cartesian Products 2016
SIGMOD
0.0001505607
960
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019
SIGMOD
0.00012836554
1,045
Graphflow: An Active Graph Database 2017
SIGMOD
0.00012322402
1,100
CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019
SIGMOD
0.00012013426
1,180
In-Memory Subgraph Matching: An In-depth Study 2020
SIGMOD
0.00011627669
1,200
Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads 2016
SIGMOD
0.00011563303
1,572
Scalable Subgraph Enumeration in MapReduce 2015
VLDB
0.00010197978
1,812
Joins via Geometric Resolutions: Worst-case and Beyond 2015
PODS
9.5803973e-05
1,900
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021
SIGMOD
9.4059063e-05
2,014
RapidMatch: A Holistic Approach to Subgraph Query Processing 2021
VLDB
9.1832045e-05
2,020
Scalable Distributed Subgraph Enumeration 2017
VLDB
9.1729558e-05
2,101
DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine 2016
SIGMOD
9.0476814e-05
2,166
Subgraph Matching: on Compression and Computation 2018
VLDB
8.9334874e-05
2,702
TreeSpan: Efficiently Computing Similarity All-Matching 2012
SIGMOD
8.1177147e-05
3,164
GuP: Fast Subgraph Matching by Guard-based Pruning 2023
SIGMOD
7.5771124e-05
4,075
A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024
SIGMOD
6.8188389e-05
4,123
HUGE: An Efficient and Scalable Subgraph Enumeration System 2021
SIGMOD
6.7927568e-05
4,511
Circinus: Fast Redundancy-Reduced Subgraph Matching 2023
SIGMOD
6.5681258e-05
4,587
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction 2023
SIGMOD
6.5161686e-05
6,504
BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023
VLDB
5.7617085e-05
7,634
Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017
SIGMOD
5.4792319e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
1,100
CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019
SIGMOD
2
960
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019
SIGMOD
3
443
Efficient Subgraph Matching on Billion Node Graphs 2012
VLDB
4
5,880
Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach 2025
SIGMOD
5
1,900
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021
SIGMOD
6
4,587
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction 2023
SIGMOD
7
11,432
Mix & Match: Subgraph Matching for Absolute Coverage 2025
VLDB
8
10,253
BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026
SIGMOD
9
657
Efficient Subgraph Matching by Postponing Cartesian Products 2016
SIGMOD
10
4,075
A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024
SIGMOD