Contracting and Compressing Shortest Path Databases

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)

Abstract

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) 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.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First International Conference on Automated Planning and Scheduling
EditorsSusanne Biundo, Minh Do, Robert Goldman, Michael Katz, Qiang Yang, Hankz Hankui Zhuo
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages322-330
Number of pages9
ISBN (Electronic)9781713832317, 9781577358671
Publication statusPublished - 2021
EventInternational Conference on Automated Planning and Scheduling 2021 - Online, Guangzhou, China
Duration: 2 Aug 202113 Aug 2021
Conference number: 31st
https://ojs.aaai.org/index.php/ICAPS/issue/view/380 (Proceedings)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume2021-August
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2021
Abbreviated titleICAPS 2021
Country/TerritoryChina
CityGuangzhou
Period2/08/2113/08/21
Internet address

Cite this