We propose a new labeling method for shortest-path and distance queries on road networks. We present a new framework (i.e. data structure and query algorithm) referred to as highway-based labelings and a preprocessing algorithm for it named pruned highway labeling. Our proposed method has several appealing features from different aspects in the literature. Indeed, we take advantages of theoretical analysis of the seminal result by Thorup for distance oracles, more detailed structures of real road networks, and the pruned labeling algorithm that conducts pruned Dijkstra's algorithm. The experimental results show that the proposed method is comparable to the previous state-of-the-art labeling method in both query time and in data size, while our main improvement is that the preprocessing time is much faster. and continuing [11, 4, 9, 10, 5, 6, 1, 2, 7] . One of the most notable recent developments is the emergence of practical labeling methods [1, 2] . Labeling methods precompute label L(v) for each vertex v and answer distance between two points s and t using labels L(s) and L(t) without looking at the input graph. These practical methods adopt the most standard labeling framework (i.e., data structure and query algorithm) called hub-based labelings [1] . The label L(v) is a set of pairs (u, δ uv ), where u is a vertex and δ uv is distance between v and u. Since the labeling method can answer distance by only looking at two consecutive segments of precomputed data, their query time is known to be the fastest among all other proposed methods. In this paper, we shall improve the state-of-the-art algorithm (i.e, the labeling method) in several ways. Specifically, we present a new labeling framework referred to as the highway-based labeling framework and a preprocessing algorithm for the framework named pruned highway labeling. Our proposed method has several appealing features from different aspects in the literature. Distance oracles. The idea behind our approach has some similarity with Thorup's distance oracle for planar graphs [12] . Specifically, our approach repeatedly separates input graphs by shortest paths, and then stores distance from vertices to the shortest paths. These are also keys in Thorup's paper. Indeed, we can adapt Thorup's proof to justify the correctness and efficiency of our proposed algorithm theoretically, to some extent. Highways. Several previous methods exploit highway structure in road networks. Highways are useful since they are central, in the sense that many shortest paths must pass through highways. However, the hub-based labeling algorithm does not directly exploit highways. In contrast, our approach takes more advantage of these highways. Pruned labeling. The notion of pruned labeling [3] is the key ingredient of the recent state-of-the-art label computation algorithms for distance queries on complex networks [3] and reachability queries on DAGs [13] .
The pruned highway labeling approach proposed by Akiba et al. REF decomposes the road network into disjoint paths and the label of a node include the distance to some nodes of the paths.
Fast shortest-path distance queries on road networks by pruned highway labeling
ALENEX
Computer Science