Incremental Single-Source Multi-Target A* Algorithm for LBS Based on Road Network Distance

Htoo HTOO; Yutaka OHSAWA; Noboru SONEHARA; Masao SAKAUCHI

doi:10.1587/transinf.E96.D.1043

Incremental Single-Source Multi-Target A* Algorithm for LBS Based on Road Network Distance

Htoo HTOO, Yutaka OHSAWA, Noboru SONEHARA, Masao SAKAUCHI

Full Text Views

0

Share
Cite this

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 location-based 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 single-source multi-target A* (SSMTA*) algorithm, which is a multi-target 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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.5 pp.1043-1052

Publication Date: 2013/05/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.1043

Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)

Category: Spatial DB

Cite this

Copy

Htoo HTOO, Yutaka OHSAWA, Noboru SONEHARA, Masao SAKAUCHI, "Incremental Single-Source Multi-Target A* Algorithm for LBS Based on Road Network Distance" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 5, pp. 1043-1052, May 2013, doi: 10.1587/transinf.E96.D.1043.
Abstract: 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 location-based 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 single-source multi-target A* (SSMTA*) algorithm, which is a multi-target 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1043/_p

Copy

@ARTICLE{e96-d_5_1043,
author={Htoo HTOO, Yutaka OHSAWA, Noboru SONEHARA, Masao SAKAUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Incremental Single-Source Multi-Target A* Algorithm for LBS Based on Road Network Distance},
year={2013},
volume={E96-D},
number={5},
pages={1043-1052},
abstract={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 location-based 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 single-source multi-target A* (SSMTA*) algorithm, which is a multi-target 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.},
keywords={},
doi={10.1587/transinf.E96.D.1043},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - Incremental Single-Source Multi-Target A* Algorithm for LBS Based on Road Network Distance
T2 - IEICE TRANSACTIONS on Information
SP - 1043
EP - 1052
AU - Htoo HTOO
AU - Yutaka OHSAWA
AU - Noboru SONEHARA
AU - Masao SAKAUCHI
PY - 2013
DO - 10.1587/transinf.E96.D.1043
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2013
AB - 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 location-based 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 single-source multi-target A* (SSMTA*) algorithm, which is a multi-target 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.
ER -