Efficient Path Finding Based on the $A^*$ algorithm for Processing k-Nearest Neighbor Queries in Road Network Databases
Sung-Hyun Shin, Sang‐Chul Lee, Sang‐Wook Kim, Jung-Hoon Lee, Eul-Kyu Im · 2009
This paper proposes an efficient path finding scheme capable of searching the paths to k static objects from a given query point, aiming at both improving the legacy k-nearest neighbor search and making it easily applicable to the road network environment. To the end of improving the speed of finding one-to-many paths, the modified A* obviates the duplicated part of node scans involved in the multiple executions of a one-to-one path finding algorithm. Additionally, the cost to the each object found in this step makes it possible to finalize the k objects according to the network distance from the candidate set as well as to order them by the path cost. Experiment results show that the proposed scheme has the accuracy of around 100% and improves the search speed by times of k-nearest neighbor searches, compared with INE, post-Dijkstra, and method.