MGR: Efficiently Processing Maximal Group Reverse k Nearest Neighbors Queries

Abstract

Given a set of facilities and a set of clients, a reverse $k$ nearest neighbors ( $\text{R}k$ NN) query returns every client for which the query facility is one of the $k$ -closest facilities. $\text{R}k$ 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 $\text{R}k$ NN query, namely, maximal group reverse $k$ nearest neighbors (MaxGroupR $k$ NN) query. Given a set of clients, a set of candidate facilities and parameters $k$ and $m$ , MaxGroupR $k$ NN query returns a set of $m$ facilities out of the candidates, such that the total number of $\text{R}k$ NNs of the result set is maximized. The MaxGroupR $k$ NN 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 efficient 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.

Keywords

• Spatial queries
• k nearest neighbors%22%2C%22default_operator%22%3A%22AND%22%7D%7D%7D"> reverse <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic> nearest neighbors
• facility location