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: 6659
Venue: SIGMOD
Year: 2023
Pagerank: 5.1725247e-05
Overall Rank: 11,201 | 22.16%
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,664	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.2956801e-05
10,525	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	5.1725247e-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
270	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022892419
1,681	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010108085
1,772	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.8669496e-05
2,110	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.2155507e-05
2,516	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.5486549e-05
2,826	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	8.1351358e-05
3,561	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.3703764e-05
4,338	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.8270435e-05
4,431	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB	6.7642043e-05
5,139	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.4143412e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,139	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.4143412e-05
10,088	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD	5.1725247e-05
2,059	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	9.3142927e-05
10,525	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	5.1725247e-05
1,360	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011150375
9,664	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.2956801e-05
7,104	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.754502e-05
2,516	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.5486549e-05
9,224	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	5.3616561e-05
1,252	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011557184