Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road Networks

Aggregate nearest neighbor (A(NN)) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (F-ANN) problem further generalizes ANN by introducing an extra flexibility parameter phi that ranges in (0, 1]. In this article, we focus on F-ANN on road networks, denoted as F-ANNR,F- and its keyword-aware variant, denoted as KFANNR. To solve these problems, we propose a series of universal (i.e., suitable for both max and sum) algorithms, including a Dijkstra-based algorithm that enumerates P instead of phi vertical bar Q vertical bar-combinations of Q, a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and kNN. We also propose a specific exact solution to max-FANN R and a constant-factor ratio approximate solution to sum-F-ANNR. These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top-k and multiple F-ANNR (resp., KFANNR) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.