P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators
Zitong Chen, Ada Wai-Chee Fu, Minhao Jiang, Eric Lo, Pengfei Zhang
Abstract
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.
Topics & Concepts
Vertex (graph theory)Computer scienceDecompositionEnhanced Data Rates for GSM EvolutionData miningDistributed computingTheoretical computer scienceArtificial intelligenceGraphBiologyEcologyData Management and AlgorithmsAdvanced Database Systems and QueriesAutomated Road and Building Extraction