MGR: Efficiently Processing Maximal Group Reverse k Nearest Neighbors Queries

作者：Meng, Xin; Ma, Guojie^*; Yang, Shiyu; Wang, Liping

来源：IEEE Access, 2022, 10: 78576-78587.

DOI：10.1109/ACCESS.2022.3188396

• Spatial queries
• reverse k nearest neighbors
• facility location

Given a set of facilities and a set of clients, a reverse k nearest neighbors (Rk NN) query returns every client for which the query facility is one of the k-closest facilities. Rk NN query has been studied thoroughly for its importance in various fields such as facility location. In this paper, we propose a brand new variant of RkNN query, namely, maximal group reverse k nearest neighbors (MaxGroupRkNN) query. Given a set of clients, a set of candidate facilities and parameters k and m, MaxGroupRkNN query returns a set of m facilities out of the candidates, such that the total number of RkNNs of the result set is maximized. The MaxGroupRkNN query is important for multi-facility location problem, which aims to maximize the total potential clients of a group of facilities providing the same service such as chain stores, charging stations and logistic centers. A straightforward solution is to enumerate all possible combinations which is obviously time consuming. In order to address this problem, we present an effcient solution namely MGR, which is based on a well-designed pruning technique. The proposed pruning technique is able to filter out the candidates that cannot contribute to the final result and reduce the computation cost dramatically. Moreover, we propose a well-designed optimization technique that can further reduce the computation cost. A detailed theoretical analysis of our methods is provided and the experimental results also confirm that our proposed methods have high efficiency and scalability.

• 单位
  广州大学