도로 네트워크에서 $A^*$ 알고리즘을 이용한 k-최근접 이웃 객체에 대한 효과적인 경로 탐색 방법 Efficient Path Finding Based on the $A^*$ algorithm for Processing k-Nearest Neighbor Queries in Road Network Databases원문보기
본 논문에서는 기존 k-최근접 객체 검색의 효율성을 개선하고 도로 네트워크에의 응용을 용이하게 하기 위하여 질의 점으로부터 k개의 정적 객체까지의 경로를 효과적으로 탐색할 수 있는 방법을 제안한다. 제안한 방법은 우선, k-최근접 이웃 질의 방법을 이용하여 후보 정적 객체들을 선정한 후 이들 후보 객체들의 위치 정보를 이용하여 최단 경로를 탐색한다. 일대다 경로탐색을 위하여 A* 알고리즘을 개선하여 반복된 일대일 경로탐색에 따르는 중복된 노드 스캔을 제거한다. 또, 계산된 결과를 이용하여 질의점으로부터 네트워크 거리상으로 가까운 k개의 정적 객체들의 위치를 재정렬하여 반환한다. 성능평가 실험 결과, 제안한 방법은 기존 방법들인 INE, post-Dijkstra, 그리고 $na{\ddot{i}}ve$ method에 비해 정확성이 100%로 매우 높게 나타났으며, 노드 탐색 시간은 $1.3{\sim}3.0$배로 향상된 성능을 보였다.
본 논문에서는 기존 k-최근접 객체 검색의 효율성을 개선하고 도로 네트워크에의 응용을 용이하게 하기 위하여 질의 점으로부터 k개의 정적 객체까지의 경로를 효과적으로 탐색할 수 있는 방법을 제안한다. 제안한 방법은 우선, k-최근접 이웃 질의 방법을 이용하여 후보 정적 객체들을 선정한 후 이들 후보 객체들의 위치 정보를 이용하여 최단 경로를 탐색한다. 일대다 경로탐색을 위하여 A* 알고리즘을 개선하여 반복된 일대일 경로탐색에 따르는 중복된 노드 스캔을 제거한다. 또, 계산된 결과를 이용하여 질의점으로부터 네트워크 거리상으로 가까운 k개의 정적 객체들의 위치를 재정렬하여 반환한다. 성능평가 실험 결과, 제안한 방법은 기존 방법들인 INE, post-Dijkstra, 그리고 $na{\ddot{i}}ve$ method에 비해 정확성이 100%로 매우 높게 나타났으며, 노드 탐색 시간은 $1.3{\sim}3.0$배로 향상된 성능을 보였다.
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 findin...
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 $1.3{\sim}3.0$ times of k-nearest neighbor searches, compared with INE, post-Dijkstra, and $na{\ddot{i}}ve$ method.
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 $1.3{\sim}3.0$ times of k-nearest neighbor searches, compared with INE, post-Dijkstra, and $na{\ddot{i}}ve$ method.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 VN3 방법과 근사 인덱싱 방법과 같은 k-NN 질의 처리 방법을 이용하여 추출된 정적 객체들의 위치를 파악하고, 정확한 fc-NN 객체를 선별하기 위해 최적 경로를 효과적으로 탐색하는 방법을 제안한다.
본 논문에서는 k개의 객체들을 k-NN 질의 처리 방법으로 빠르게 추출하고, 이들 정적 객체들의 경로 및 거리를 검색하는 방법을 제안한다. 질의점으로부터 k- NN 정적 객체를 검색하기 위해서는 최근접 정적 객체의 정형적인 정의가 필요하다.
본 논문에서는 질의점으로부터 fc-NN 정적 객체를 검색한 후, 이들에 대한 효율적인 최단 네트워크 거리 및 경로를 계산하는 방법을 제안하고 성능을 평가한다. 이러한 방법은 먼저, 네트워크 거리를 기준으로 가까운 左개의 정적 객체를 찾는 단계부터 시작하며, VN3와 근사 인덱싱 방법과 같은 fc-NN 질의 처리 방법을 이용하여 정적 객체를 일차적으로 추출한다.
하지만, 이들 방법은 모든 도로 세그먼트를 확장하면서 정적객체들을 검색하거나, 최단의 경로 및 거리의 계산 없이 정적 객체를 검색하는 문제점을 가지고 있다. 이에 본 논문에서는 k-NN 질의에 대해 최단 경로 탐색을 측정하는 방법을 제시하였다. 우선, fc-NN 질의 처리 방법을 통하여 k개의 정적 객체를 찾고 각 정적 객체까지의 경로를 탐색한다.
효과적인 최적 노드 선별 본 논문에서는 A* 알고리즘의 개선으로 최단 경로를 탐색할 경우에 경유하는 최적의 경로를 효과적으로 선별하기 위한 방법을 제안한다. 제안한 방법은 주어진 두 노드 u와 u를 연결하는 인접 노드 # 중에 #의 비용이 가장 작은 노드를 탐색하는 것으로 불필요한 경로 탐색 비용을 줄이는 방법이다.
가설 설정
정의 2: 도로 네트워크 V7에서 노드는 “와 u이고, u, uEV이다. 도로 세그먼트에서 노드 "는 (u, d)의 시작 노드이고, u는 (u, u)의 끝 정점이라고 할 때, 이들의 네트워크 거리는 cfefN(u, u)이고, 유클리드 거리는 distE(u, v) 라 정의한다.
제안 방법
이전 과정에서 찾은 *개의 객체에 대한 경로를 계산하는데, 기존 A* 알고리즘을 개선하여 질의점으로부터 k개의 정적 객체에 대한 각 경로를 통합적으로 탐색하는 방법을 제안한다. 마지막으로, 실제 구한 경로와 거리 정보를 이용하여 검색된 /c개의 정적 객체를 질의점으로부터 가까운 순서로 정렬하여 반환한다.
프레임워크를 나타낸다. 먼저, 인덱스 부분은 fc-NN 질의 처리 방법을 이용하여 左개의 정적 객체들의 위치를 검색한다. 여기서, fc-NN 질의 처리 방법은 검색 과정에서 객체간 거리 오차가 발생한다.
이에 본 논문에서는 k-NN 질의에 대해 최단 경로 탐색을 측정하는 방법을 제시하였다. 우선, fc-NN 질의 처리 방법을 통하여 k개의 정적 객체를 찾고 각 정적 객체까지의 경로를 탐색한다. 탐색하는 과정에서 A* 알고리즘을 개선하여 적용하기 때문에 효과적으로 질의점으로부터 다수의 정적 객체까지의 경로를 탐색할 수 있다.
Restriction) 방법을 제안하였다(3). 이와 더불어 모든 도로 세그먼트를 점진적으로 확장하면서 정적 객체를 검색하는 INE(Incremental network expansion) 방법을 제안하였다. 이들 방법은 저장 비용이 작다는 장점에 비해, 질의 처리시 여러 번의 시행착오가 수반되거나.
이러한 방법은 먼저, 네트워크 거리를 기준으로 가까운 左개의 정적 객체를 찾는 단계부터 시작하며, VN3와 근사 인덱싱 방법과 같은 fc-NN 질의 처리 방법을 이용하여 정적 객체를 일차적으로 추출한다. 이전 과정에서 찾은 *개의 객체에 대한 경로를 계산하는데, 기존 A* 알고리즘을 개선하여 질의점으로부터 k개의 정적 객체에 대한 각 경로를 통합적으로 탐색하는 방법을 제안한다. 마지막으로, 실제 구한 경로와 거리 정보를 이용하여 검색된 /c개의 정적 객체를 질의점으로부터 가까운 순서로 정렬하여 반환한다.
Road Network) 를 사용한다[2]. 정적 객체의 수는 각각의 도로 세그먼트 수 비율을 0.5%, 1%, 5%로 변화시켜 생성하였으며, 객체들의 위치를 임의로 분포 시켜 설정하였다. 성능 평가를 위하여 다음과 같은 방법으로 수행하였다:
제안한 방법은 주어진 두 노드 u와 u를 연결하는 인접 노드 # 중에 #의 비용이 가장 작은 노드를 탐색하는 것으로 불필요한 경로 탐색 비용을 줄이는 방법이다. 본 논문에서는 이러한 노드를 경유하는 최적 경로를 다음과 같이 정의한다.
있다. 질의 점 q로부터 정적 객체 이까지의 경로를 탐색하기 위해, 먼저 질의점 q로부터 노드 花4, 沾를 탐색하고, 공식 (2)를 이용하여 distNE(、q, n4, nl)와 distNE(q, r&, nY) .를 계산한다.
대상 데이터
본 실험 수행을 위해, 실험 환경은 실제 도로 네트워크 데이터로 ORN (Oldenburg Road Network)와 CRN (California Road Network) 를 사용한다[2]. 정적 객체의 수는 각각의 도로 세그먼트 수 비율을 0.
이론/모형
최단 경로 계산 질의점으로부터 임의의 정적 객체까지의 최단 경로를 탐색하기 위해 A* 알고리즘을 개선하여 이용한다. 다음 정리 1은 A* 알고리즘을 개선한 최단 경로식을 다음과 같이 정리한다.
성능/효과
이는 앞서의 실험의 결과에서와 같이 Our Method가 모든 경우에 있어서 비교적 좋은 성능을 보이기 때문이다. 결국, 제안한 Our Method는 k의 수를 변경하는 경우나, 도로세그먼트의 비율에 따른 경우에 있어서도 기존 방법에 비해 성능을 크게 향상시킨다고 말할 수 있다.
5%, 1%, 5%로 변경하면서 성능을 측정한 결과이다. 그림을 보면, 모든 경우에 있어서 제안한 Our Method가 다른 방법에 비해 성능을 향상시켰음을 알 수 있다. 이는 앞서의 실험의 결과에서와 같이 Our Method가 모든 경우에 있어서 비교적 좋은 성능을 보이기 때문이다.
25로 변경하여 수행 시간을 측정한 결과이다. 그림을 보면, 제안한 Our Method는 기존 방법들에 비해 성능을 향상시킨 것으로 나타났다. 그러나, Our Method는 pseudo-k의 비율이 2% 이상인 경우, 성능이 post-Dijkstra 보다 저하된 것으로 나타났다.
탐색하는 과정에서 A* 알고리즘을 개선하여 적용하기 때문에 효과적으로 질의점으로부터 다수의 정적 객체까지의 경로를 탐색할 수 있다. 실험을 통하여 본 논문에서 제안하는 방법이 다른 방법에 비해 우수함을 보였다.
참고문헌 (8)
Wu, S. and Wu, K., 'Effective Location-Based Services with Dynamic Data Management in Mobile Environments,' Wireless Networks, vol.12, no.3, pp.369-381, 2006
Lee, S.-C., Kim, S.-W., Lee, J. and Yoo, J. S., 'Approximate Indexing in Road Network Databases,' ACM Int'l Symp. on Applied Computing, ACM SAC, pp.1568-1572, Mar. 2009
Papadias, D., Zhang, J. MarnouIis, N., and Tao, Y, 'Query Processing in Spatial Network Databases,' In Proc. Int'l Conf. on Very Large Data Bases, VLDB, pp.802-813, Sept. 2003
Kolahdouzan, M. and Shahabi, C., 'Voronoi- Based K-Nearest Neighbor Search for Spatial Network Databases,' In Proc. Int'l Conf on Very Large Data Bases, VLDB, pp.840-851, Sept. 2004
Faloutsos, C. and Lin, K., 'Fastlap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets,' In Proc. ACM Int'l Conf. on Management of Data, ACM SIGMOD, pp.163-174, May 1995.
Hart, P, E, Nilsson, N. J., and Raphael, B., 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs,' IEEE Trans. on Systems Science and Cybernetics, vol, SSC-4, no. 2, pp.100-107, July 1968.
Beckmann, N., Kriegel, H., Schneider, R., and Seeger, B., 'The R $\ast$ -tree: An Efficient and Robust Access Method for Points and Rectangles,' In Proc. the ACM Int'l Carr[. on Management of Data, ACM SIGMOD, pp.322-331, May 1990
※ AI-Helper는 부적절한 답변을 할 수 있습니다.