DBScholar

Back to papers

On Graph Query Optimization in Large Networks

Summary: SPath indexes large graphs using decomposed shortest paths around vertex neighborhoods, enabling scalable pruning and construction. Its optimizer shifts subgraph matching from vertex-at-a-time to selective path-at-a-time decomposition and joins, outperforming GraphQL on real and synthetic networks. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h4e882d63e732865d
Venue
VLDB
Year
2010
Pagerank
0.00020086045
Overall Rank
356 | 97.62%
DOI
10.14778/1920841.1920887

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{zhao_vldb10,
        title = {{On Graph Query Optimization in Large Networks}},
        author = {Zhao, Peixiang and Han, Jiawei},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {340--351},
        doi = {10.14778/1920841.1920887},
        url = {https://doi.org/10.14778/1920841.1920887},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 54 citing papers.

Rank Citing Paper Year Venue Pagerank
440 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018235529
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017479773
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,046 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00012315969
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,180 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011600363
1,502 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB 0.00010431532
1,565 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 0.00010185615
1,873 Efficient SimRank-based Similarity Join Over Large Graphs 2013 VLDB 9.4472588e-05
1,907 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.379165e-05
1,964 Exemplar Queries: Give me an Example of What You Need 2014 VLDB 9.2831855e-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,226 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.7971869e-05
2,478 GPU-Accelerated Subgraph Enumeration on Partitioned Graphs 2020 SIGMOD 8.3890338e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
2,705 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.0936619e-05
3,020 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7267183e-05
3,107 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6265309e-05
3,665 On Querying Historical Evolving Graph Sequences 2011 VLDB 7.0996773e-05
3,771 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 7.0132957e-05
4,103 Natural Language Question Answering over RDF — A Graph Data Driven Approach 2014 SIGMOD 6.792391e-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,801 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.3940913e-05
4,835 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 6.3793473e-05
4,938 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.3327465e-05
5,404 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.132986e-05
5,486 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.097643e-05
5,995 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.903845e-05
6,245 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.8210521e-05
6,251 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8179719e-05
6,272 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.8112899e-05
6,315 Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs 2020 SIGMOD 5.7968933e-05
6,632 CAVE: Concurrency-Aware Graph Processing on SSDs 2024 SIGMOD 5.7111251e-05
6,829 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.6556888e-05
7,502 Extending Graph Patterns with Conditions 2020 SIGMOD 5.4943054e-05
7,552 Fast Local Subgraph Counting 2024 VLDB 5.4802093e-05
8,067 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 5.3810658e-05
8,399 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB 5.3235867e-05
8,706 RBench: Application-Specific RDF Benchmarking 2015 SIGMOD 5.2706868e-05
8,899 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2401722e-05
9,126 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD 5.208561e-05
9,684 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 5.1258854e-05
9,750 Banyan: A Scoped Dataflow Engine for Graph Query Service 2022 VLDB 5.1165079e-05
9,884 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1037285e-05
10,101 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.068372e-05
10,281 Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query 2020 SIGMOD 5.0334833e-05
Previous Page 1 / 2 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.

Rank Cited Paper Year Venue Pagerank
176 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00026634326
195 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00025589066
269 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022625826
272 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022559588
288 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022009138
294 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021884041
331 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00020800828
333 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00020712452
439 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018247958
734 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00014334121
779 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00014049427
786 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00013979657
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,684 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB
2 779 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD
3 3,933 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD
4 3,506 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB
5 8,399 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB
6 440 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB
7 5,357 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB
8 5,409 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB
9 4,125 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD
10 5,893 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD