Efficient Exact k-Flexible Aggregate Nearest Neighbor Search in Road Networks Using the M-tree

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, I...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-09
Main Authors: Chung, Moonyoung, Hyun, Soon J, Woong-Kee Loh
Format: Article
Language:English
Subjects:
Algorithms
Euclidean geometry
Networks
Nodes
Roads
Search algorithms
Shortest-path problems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422