Contracting and Compressing Shortest Path Databases
| Shortest Path Compressed Path Databases Contraction Hierarchies |
PaperID: 206
pdf
poster
|
| Compressed Path Databases (CPD) are powerful database-driven methods for shortest path extraction in grids and in spatial networks. Yet CPDs have two main drawbacks: (1) constructing the database requires an offline all-pairs precompute, which can sometimes be prohibitive and; (2) extracting a path requires a number of database lookups equal to its number of edges, which can be costly in terms of time. In this work, we consider how CPD methods can be improved and enhanced by: (i) contracting the input graph before preprocessing and; (ii) by limiting the preprocessing step to only a selected subset of graph nodes. We also describe a new bi-directional path extraction algorithm which we call CH-CPD. In a range of experiments on road networks, we show that CH-CPD substantially improves on conventional CPDs in terms of preprocessing costs and online performance. We also report convincing query time improvements against a range of methods from the recent literature. | |
Session 9: Classical Planning | Search
Jump Point Search with Temporal Obstacles
Authors: Shuli Hu, Daniel Harabor, Graeme Gange, Peter Stuckey and Nathan Sturtevant
Keywords:
heuristicpathfindingjump point searchtemporal obstacles
Width-Based Backward Search
Authors: Chao Lei and Nir Lipovetzky
Keywords:
classical planningsearchregression
The Consistent Case in Bidirectional Search and a Bucket-to-Bucket Algorithm as a Middle Ground between Front-to-End and Front-to-Front
Authors: Vidal Alcázar
Keywords:
bidirectionalheuristicconsistency
Contracting and Compressing Shortest Path Databases
Authors: Bojie Shen, Muhammad Aamir Cheema, Daniel Harabor and Peter Stuckey
Keywords:
Shortest PathCompressed Path DatabasesContraction Hierarchies