Answering range-based reverse kNN and why-not reverse kNN queries

摘要

Given a dataset D and a point q, a reverse nearest neighbor (RNN) query retrieves all the points p ∈ D that have q as their nearest neighbor. Although the RNN problem was first proposed in [1], it still has received considerable attention due to its importance in several applications involving decision support, resource allocation, profile-based marketing, etc. Despite significant progress on this problem, there is a research gap in finding RNNs not just for an object, but for a given range, which is a natural extension of the problem. In this paper, we proposed a range-based reverse k nearest neighbors (RRkNN) query, it retrieves all the points p ∈ D that have any position in the query range R as their kNN. It is useful in our daily life. In this paper, We assume that the shape of range R is rectangle.