상세정보
학술지
Efficient exact k-flexible aggregate nearest neighbor search in road networks using the M-tree
- 저자
- 정문영, 현순주, 노웅기
- 발행일
- 202209
- 출처
- Journal of Supercomputing, v.78 no.14, pp.16286-16302
- ISSN
- 0920-8542
- 출판사
- Springer
- 협약과제
- 21HS2100, 클라우드 엣지 기반 도시교통 브레인 핵심기술 개발, 정문영
- 초록
- This study proposes an efficient exact k-flexible aggregate nearest neighbor (k-FANN) search algorithm in road networks using the M-tree. The state-of-the-art IER-kNN algorithm used the R-tree and pruned off unnecessary nodes based on the Euclidean coordinates of objects in road networks. However, IER-kNN made many unnecessary accesses to index nodes since the Euclidean distances between objects are significantly different from the actual shortest-path distances between them. In contrast, our algorithm proposed in this study 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.
- KSP 제안 키워드
- Aggregate nearest neighbor, KNN algorithm, R-Tree, Road networks, Search Algorithm(GSA), euclidean distance, nearest neighbor(NN), nearest neighbor search, shortest path, state-of-The-Art