Reverse Nearest Neighbor Queries for Dynamic Databases.
Ioana Stanoi, Divyakant Agrawal, Amr El Abbadi · 2000
In this paper we propose an algorithm for answering reverse nearest neighbor (RNN) queries, a problem formulated only recently. This class of queries is strongly related to that of nearest neighbor (NN) queries, although the two are not necessarily complementary. Unlike nearest neighbor queries, RNN queries find the set of database points that have the query point as the nearest neighbor. There is no other proposal we are aware of, that provides an algorithmic approach to answer RNN queries. The earlier approach for RNN queries ([KM99]) is based on the pre-computation of neighborhood information that is organized in terms of auxiliary data structures. It can be argued that the precomputation of the RNN information for all points in the database can be too restrictive. In the case of dynamic databases, insert and update operations are expensive and can lead to modifications of large parts of the auxiliary data structures. Also, answers to RNN queries for a set of data points depend on t...