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

1. Peixiang Zhao (University of Illinois Urbana-Champaign)
2. Jiawei Han (University of Illinois Urbana-Champaign)

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

Rank	Citing Paper	Year	Venue	Pagerank
10,419	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,552	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	5.093636e-05
11,165	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	5.093636e-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
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

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