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

Aggregate nearest neighbor (
Ann
) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (
Fann
) problem further generalizes
Ann
by introducing an extra flexibility parameter
$\phi$
that ranges in
$(0, 1]$
. In this article, we focus on
Fann
on road networks, denoted as
Fann
$_\mathcal {R}$
, and its keyword-aware variant, denoted as
KFann
$_\mathcal {R}$
. 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 |Q|$
-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
$k$
NN. We also propose a specific exact solution to
max
-
Fann
$_\mathcal {R}$
and a constant-factor ratio approximate solution to
sum
-
Fann
$_\mathcal {R}$
. 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
Fann
$_\mathcal {R}$
(resp.,
KFann
$_\mathcal {R}$
) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.