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
10280
Venue
VLDB
Year
2010
Pagerank
0.00020375193
Overall Rank
352 | 97.59%
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 53 citing papers.

Rank Citing Paper Year Venue Pagerank
442 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018398144
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017717377
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,036 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00012499878
1,102 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012166591
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.0001179597
1,237 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011545768
1,487 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB 0.00010615297
1,552 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 0.00010379532
1,812 Efficient SimRank-based Similarity Join Over Large Graphs 2013 VLDB 9.6948178e-05
1,897 Exemplar Queries: Give me an Example of What You Need 2014 VLDB 9.5243334e-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,182 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 9.010121e-05
2,190 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 8.9804702e-05
2,607 GPU-Accelerated Subgraph Enumeration on Partitioned Graphs 2020 SIGMOD 8.3489531e-05
2,650 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.2920414e-05
2,731 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1959181e-05
3,102 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7568687e-05
3,194 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6491858e-05
3,594 On Querying Historical Evolving Graph Sequences 2011 VLDB 7.2736453e-05
3,709 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 7.1780227e-05
3,981 Natural Language Question Answering over RDF — A Graph Data Driven Approach 2014 SIGMOD 6.9746167e-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,722 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.5438628e-05
4,748 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 6.5251089e-05
4,813 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.4974292e-05
5,275 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.2873652e-05
5,370 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.2436385e-05
5,870 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 6.061038e-05
6,149 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.9581422e-05
6,393 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8879832e-05
6,423 Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs 2020 SIGMOD 5.8813146e-05
6,490 CAVE: Concurrency-Aware Graph Processing on SSDs 2024 SIGMOD 5.8643667e-05
6,728 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.7898807e-05
6,924 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.738697e-05
7,365 Extending Graph Patterns with Conditions 2020 SIGMOD 5.6329929e-05
7,891 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 5.5211516e-05
8,245 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB 5.4577751e-05
8,251 Fast Local Subgraph Counting 2024 VLDB 5.4574671e-05
8,582 RBench: Application-Specific RDF Benchmarking 2015 SIGMOD 5.4081423e-05
8,935 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD 5.3483178e-05
9,532 Banyan: A Scoped Dataflow Engine for Graph Query Service 2022 VLDB 5.2537948e-05
9,665 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.2406724e-05
9,693 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2351259e-05
9,872 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.2043672e-05
10,050 Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query 2020 SIGMOD 5.1685424e-05
10,354 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 5.093636e-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
177 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00027100548
187 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00026138589
269 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022786599
272 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022695855
294 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022253507
302 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021963347
322 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00021275303
326 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00021152829
431 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018577017
727 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00014565738
746 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00014402233
776 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014110016
Previous Page 1 / 1 Next

Semantically Similar Papers

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