P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators

The most efficient known approach for shortest distance querying on road networks is via a tree decomposition based 2-hop labeling index. A major challenge here is how to reduce the query time by reducing the label size. To this end, we propose P2H with the novel ideas of projected vertex separators and optimized selection of vertex separators. We also introduce mechanisms for index maintenance for edge weight updating. Our experiments on multiple real road networks show that P2H can greatly reduce the effective label sizes and query time over existing algorithms. For larger datasets, P2H is around twice as efficient as the best known algorithm.