
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Incremental SingleSource MultiTarget A* Algorithm for LBS Based on Road Network Distance
Htoo HTOO Yutaka OHSAWA Noboru SONEHARA Masao SAKAUCHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.5
pp.10431052 Publication Date: 2013/05/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.1043
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management) Category: Spatial DB Keyword: A* algorithm, road network, POI query, incremental Euclidean restriction,
Full Text: PDF(627.7KB)>>
Summary:
Searching for the shortest paths from a query point to several target points on a road network is an essential operation for several types of queries in locationbased services. This search can be performed using Dijkstra's algorithm. Although the A* algorithm is faster than Dijkstra's algorithm for finding the shortest path from a query point to a target point, the A* algorithm is not so fast to find all paths between each point and the query point when several target points are given. In this case, the search areas on road network overlap for each search, and the total number of operations at each node is increased, especially when the number of query points increases. In the present paper, we propose the singlesource multitarget A* (SSMTA*) algorithm, which is a multitarget version of the A* algorithm. The SSMTA* algorithm guarantees at most one operation for each road network node, and the searched area on road network is smaller than that of Dijkstra's algorithm. Deng et al. proposed the LBC approach with the same objective. However, several heaps are used to manage the search area on the road network and the contents in each heap must always be kept the same in their method. This operation requires much processing time. Since the proposed method uses only one heap, such content synchronization is not necessary. The present paper demonstrates through empirical evaluations that the proposed method outperforms other similar methods.

