FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints

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

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

12 Citations (Scopus)

Abstract

Multi-Constraint Shortest Path (MCSP) generalizes the classic shortest path from single to multiple criteria such that more personalized needs can be satisfied. However, MCSP query is essentially a high-dimensional skyline problem and thus time-consuming to answer. Although the current Forest Hop Labeling (FHL) index can answer MCSP efficiently, it takes a long time to construct and lacks the flexibility to handle arbitrary criteria combinations. In this paper, we propose a skyline-cube-based FHL index that can handle the flexible MCSP efficiently. Firstly, we analyze the relation between low and high-dimensional skyline paths theoretically and use a cube to organize them hierarchically. After that, we propose methods to derive the high-dimensional path from the lower ones, which can adapt to the flexible scenario naturally and reduce the expensive high dimensional path concatenation. Then we introduce efficient methods for both single and multi-hop cube concatenations and propose pruning methods to further alleviate the computation. Finally, we improve the FHL structure with lower height for faster construction and query. Experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art.

Original languageEnglish
Title of host publicationPVLDB 2022 - Proceedings of the 48th International Conference on Very Large Databases
PublisherVLDB Endowment
Pages3112-3125
Number of pages14
Volume15
Edition11
DOIs
Publication statusPublished - 1 Jul 2022
Externally publishedYes
Event48th International Conference on Very Large Data Bases, VLDB 2022 - Sydney, Australia
Duration: 5 Sept 20229 Sept 2022

Publication series

NameProceedings of the VLDB Endowment
PublisherVery Large Data Base Endowment Inc.
ISSN (Print)2150-8097

Conference

Conference48th International Conference on Very Large Data Bases, VLDB 2022
Country/TerritoryAustralia
CitySydney
Period5/09/229/09/22

ASJC Scopus subject areas

  • Information Systems

Fingerprint

Dive into the research topics of 'FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints'. Together they form a unique fingerprint.

Cite this