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: h17ffd5b3037fd244
Venue: SIGMOD
Year: 2011
Pagerank: 0.00010705427
Overall Rank: 1,426 | 90.42%
DOI: 10.1145/1989323.1989368

Incoming Non-self Citations Over Time

Authors

1. Yufei Tao (Chinese University of Hong Kong)
2. Cheng Sheng (Chinese University of Hong Kong)
3. Jian Pei (Simon Fraser University)

BibTeX Citation

@inproceedings{tao_sigmod11,
        title = {{On k-skip Shortest Paths}},
        author = {Tao, Yufei and Sheng, Cheng and Pei, Jian},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989368},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989368},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,234	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011404678
1,253	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011331798
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010158887
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9828268e-05
3,485	On k-Path Covers and their Applications	2014	VLDB	7.2616863e-05
4,637	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.4902365e-05
6,973	Utility-Aware Ridesharing on Road Networks	2017	SIGMOD	5.6281625e-05
9,193	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB	5.2091591e-05
11,925	Online Ridesharing with Meeting Points	2022	VLDB	4.9769913e-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
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019477423
447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018151383
991	Path Oracles for Spatial Networks	2009	VLDB	0.00012642908
1,270	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011254207

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,416	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB
2	2,143	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB
3	6,087	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
4	7,379	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
5	953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
6	4,786	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD
7	1,270	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB
8	447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD
9	5,343	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
10	3,485	On k-Path Covers and their Applications	2014	VLDB