Efficient Subgraph Matching on Billion Node Graphs
Summary: Subgraph matching on billion-node graphs with a distributed-memory store. A novel algorithm avoids super-linear indices, relying on efficient graph exploration and massive parallelism for scalable query processing; experiments demonstrate web-scale feasibility. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Zhao Sun (Fudan University)
- 2. Hongzhi Wang (Harbin Engineering University)
- 3. Haixun Wang (Microsoft)
- 4. Bin Shao (Microsoft)
- 5. Jianzhong Li (Harbin Engineering University)
BibTeX Citation
@article{sun_vldb12,
title = {{Efficient Subgraph Matching on Billion Node Graphs}},
author = {Sun, Zhao and Wang, Hongzhi and Wang, Haixun and Shao, Bin and Li, Jianzhong},
journal = {PVLDB},
series = {{VLDB} '12},
volume = {5},
number = {9},
pages = {788},
doi = {10.14778/2311906.2311907},
url = {https://doi.org/10.14778/2311906.2311907},
year = {2012}
}Incoming Citations (Sorted by Pagerank)
Showing 7 of 57 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,428 | An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] | 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,558 | Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration | 2026 | VLDB | 5.093636e-05 |
| 10,787 | cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns | 2025 | SIGMOD | 5.093636e-05 |
| 11,075 | Mix & Match: Subgraph Matching for Absolute Coverage | 2025 | VLDB | 5.093636e-05 |
| 11,165 | gSWORD: GPU-accelerated Sampling for Subgraph Counting | 2024 | SIGMOD | 5.093636e-05 |
| 11,756 | Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees | 2020 | SIGMOD | 5.093636e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3 | Pregel: A System for Large-Scale Graph Processing | 2010 | SIGMOD | 0.0012250108 |
| 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 |
| 591 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.0001603683 |
| 776 | Distance-Join: Pattern Match Query In a Large Graph Database | 2009 | VLDB | 0.00014110016 |
| 908 | Probase: A Probabilistic Taxonomy for Text Understanding | 2012 | SIGMOD | 0.00013300624 |
| 1,231 | SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs | 2010 | VLDB | 0.00011571594 |
| 3,548 | Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases | 2012 | VLDB | 7.3214417e-05 |
| 4,282 | Mining Top-K Large Structural Patterns in a Massive Network | 2011 | VLDB | 6.7842201e-05 |
| 4,853 | Efficient Subgraph Search over Large Uncertain Graphs | 2011 | VLDB | 6.4780097e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,370 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD |
| 2 | 3,709 | Multi-Query Optimization for Subgraph Isomorphism Search | 2017 | VLDB |
| 3 | 5,581 | Subgraph Matching over Graph Federation | 2022 | VLDB |
| 4 | 659 | Efficient Subgraph Matching by Postponing Cartesian Products | 2016 | SIGMOD |
| 5 | 3,477 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB |
| 6 | 10,050 | Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query | 2020 | SIGMOD |
| 7 | 10,564 | gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs | 2026 | VLDB |
| 8 | 10,558 | Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration | 2026 | VLDB |
| 9 | 10,204 | Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching | 2026 | SIGMOD |
| 10 | 2,190 | Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching | 2021 | SIGMOD |