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
Abstract
Aggregate nearest neighbor ( <small>Ann</small> ) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor ( <small>Fann</small> ) problem further generalizes <small>Ann</small> by introducing an extra flexibility parameter <inline-formula><tex-math notation="LaTeX">$\phi$</tex-math></inline-formula> that ranges in <inline-formula><tex-math notation="LaTeX">$(0, 1]$</tex-math></inline-formula> . In this article, we focus on <small>Fann</small> on road networks, denoted as <small>Fann</small> <inline-formula><tex-math notation="LaTeX">$_\mathcal {R}$</tex-math></inline-formula> , and its keyword-aware variant, denoted as <small>KFann</small> <inline-formula><tex-math notation="LaTeX">$_\mathcal {R}$</tex-math></inline-formula> . To solve these problems, we propose a series of universal (i.e., suitable for both <i>max</i> and <i>sum</i> ) algorithms, including a Dijkstra-based algorithm that enumerates <inline-formula><tex-math notation="LaTeX">$P$</tex-math></inline-formula> instead of <inline-formula><tex-math notation="LaTeX">$\phi |Q|$</tex-math></inline-formula> -combinations of <inline-formula><tex-math notation="LaTeX">$Q$</tex-math></inline-formula> , a queue-based approach that processes data points from-near-to-far, and a framework that combines <i>incremental euclidean restriction</i> (IER) and <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> NN. We also propose a specific exact solution to <i>max</i> - <small>Fann</small> <inline-formula><tex-math notation="LaTeX">$_\mathcal {R}$</tex-math></inline-formula> and a constant-factor ratio approximate solution to <i>sum</i> - <small>Fann</small> <inline-formula><tex-math notation="LaTeX">$_\mathcal {R}$</tex-math></inline-formula> . These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top- <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> and multiple <small>Fann</small> <inline-formula><tex-math notation="LaTeX">$_\mathcal {R}$</tex-math></inline-formula> (resp., <small>KFann</small> <inline-formula><tex-math notation="LaTeX">$_\mathcal {R}$</tex-math></inline-formula> ) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.