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.
