On k-skip Shortest Paths

Summary: Introduces k-skip shortest paths: P* hits every k-th vertex along the SP, yielding a 1/k sampled description. SNDB algorithms compute k-skip SPs faster than full SPs with a compact index smaller than the road network, validated on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4401
Venue: SIGMOD
Year: 2011
Pagerank: 0.00014422699
Overall Rank: 1,054 | 92.67%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
2,766	On k-Path Covers and their Applications	2014	VLDB	8.1526804e-05
4,534	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.1049756e-05
6,743	Utility-Aware Ridesharing on Road Networks	2017	SIGMOD	4.9430196e-05
8,885	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB	4.4282232e-05
11,413	Online Ridesharing with Meeting Points	2022	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023310419
945	Path Oracles for Spatial Networks	2009	VLDB	0.00015137526
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,078	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	4.400728e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
6,503	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.0357715e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
4,542	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD	6.1019408e-05
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023310419
5,597	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4178241e-05
2,766	On k-Path Covers and their Applications	2014	VLDB	8.1526804e-05