When Hierarchy meets 2-hop-labeling: Effiicient shortest distance ?eries on road networks

Publication Type:
Conference Proceeding
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2018, pp. 709 - 724
Issue Date:
Filename Description Size
p709-ouyang.pdfPublished version2.08 MB
Adobe PDF
Full metadata record
© 2018 Association for Computing Machinery. Computing the shortest distance between two vertices is a fundamental problem in road networks. Since a direct search using the Dijkstra's algorithm results in a large search space, researchers resort to indexing-based approaches. State-of-the-art indexing-based solutions can be categorized into hierarchy-based solutions and hopbased solutions. However, the hierarchy-based solutions require a large search space for long-distance queries while the hop-based solutions result in a high computational waste for short-distance queries. To overcome the drawbacks of both solutions, in this paper, we propose a novel hierarchical 2-hop index (H2H-Index) which assigns a label for each vertex and at the same time preserves a hierarchy among all vertices. With the H2H-Index, we design an e?cient query processing algorithm with performance guarantees by visiting part of the labels for the source and destination based on the vertex hierarchy. We also propose an algorithm to construct the H2H-Index based on distance preserved graphs. The algorithm is further optimized by computing the labels based on the partially computed labels of other vertices. We conducted extensive performance studies using large real road networks including the whole USA road network. The experimental results demonstrate that our approach can achieve a speedup of an order of magnitude in query processing compared to the state-of-the-art while consuming comparable indexing time and index size.
Please use this identifier to cite or link to this item: