Light Materialized Path View for Location Based Services

Abstract

This paper proposes a shortest path search algorithm based on materialized-path-view constructed only on partitioned subgraphs, and its three variations referring different levels of distance materialization. A road network is partitioned into the subgraphs, and the distance materialization is performed only in the subgraphs. Therefore, the amount of pre-computed data is greatly reduced. The shortest path is retrieved by a best-first-search using a priority queue. The difference between three variations of the algorithm is the materialization level of the distance in the subgraphs. The performance of them is evaluated comparing with A* algorithm and HEPV experimentally. Through the results, we show the proposed algorithm outperforms the conventional methods.