In spatial database and road network applications, the search for the nearest neighbor (NN) from a given query object q is the most fundamental and important problem. Aggregate nearest neighbor
(ANN) search is an extension of the NN search with a set of query objects Q = {q_0, ..., q_(M-1) }and finds the object p* that minimizes g{d(p*, q_i), q_i ∈ Q}, where g (max or sum) is an aggregate function and d() is a distance function between two objects. Flexible aggregate nearest neighbor (FANN) search is an extension of the ANN search with the introduction of a flexibility factor ϕ (0 < ϕ ≤ 1) and finds the object p* and the set of query objects Q*_ϕ that minimize g{d(p*,q_i), q_i ∈ Q*_ϕ }, where Q*_ϕ can be any subset of Q of size ϕ|Q|.
This study proposes two efficient flexible aggregate nearest neighbor (FANN) search algorithms in road networks. The state-of-the-art FANN search algorithm in road networks, which is known as IER-kNN, used the Euclidean distance based on the two-dimensional coordinates of objects when choosing an R-tree node that most potentially contains p*. However, since the Euclidean distance is significantly different from the actual shortest-path distance between objects, IER-kNN looks up many unnecessary nodes, thereby incurring many calculations of ‘expensive’ shortest-path distances and eventually performance degradation.
First, we propose an efficient α-probabilistic FANN search algorithm in road networks. The proposed algorithm transforms road network objects into μ-dimensional Euclidean space objects while preserving the distances between them as much as possible using landmark multidimensional scaling (LMDS). Since the Euclidean distance after LMDS transformation is very close to the shortest-path distance, the lookup of unnecessary R-tree nodes and the calculation of expensive shortest-path distances are reduced significantly, thereby greatly improving the search performance. As a result of performance comparison experiments conducted for various real road networks and parameters, the proposed algorithm always achieved higher performance than the IER-kNN; the performance (execution time) of the proposed algorithm was improved by up to 10.87 times without loss of accuracy.
Secondly, we propose an efficient exact FANN search algorithm in road networks using the M-tree. This algorithm can greatly reduce unnecessary accesses to index nodes compared with IER-kNN since the M-tree is constructed based on the actual shortest-path distances between objects. To the best of our knowledge, our algorithm is the first exact FANN algorithm that uses the M-tree. We prove that our algorithm does not cause any false drop. In conducting a series of experiments using various real road network datasets, our algorithm consistently outperformed IER-kNN by up to 6.92 times.
공간 데이터베이스와 도로 네트워크 응용에서 하나의 질의 객체 q에 대한 최근접 이웃(Nearest neighbor, NN) 검색은 가장 기본적이고 중요한 문제이다. 집계값 최근접 이웃 (Aggregate nearest neighbor, ANN) 검색은 기존의 NN 문제를 복수 개의 질의 객체 Q = {q_0, ..., q_(M-1)}에 대하여 확장한 것으로, g{d(p*,q_i), q_i ∈ Q}를 최소화하는 객체 p*를 검색한다. 여기에서 g = max, sum은 집계값 함수(aggregate function)이며, d()는 두 객체 간의 거리 함수이다. 유연한 집계값 최근접 이웃(Flexible aggregate nearest neighbor, FANN) 검색은 ANN 문제에 유연성 인자(flexibility factor) ϕ (0 ≤ ϕ ≤ 1)를 도입하여 확장한 것으로, g{d(p*,q_i), q_i ∈ Q*_ϕ }를 최소화하는 객체 p* 및 질의 객체 집합 Q*_ϕ를 검색한다. 여기에서 Q*_ϕ는 크기 ϕM인 Q의 임의의 부분집합이다.
본 연구에서는 도로 네트워크에서의 효율적인 FANN 검색 알고리즘을 제안한다. 기존에 가장 높은 FANN 검색 성능을 보인 IER-kNN 알고리즘은 도로 네트워크 객체들의 유클리드 좌표에 기반한 R-트리 인덱스를 이용하여 유연한 집계값 최근접 이웃 후보를 포함하는 노드를 선택한다. 하지만, 객체 간의 유클리드거리는 실제 최단경로 거리와 매우 다르므로, IER-kNN 은 필요 없는 노드에 대한 액세스가 많이 발생하여 ’비싼’ 최단경로 거리 계산이 많이 발생하고 결국 성능 저하가 발생한다.
제안된 첫 번째 알고리즘은 α-확률적인 유연한 집계값 최근접 이웃 검색 알고리즘으로, 랜드마크 다차원 스케일링(landmark multidimensional scaling, LMDS) 변환을 이용하여 도로 네트워크 객체들을 그들 간의 최단경로 거리가 유지되도록 μ-차원 유클리드 공간 객체로 변환한다. 검색 대상인 R-트리 노드를 선정함에 있어서 최단경로 거리에 가까운 거리를 사용하므로, 불필요한 노드의 검색 및 비싼 최단경로 거리의 계산이 크게 줄어들고, 따라서 검색 성능이 대폭 향상된다. 다양한 실제 도로 네트워크 데이터셋과 파라미터에 대하여 성능 비교 실험을 수행한 결과, 제안된 알고리즘은 항상 기존의 알고리즘보다 높은 성능을 보였고, 정확도의 손실 없이 최대 10.87배까지 성능이 향상되었다.
두 번째 알고리즘은 M-트리를 이용한 효율적이고 정확한 k-FANN 검색 알고리즘이다. M-트리는 객체 간의 실제 최단경로 거리에 기반하여 구축됨으로써, 제안된 알고리즘은 IER-kNN에 비하여 필요 없는 인덱스 노드의 액세스를 크게 줄일 수 있다. 우리가 아는 한에서, 제안된 알고리즘은 M-트리를 이용한 최초의 정확한 FANN 알고리즘이며, 거짓 음성(false drop)을 발생시키지 않는다. 다양한 실제 도로 네트워크 데이터셋을 이용한 일련의 실험 결과, 제안된 알고리즘은 기존의 알고리즘보다 항상 높은 성능을 보였고, 최대 6.92배까지 향상되었다.
