On Graph Query Optimization in Large Networks

Summary: SPath: a high-performance graph index for large networks built from decomposed shortest paths around vertex neighborhoods. Query planning decomposes the query into candidate paths, selects a subset, and joins them to reconstruct the query graph, enabling scalable path-at-a-time querying and beating vertex-at-a-time and GraphQL baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10090
Venue: VLDB
Year: 2010
Pagerank: 0.00020516762
Overall Rank: 352 | 97.56%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Peixiang Zhao
2. Jiawei Han

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
434	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018612924
487	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017695307
682	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015144404
1,031	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012615956
1,048	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012532323
1,097	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012273511
1,201	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011794097
1,278	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011462905
1,469	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010747632
1,566	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010397786
1,873	Exemplar Queries: Give me an Example of What You Need	2014	VLDB	9.661206e-05
1,940	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.5218266e-05
2,094	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.2515997e-05
2,162	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	9.0994327e-05
2,214	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.008953e-05
2,312	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.8466711e-05
2,689	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	8.317052e-05
2,789	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.1864277e-05
2,827	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	8.1346366e-05
3,396	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.5176876e-05
3,677	On Querying Historical Evolving Graph Sequences	2011	VLDB	7.2698666e-05
3,762	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.1990313e-05
3,918	Natural Language Question Answering over RDF — A Graph Data Driven Approach	2014	SIGMOD	7.0826322e-05
3,948	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	7.0699328e-05
4,186	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.9091925e-05
4,693	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	6.6231764e-05
4,702	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	6.6188333e-05
4,750	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.5980489e-05
5,200	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	6.3897796e-05
5,223	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	6.3799903e-05
5,297	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.347246e-05
5,779	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	6.1549096e-05
6,059	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	6.0534485e-05
6,332	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.9722544e-05
6,546	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.9031535e-05
6,620	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.8801038e-05
6,819	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	5.8222444e-05
6,973	CAVE: Concurrency-Aware Graph Processing on SSDs	2024	SIGMOD	5.7955627e-05
7,235	Extending Graph Patterns with Conditions	2020	SIGMOD	5.7195408e-05
7,771	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.6064466e-05
8,111	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	5.5423036e-05
8,117	Fast Local Subgraph Counting	2024	VLDB	5.5419908e-05
8,453	RBench: Application-Specific RDF Benchmarking	2015	SIGMOD	5.4921413e-05
8,805	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	5.4311509e-05
9,445	Banyan: A Scoped Dataflow Engine for Graph Query Service	2022	VLDB	5.332142e-05
9,523	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.3218384e-05
9,717	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	5.2849709e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	5.1725247e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	5.1725247e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	5.1725247e-05

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
175	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027377116
188	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026415788
268	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022984157
270	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022892419
292	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.0002223786
297	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00022068839
315	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021518897
321	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021373781
428	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018725237
725	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014708873
736	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.0001459447
762	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014288919

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,762	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.1990313e-05
736	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.0001459447
3,794	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	7.1757545e-05
3,436	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	7.482297e-05
8,111	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	5.5423036e-05
434	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018612924
5,139	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.4143412e-05
8,011	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.5653705e-05
4,226	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	6.8841731e-05
5,770	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	6.157172e-05