Multi-Constraint Shortest Path using Forest Hop Labeling

The textitMulti-Constraint Shortest Path (MCSP) problem aims to find the shortest path between two nodes in a network subject to a given constraint set. It is typically processed as a textitskyline path problem. However, the number of intermediate skyline paths becomes larger as the network size increases and the constraint number grows, which brings about the dramatical growth of computational cost and further makes the existing index-based methods hardly capable of obtaining the complete exact results. In this paper, we propose a novel high-dimensional skyline path concatenation method to avoid the expensive skyline path search, which then supports the efficient construction of hop labeling index for textitMCSP queries. Specifically, a set of insightful observations and techniques are proposed to improve the efficiency of concatenating two skyline path set, a textitn-Cube technique is designed to prune the concatenation space among multiple hops, and a textitconstraint pruning method is used to avoid the unnecessary computation. Furthermore, to scale up to larger networks, we propose a novel textitforest hop labeling which enables the parallel label construction from different network partitions. Our approach is the first method that can achieve both accuracy and efficiency for textitMCSP query answering. Extensive experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art solutions.