DBScholar

Back to papers

TreeSpan: Efficiently Computing Similarity All-Matching

Summary: TreeSpan uses a spanning-tree cover QT to span all q subgraphs within theta; exact matching on each tree yields similarity matches. Approach blends with filtering, sharing, and ordered search, yielding 7 orders-of-magnitude speedups over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4613
Venue
SIGMOD
Year
2012
Pagerank
8.2920414e-05
Overall Rank
2,650 | 81.83%
DOI
10.1145/2213836.2213896

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{zhu_sigmod12,
        title = {{TreeSpan: Efficiently Computing Similarity All-Matching}},
        author = {Zhu, Gaoping and Lin, Xuemin and Zhu, Ke and Zhang, Wenjie and Yu, Jeffrey Xu},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213896},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213896},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
659 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00015214062
1,036 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00012499878
3,522 A Partition-Based Approach to Structure Similarity Search 2014 VLDB 7.3491042e-05
4,503 Event Pattern Matching over Graph Streams 2015 VLDB 6.6597953e-05
6,728 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.7898807e-05
6,895 QUBLE: Blending Visual Subgraph Query Formulation with Query Processing on Large Networks 2013 SIGMOD 5.7442637e-05
7,150 BSX : Subgraph Matching with Batch Backtracking Search 2025 SIGMOD 5.687428e-05
7,152 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 5.6872619e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-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,552 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 5.093636e-05
10,952 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 5.093636e-05
11,762 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Previous Page 1 / 1 Next

Semantically Similar Papers