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.6854796e-05
Overall Rank
6,711 | 55.02%
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 9 of 9 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
8,899
Subgraph Matching: A New Decomposition Based Approach 2025
VLDB
5.2401722e-05
10,289
A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026
SIGMOD
5.031399e-05
10,333
MAVIS: Materialized View for Subgraph Matching 2026
SIGMOD
5.0225409e-05
10,379
Algebraic Subgraph Counting 2027
SIGMOD
4.9605343e-05
10,805
CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026
VLDB
4.9605343e-05
10,811
Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026
VLDB
4.9605343e-05
10,817
gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs 2026
VLDB
4.9605343e-05
10,859
Subgraph Enumeration: Beyond Tree Decomposition 2026
VLDB
4.9605343e-05
11,059
Aquila: A High-Concurrency System for Incremental Graph Query 2026
VLDB
4.9605343e-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.00024929198
235
The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018
VLDB
0.00023701614
288
Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008
SIGMOD
0.00022009138
485
TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013
SIGMOD
0.00017479773
606
Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask 2018
VLDB
0.00015609823
627
Rethinking SIMD Vectorization for In-Memory Databases 2015
SIGMOD
0.00015430074
658
Efficient Subgraph Matching by Postponing Cartesian Products 2016
SIGMOD
0.00015032442
952
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019
SIGMOD
0.00012878316
1,049
Graphflow: An Active Graph Database 2017
SIGMOD
0.00012293903
1,090
CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019
SIGMOD
0.00012062682
1,171
In-Memory Subgraph Matching: An In-depth Study 2020
SIGMOD
0.00011677799
1,188
Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads 2016
SIGMOD
0.00011580449
1,565
Scalable Subgraph Enumeration in MapReduce 2015
VLDB
0.00010185615
1,821
Joins via Geometric Resolutions: Worst-case and Beyond 2015
PODS
9.5466386e-05
1,907
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021
SIGMOD
9.379165e-05
1,988
RapidMatch: A Holistic Approach to Subgraph Query Processing 2021
VLDB
9.2301018e-05
2,023
Scalable Distributed Subgraph Enumeration 2017
VLDB
9.1568397e-05
2,101
DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine 2016
SIGMOD
9.0309825e-05
2,128
Subgraph Matching: on Compression and Computation 2018
VLDB
8.9879343e-05
2,705
TreeSpan: Efficiently Computing Similarity All-Matching 2012
SIGMOD
8.0936619e-05
3,107
GuP: Fast Subgraph Matching by Guard-based Pruning 2023
SIGMOD
7.6265309e-05
4,099
A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024
SIGMOD
6.7940875e-05
4,133
HUGE: An Efficient and Scalable Subgraph Enumeration System 2021
SIGMOD
6.7738028e-05
4,370
Circinus: Fast Redundancy-Reduced Subgraph Matching 2023
SIGMOD
6.6213567e-05
4,485
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction 2023
SIGMOD
6.5644966e-05
6,251
BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023
VLDB
5.8179719e-05
7,649
Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017
SIGMOD
5.4598986e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
1,090
CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019
SIGMOD
2
952
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019
SIGMOD
3
440
Efficient Subgraph Matching on Billion Node Graphs 2012
VLDB
4
5,895
Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach 2025
SIGMOD
5
1,907
Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021
SIGMOD
6
4,485
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction 2023
SIGMOD
7
11,491
Mix & Match: Subgraph Matching for Absolute Coverage 2025
VLDB
8
9,881
BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026
SIGMOD
9
658
Efficient Subgraph Matching by Postponing Cartesian Products 2016
SIGMOD
10
4,099
A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024
SIGMOD