TY - JOUR
T1 - Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road Networks
AU - Chen, Zhongpu
AU - Yao, Bin
AU - Wang, Zhi-Jie
AU - Gao, Xiaofeng
AU - Shang, Shuo
AU - Ma, Shuai
AU - Guo, Minyi
N1 - KAUST Repository Item: Exported on 2021-11-25
Acknowledgements: This work (Bin Yao) was supported by the NSFC (U1636210)
PY - 2021/11/5
Y1 - 2021/11/5
N2 - 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] (0,1]. In this article, we focus on Fann on road networks, denoted as Fann-\mathcal {R} R, and its keyword-aware variant, denoted as KFann-\mathcal {R} 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 P instead of \phi |Q|φ|Q|-combinations of Q Q, a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and k kNN. We also propose a specific exact solution to max-Fann-\mathcal {R} R and a constant-factor ratio approximate solution to sum-Fann-\mathcal {R} 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 k and multiple Fann-\mathcal {R} R (resp., KFann-\mathcal {R} R) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.
AB - 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] (0,1]. In this article, we focus on Fann on road networks, denoted as Fann-\mathcal {R} R, and its keyword-aware variant, denoted as KFann-\mathcal {R} 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 P instead of \phi |Q|φ|Q|-combinations of Q Q, a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and k kNN. We also propose a specific exact solution to max-Fann-\mathcal {R} R and a constant-factor ratio approximate solution to sum-Fann-\mathcal {R} 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 k and multiple Fann-\mathcal {R} R (resp., KFann-\mathcal {R} R) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.
UR - http://hdl.handle.net/10754/673759
UR - https://ieeexplore.ieee.org/document/9007415/
UR - http://www.scopus.com/inward/record.url?scp=85118933952&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2020.2975998
DO - 10.1109/TKDE.2020.2975998
M3 - Article
SN - 1558-2191
VL - 33
SP - 3701
EP - 3715
JO - IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
JF - IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
IS - 12
ER -