Efficient Constrained Shortest Path Query Answering with Forest Hop Labeling

Ziyi Liu, Lei Li, Mengxuan Zhang, Wen Hua, Pingfu Chao, Xiaofang Zhou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

11 Citations (Scopus)


The Constrained Shortest Path (CSP) problem aims to find the shortest path between two nodes in a road network subject to a given constraint on another attribute. It is typically processed as a skyline path problem on the two attributes, resulting in very high computational cost which can be prohibitive for large road networks. The main bottleneck is to deal with a large amount of partial skyline paths, which further makes the existing index-based methods incapable to obtain the complete exact skyline paths. In this paper, we propose a novel skyline path concatenation approach to avoid the expensive skyline path search, which is then used to efficiently construct a 2-hop labeling index for the CSP queries. Specifically, a rectangle-based technique is designed to prune the concatenation space from multiple hops, and a constraint pruning method is used to further speed up the CSP query processing. To further scale up to larger networks, we propose a novel forest hop labeling that constructs labels from different partitions in parallel. Our approach is the first method that can achieve both accuracy and efficiency for CSP query answering. Extensive experiments on real-life road networks demonstrate that our method outperforms the state-of-the-art CSP solutions by several orders of magnitude.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781728191843
Publication statusPublished - Apr 2021
Externally publishedYes
Event37th IEEE International Conference on Data Engineering, ICDE 2021 - Virtual, Chania, Greece
Duration: 19 Apr 202122 Apr 2021

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference37th IEEE International Conference on Data Engineering, ICDE 2021
CityVirtual, Chania


  • Constrained shortest path
  • Hop labeling
  • Road network

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Efficient Constrained Shortest Path Query Answering with Forest Hop Labeling'. Together they form a unique fingerprint.

Cite this