Flexible Aggregate Nearest Neighbor Queries in Road Networks
Flexible Aggregate Nearest Neighbor Queries in Road Networks
复制标题
DOI：
10.1109/icde.2018.00074
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Bin Yao;Zhongpu Chen;Xiaofeng Gao;Shuo Shang;Shuai Ma;M. Guo
中科院分区：
文献类型：
--
作者：
Bin Yao;Zhongpu Chen;Xiaofeng Gao;Shuo Shang;Shuai Ma;M. Guo
聚集最近邻(ANN)查询在欧几里德空间和道路网络中都有研究。灵活聚集最近邻(FANN)问题通过引入额外的灵活性进一步推广了ANN。在给定一组数据点P、一组查询点Q和一个用户定义的灵活性参数ϕ(取值范围在(0，1))的情况下，FA N N查询从P返回最佳候选者，它最小化到Q中任何ϕ|Q|对象的聚集(通常是最大或和)距离。本文针对道路网络中的问题，提出了一系列通用的(即，同时适用于最大和和)算法来回答道路网络中的最大和和查询，包括基于Dijkstra的枚举P的算法，一种从近到远处理数据点的基于队列的方法，以及结合增量欧几里得约束(IER)和KNN的框架。我们还给出了max-FANNR的具体精确解和SUM-FANNR的具体近似解，它们可以在保证恒定因子近似的情况下返回接近最优的结果。这些具体的算法易于实现，在某些场景下可以达到优异的性能。此外，我们进一步将FANNR扩展到k-FANNR，并成功地将所提出的大多数算法用于回答k-FANNR查询。我们在真实的道路网络上对所提出的算法进行了全面的实验评估，以证明其优越的效率和高质量。
Aggregate nearest neighbor (ANN) query has been studied in both the Euclidean space and road networks. The flexible aggregate nearest neighbor (FANN) problem further generalizes ANN by introducing an extra flexibility. Given a set of data points P, a set of query points Q, and a user-defined flexibility parameter ϕ that ranges in (0, 1], an FA N N query returns the best candidate from P, which minimizes the aggregate (usually max or sum) distance to any ϕ |Q| objects in Q. In this paper, we focus on the problem in road networks (denoted as FANNR), and present a series of universal (i.e., suitable for both max and sum) algorithms to answer FANNR queries in road networks, including a Dijkstra-based algorithm enumerating P, 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-FANNR and a specific approximate solution to sum-FANNR which can return a near-optimal result with a guaranteed constant-factor approximation. These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend the FANNR to k-FANNR, and successfully adapt most of the proposed algorithms to answer k-FANNR queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real road networks to demonstrate their superior efficiency and high quality.