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
7076
Venue
SIGMOD
Year
2025
Pagerank
5.687428e-05
Overall Rank
7,150 | 50.95%
DOI
10.1145/3709665
Incoming Non-self Citations Over Time
BibTeX Citation
Copy BibTeX
@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 7 of 7 citing papers.
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
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
485
TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases
2013
SIGMOD
0.00017717377
634
Rethinking SIMD Vectorization for In-Memory Databases
2015
SIGMOD
0.00015533814
649
Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask
2018
VLDB
0.00015320656
659
Efficient Subgraph Matching by Postponing Cartesian Products
2016
SIGMOD
0.00015214062
1,006
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together
2019
SIGMOD
0.00012699518
1,058
Graphflow: An Active Graph Database
2017
SIGMOD
0.00012378784
1,102
CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching
2019
SIGMOD
0.00012166591
1,199
Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads
2016
SIGMOD
0.00011703966
1,237
In-Memory Subgraph Matching: An In-depth Study
2020
SIGMOD
0.00011545768
1,552
Scalable Subgraph Enumeration in MapReduce
2015
VLDB
0.00010379532
1,857
Joins via Geometric Resolutions: Worst-case and Beyond
2015
PODS
9.6047945e-05
2,035
RapidMatch: A Holistic Approach to Subgraph Query Processing
2021
VLDB
9.2787188e-05
2,065
Scalable Distributed Subgraph Enumeration
2017
VLDB
9.2352771e-05
2,119
DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine
2016
SIGMOD
9.141144e-05
2,187
Subgraph Matching: on Compression and Computation
2018
VLDB
8.9966682e-05
2,190
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching
2021
SIGMOD
8.9804702e-05
2,650
TreeSpan: Efficiently Computing Similarity All-Matching
2012
SIGMOD
8.2920414e-05
3,194
GuP: Fast Subgraph Matching by Guard-based Pruning
2023
SIGMOD
7.6491858e-05
4,158
HUGE: An Efficient and Scalable Subgraph Enumeration System
2021
SIGMOD
6.8628196e-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
4,995
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction
2023
SIGMOD
6.4089186e-05
6,393
BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification
2023
VLDB
5.8879832e-05
7,764
Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling
2017
SIGMOD
5.5499989e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
1,102
CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching
2019
SIGMOD
2
1,006
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together
2019
SIGMOD
3
442
Efficient Subgraph Matching on Billion Node Graphs
2012
VLDB
4
5,758
Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach
2025
SIGMOD
5
2,190
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching
2021
SIGMOD
6
4,995
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction
2023
SIGMOD
7
11,075
Mix & Match: Subgraph Matching for Absolute Coverage
2025
VLDB
8
10,312
BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching
2026
SIGMOD
9
659
Efficient Subgraph Matching by Postponing Cartesian Products
2016
SIGMOD
10
4,983
A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction
2024
SIGMOD