Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks

Summary: Introduces Query-by-Sketch (QbS) for exact shortest-path-graph queries on massive networks, using offline labels to guide online sketch. Proves correctness/complexity; 12 datasets (up to 1.7B vertices, 7.8B edges) yield microseconds on million-scale and sub-second on billion-scale. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6107
Venue: SIGMOD
Year: 2021
Pagerank: 5.1865526e-05
Overall Rank: 6,144 | 57.30%
DOI: 10.1145/3448016.3452826

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,983	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8682622e-05
7,439	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	4.7256836e-05
8,252	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.544713e-05
8,666	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	4.467539e-05
10,477	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1905499e-05
10,580	Quantum Data Management in the NISQ Era	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
377	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025074538
946	Path Oracles for Spatial Networks	2009	VLDB	0.00015117675
1,173	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013501079
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,074	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.58889e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
4,207	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3519481e-05
8,252	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.544713e-05
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
7,240	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	4.7869144e-05
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261