Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road Networks
Zhongpu Chen, Bin Yao, Zhi-Jie Wang, Xiaofeng Gao, Shuo Shang, Shuai Ma, Minyi Guo · IEEE Transactions on Knowledge and Data Engineering · 2020
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 generalizesAnnby introducing an extra flexibility parameter$\phi$that ranges in$(0, 1]$. In this article, we focus onFannon road networks, denoted asFann$_\mathcal {R}$, and its keyword-aware variant, denoted asKFann$_\mathcal {R}$. To solve these problems, we propose a series of universal (i.e., suitable for bothmaxandsum) 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 combinesincremental euclidean restriction(IER) and$k$NN. We also propose a specific exact solution tomax-Fann$_\mathcal {R}$and a constant-factor ratio approximate solution tosum-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 multipleFann$_\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.