TY - GEN
T1 - FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints
AU - Liu, Ziyi
AU - Li, Lei
AU - Zhang, Mengxuan
AU - Hua, Wen
AU - Zhou, Xiaofang
N1 - Funding Information:
This work was partially supported by the Australian Research Council under Grant No. DP200103650 and LP180100018, Hong Kong Research Grants Council (grant# 16202722), and was partially conducted in the JC STEM Lab of Data Science Foundations funded by The Hong Kong Jockey Club Charities Trust.
Publisher Copyright:
© 2022, VLDB Endowment. All rights reserved.
PY - 2022/7/1
Y1 - 2022/7/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85138007173&partnerID=8YFLogxK
U2 - 10.14778/3551793.3551856
DO - 10.14778/3551793.3551856
M3 - Conference article published in proceeding or book
AN - SCOPUS:85138007173
VL - 15
T3 - Proceedings of the VLDB Endowment
SP - 3112
EP - 3125
BT - PVLDB 2022 - Proceedings of the 48th International Conference on Very Large Databases
PB - VLDB Endowment
T2 - 48th International Conference on Very Large Data Bases, VLDB 2022
Y2 - 5 September 2022 through 9 September 2022
ER -