QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks

Summary: QHL: an exact CSP algorithm for road networks that uses CSP-informed pruning and a preprocessed index of pruning conditions to speed up queries. Real-world experiments show CSP queries around 50 µs and order-of-magnitude improvements over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6658
Venue: SIGMOD
Year: 2023
Pagerank: 4.1945683e-05
Overall Rank: 11,199 | 22.10%
DOI: 10.1145/3589300

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Libin Wang
2. Raymond Chi-Wing Wong

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3047774e-05
10,516	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
2,188	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	9.3372315e-05
2,201	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.3048105e-05
2,639	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3975113e-05
3,342	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.197276e-05
4,193	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.37019e-05
4,973	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB	5.7909705e-05
5,035	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	5.7470184e-05
5,597	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4178241e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,597	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4178241e-05
10,088	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD	4.1945683e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
10,516	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	4.1945683e-05
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3047774e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
2,188	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	9.3372315e-05
9,205	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	4.3736393e-05
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837