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: 4463
Venue: SIGMOD
Year: 2011
Pagerank: 0.00010950754
Overall Rank: 1,386 | 90.50%
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,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011664469
1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011566372
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
3,415	On k-Path Covers and their Applications	2014	VLDB	7.4313072e-05
4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.6355948e-05
6,829	Utility-Aware Ridesharing on Road Networks	2017	SIGMOD	5.7600666e-05
9,032	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB	5.327953e-05
11,611	Online Ridesharing with Meeting Points	2022	VLDB	5.093636e-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
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
968	Path Oracles for Spatial Networks	2009	VLDB	0.00012901559
1,251	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011484136

Semantically Similar Papers

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