Approximate Skyline Index for Constrained Shortest Pathfinding with Theoretical Guarantee

作者：Ziyi Liu, Lei Li, Mengxuan Zhang, Wen Hua, Xiaofang Zhou · 年份：2024 · DOI：10.1109/icde60146.2024.00322 · 被引用次数：7 · 研究领域：Computational Geometry and Mesh Generation、Robotic Path Planning Algorithms、Artificial Intelligence in Games

The Constrained Shortest Path (CSP) problem seeks to identify the shortest path between two vertices in a road network while adhering to a specific constraint on another criterion. Solving the CSP problem frequently entails navigating the two-criteria skyline path problem, which incurs a substantial computational expense in large road networks. The primary challenge lies in handling a vast quantity of partial skyline paths, which often hinders index-based solutions from accurately determining the skyline paths. This paper introduces a-FHL, a practical approximation method designed to circumvent the costly skyline path search and hasten computation on skyline path indexing. a-FHL uses tree decomposition to hierarchically assign approximation ratios, thereby facilitating effective pruning within the labelling index. Moreover, we devise various strategies to allocate approximation ratios and an efficient approximation concatenation method to respond to the approximate CSP queries via the a-FHL index. Our method culminates in swift index construction and efficient query response. Comprehensive exper-iments conducted on real-world road networks substantiate the superiority of our approach over contemporary solutions