Efficient algorithms for reverse proximity query problems
Yokesh Kumar, Ravi Janardan, Prosenjit Gupta · 2008
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.