  The \textit{Multi-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 \textit{skyline 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 \textit{MCSP} queries. Specifically, a set of
insightful observations and techniques are proposed to improve the efficiency
of concatenating two skyline path set, a \textit{n-Cube} technique is designed
to prune the concatenation space among multiple hops, and a \textit{constraint
pruning} method is used to avoid the unnecessary computation. Furthermore, to
scale up to larger networks, we propose a novel \textit{forest 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 \textit{MCSP} query answering. Extensive experiments on
real-life road networks demonstrate the superiority of our method over the
state-of-the-art solutions.
