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: 10089
Venue: VLDB
Year: 2010
Pagerank: 0.00021475362
Overall Rank: 506 | 96.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Peixiang Zhao
2. Jiawei Han

Incoming Citations (Sorted by Pagerank)

Showing 3 of 53 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,733	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1945683e-05
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05
11,570	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	4.1945683e-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
171	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038830709
203	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034889335
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
301	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00028370644
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
336	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00027020919
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
900	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015495155
919	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015343179

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
4,067	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4795399e-05
4,072	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.4727847e-05
8,070	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.5932982e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
5,597	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4178241e-05
8,256	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.5490743e-05
4,745	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	5.9573154e-05
6,138	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1915368e-05