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 3 of 53 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,740	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.1725247e-05
10,951	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	5.1725247e-05
11,574	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	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