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 IER-kNN algorithm, which previously showed the highest FANN search performance, 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 distance between objects is much different from the actual shortest-path distance between them. In contrast, our algorithm proposed in this study can greatly reduce unnecessary accesses to index nodes compared to 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 using the M-tree. We prove that our algorithm does not cause any false drop. As a result of a series of experiments using various real road network datasets, our algorithm always showed a better performance than IER-kNN and was improved by up to 6.92 times.