Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions

Summary: Introduces Kleene Language Constrained Shortest Paths for dynamic, label-based edge restrictions in road-network queries. Extends Contraction Hierarchies to support these constraints, delivering over 3 orders of magnitude speedups on a 50M-edge North American road network vs naive Dijkstra and over 2 orders of magnitude vs prior indexing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10487
Venue: VLDB
Year: 2011
Pagerank: 0.00011484136
Overall Rank: 1,251 | 91.42%
DOI: 10.14778/1921071.1921076

Incoming Non-self Citations Over Time

Authors

1. Michael Rice (University of California Riverside)
2. Vassilis J. Tsotras (University of California Riverside)

BibTeX Citation

@article{rice_vldb11,
        title = {{Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions}},
        author = {Rice, Michael and Tsotras, Vassilis J.},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {2},
        pages = {69--80},
        doi = {10.14778/1921071.1921076},
        url = {https://doi.org/10.14778/1921071.1921076},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013028107
1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011664469
1,386	On k-skip Shortest Paths	2011	SIGMOD	0.00010950754
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	6.779194e-05
6,829	Utility-Aware Ridesharing on Road Networks	2017	SIGMOD	5.7600666e-05
7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.6667372e-05
7,976	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	5.5152959e-05
9,632	Fast Network K-function-based Spatial Analysis	2022	VLDB	5.2434488e-05
9,815	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.214913e-05
10,789	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	5.093636e-05
11,213	LION: Fast and High-Resolution Network Kernel Density Visualization	2024	VLDB	5.093636e-05
11,271	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	5.093636e-05
12,126	CANDS: Continuous Optimal Navigation via Distributed Stream Processing	2015	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
2	11,401	QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks	2023	SIGMOD
3	9,619	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
4	1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
5	9,815	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB
6	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
7	1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
8	10,789	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD
9	7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
10	2,097	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB