Detailed Information

Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

A Border Line-Based Pruning Scheme for Shortest Path Computations

Authors
Park, JinKyuMoon, DaejinHwang, Eenjun
Issue Date
30-10월-2010
Publisher
KSII-KOR SOC INTERNET INFORMATION
Keywords
Dijkstra' s algorithm; path-finding; shortest path container; pruning method; minimum bounding rectangle; convex hull; border-line
Citation
KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS, v.4, no.5, pp.939 - 955
Indexed
SCIE
SCOPUS
KCI
OTHER
Journal Title
KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS
Volume
4
Number
5
Start Page
939
End Page
955
URI
https://scholar.korea.ac.kr/handle/2021.sw.korea/115485
DOI
10.3837/tiis.2010.10.014
ISSN
1976-7277
Abstract
With the progress of IT and mobile positioning technologies, various types of location-based services (LBS) have been proposed and implemented. Finding a shortest path between two nodes is one of the most fundamental tasks in many LBS related applications. So far, there have been many research efforts on the shortest path finding problem. For instance, A* algorithm estimates neighboring nodes using a heuristic function and selects minimum cost node as the closest one to the destination. Pruning method, which is known to outperform the A* algorithm, improves its routing performance by avoiding unnecessary exploration in the search space. For pruning, shortest paths for all node pairs in a map need to be pre-computed, from which a shortest path container is generated for each edge. The container for an edge consists of all the destination nodes whose shortest path passes through the edge and possibly some unnecessary nodes. These containers are used during routing to prune unnecessary node visits. However, this method shows poor performance as the number of unnecessary nodes included in the container increases. In this paper, we focus on this problem and propose a new border line-based pruning scheme for path routing which can reduce the number of unnecessary node visits significantly. Through extensive experiments on randomly-generated, various complexity of maps, we empirically find out optimal number of border lines for clipping containers and compare its performance with other methods.
Files in This Item
There are no files associated with this item.
Appears in
Collections
College of Engineering > School of Electrical Engineering > 1. Journal Articles

qrcode

Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher Hwang, Een jun photo

Hwang, Een jun
공과대학 (전기전자공학부)
Read more

Altmetrics

Total Views & Downloads

BROWSE