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.00021528261
Overall Rank: 502 | 96.52%
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
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
1,125	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013829006
1,487	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011691164
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
1,715	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010776518
1,906	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010135267
1,962	Exemplar Queries: Give me an Example of What You Need	2014	VLDB	9.9463687e-05
2,021	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.7730473e-05
2,118	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.5036922e-05
2,172	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.37776e-05
2,402	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.87387e-05
2,787	Scalable Distributed Subgraph Enumeration	2017	VLDB	8.1219297e-05
2,882	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9666138e-05
2,988	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7752463e-05
3,034	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6737281e-05
3,119	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.5393376e-05
3,217	Natural Language Question Answering over RDF — A Graph Data Driven Approach	2014	SIGMOD	7.3672608e-05
3,488	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	7.0460627e-05
3,643	On Querying Historical Evolving Graph Sequences	2011	VLDB	6.8856861e-05
4,326	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	6.2772512e-05
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
4,756	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	5.9364786e-05
4,955	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	5.8057282e-05
5,002	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	5.7610359e-05
5,490	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4788004e-05
5,502	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.4730826e-05
5,871	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2912806e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
5,921	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	5.2681722e-05
6,391	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0780425e-05
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
6,493	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.0344095e-05
6,965	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	4.8759021e-05
7,091	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	4.8304411e-05
7,256	CAVE: Concurrency-Aware Graph Processing on SSDs	2024	SIGMOD	4.7819929e-05
7,304	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7628386e-05
7,566	Extending Graph Patterns with Conditions	2020	SIGMOD	4.7047078e-05
7,863	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	4.628688e-05
7,936	Fast Local Subgraph Counting	2024	VLDB	4.6089395e-05
8,074	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.58889e-05
8,574	RBench: Application-Specific RDF Benchmarking	2015	SIGMOD	4.4884743e-05
8,762	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	4.4520434e-05
9,519	Banyan: A Scoped Dataflow Engine for Graph Query Service	2022	VLDB	4.3287375e-05
9,523	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3273374e-05
9,729	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2901665e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1905499e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1905499e-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
172	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038837872
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
280	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029092277
302	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00028343691
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027077424
337	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00027002505
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
916	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015326675

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
4,070	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4739921e-05
3,894	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.6531173e-05
8,074	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.58889e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
5,606	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4126223e-05
8,252	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.544713e-05
4,739	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	5.9515822e-05
6,144	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1865526e-05