Efficient algorithms for reverse proximity query problems

Determining the influence of an object on other objects in a database, based on proximity, is important in many applications. Abstractly, we wish to pre-process a set, P, of points in d-space so that the points of P that are assigned a new query point q as a Euclidean nearest neighbor can be reported quickly. These are the reverse nearest neighbors of q and are the ones most influenced by q. This generalizes to bichromatic reverse nearest neighbors, in which two sets, clients and servers, are given, where each client is influenced by some server, and of interest are the clients that are assigned a new server q as a nearest neighbor. Both extend to higher orders k > 1, where we seek the points that are assigned q as one of their k nearest neighbors, indicating varying degrees of influence. Each version also has a counterpart where "nearest" is replaced by "farthest", signifying low influence. We present a general approach that solves such reverse proximity query problems in an efficient and unified way, in any dimension, using well-known geometric transformations. We also give simple approximation algorithms in two and three dimensions (the primary domain of GIS applications) that report points that are "close to"being the desired true reverse proximity neighbors, as determined by a user-specified error parameter. This is based on approximating the proximity loci of the points by suitable convex polytopes that are amenable to simple and efficient querying. Theoretical analyses show that our solutions are fast and provably accurate, and this is further confirmed by experiments.