A Border Line-Based Pruning Scheme for Shortest Path Computations
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Park, JinKyu | - |
dc.contributor.author | Moon, Daejin | - |
dc.contributor.author | Hwang, Eenjun | - |
dc.date.accessioned | 2021-09-07T23:25:29Z | - |
dc.date.available | 2021-09-07T23:25:29Z | - |
dc.date.created | 2021-06-14 | - |
dc.date.issued | 2010-10-30 | - |
dc.identifier.issn | 1976-7277 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/115485 | - |
dc.description.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. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | KSII-KOR SOC INTERNET INFORMATION | - |
dc.subject | MODEL | - |
dc.title | A Border Line-Based Pruning Scheme for Shortest Path Computations | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Hwang, Eenjun | - |
dc.identifier.doi | 10.3837/tiis.2010.10.014 | - |
dc.identifier.scopusid | 2-s2.0-78449240337 | - |
dc.identifier.wosid | 000284007800014 | - |
dc.identifier.bibliographicCitation | KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS, v.4, no.5, pp.939 - 955 | - |
dc.relation.isPartOf | KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS | - |
dc.citation.title | KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS | - |
dc.citation.volume | 4 | - |
dc.citation.number | 5 | - |
dc.citation.startPage | 939 | - |
dc.citation.endPage | 955 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.identifier.kciid | ART001497171 | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.description.journalRegisteredClass | kci | - |
dc.description.journalRegisteredClass | other | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Telecommunications | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Information Systems | - |
dc.relation.journalWebOfScienceCategory | Telecommunications | - |
dc.subject.keywordPlus | MODEL | - |
dc.subject.keywordAuthor | Dijkstra&apos | - |
dc.subject.keywordAuthor | s algorithm | - |
dc.subject.keywordAuthor | path-finding | - |
dc.subject.keywordAuthor | shortest path container | - |
dc.subject.keywordAuthor | pruning method | - |
dc.subject.keywordAuthor | minimum bounding rectangle | - |
dc.subject.keywordAuthor | convex hull | - |
dc.subject.keywordAuthor | border-line | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.