Efficient algorithms for reverse proximity query problems

ABSTRACT

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.

REFERENCES

• 1: Elke Achtert , Christian Böhm , Peer Kröger , Peter Kunath , Alexey Pryakhin , Matthias Renz, Efficient reverse k-nearest neighbor search in arbitrary metric spaces, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142531]
• 2: P. Agarwal and J. Erickson. Geometric range searching and its relatives. In J. E. Goodman B. Chazelle and R. Pollack, editors, Adv. in Disc. and Comp. Geom., pages 1--56. AMS Press, 1998.
• 3: A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100260]
• 4: Richard Anderson , Brian Tjaden, The inverse nearest neighbor problem with astrophysical applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.767-768, January 07-09, 2001, Washington, D.C., United States
• 5: Rimantas Benetis , S. Jensen , Gytis Karĉiauskas , Simonas Ŝaltenis, Nearest and reverse nearest neighbor queries for moving objects, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.229-249, September 2006 [doi>10.1007/s00778-005-0166-4]
• 6: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 7: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 8: J. Kang, M. Mokbel, S. Shekhar, T. Xia, and D. Zhang. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors. In Proc. IEEE ICDE Conf., pages 806--815, 2007.
• 9: Flip Korn , S. Muthukrishnan, Influence sets based on reverse nearest neighbor queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.201-212, May 15-18, 2000, Dallas, Texas, United States
• 10: Flip Korn , S. Muthukrishnan , Divesh Srivastava, Reverse nearest neighbor aggregates over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.814-825, August 20-23, 2002, Hong Kong, China
• 11: A. Maheshwari, J. Vahrenhold, and N. Zeh. On reverse nearest neighbor queries. In Proc. Canadian Conf. Comput. Geom., 2002.
• 12: Alexandros Nanopoulos , Yannis Theodoridis , Yannis Manolopoulos, C2P: Clustering based on Closest Pairs, Proceedings of the 27th International Conference on Very Large Data Bases, p.331-340, September 11-14, 2001
• 13: Amit Singh , Hakan Ferhatosmanoglu , Ali Şaman Tosun, High dimensional reverse nearest neighbor queries, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956882]
• 14: I. Stanoi, D. Agrawal, and A. El Abbadi. Reverse nearest neighbor queries for dynamic databases. In SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 44--53, 2000.
• 15: Yufei Tao , Man Lung Yiu , Nikos Mamoulis, Reverse Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.18 n.9, p.1239-1252, September 2006 [doi>10.1109/TKDE.2006.148]
• 16: Yufei Tao , Dimitris Papadias , Xiang Lian, Reverse kNN search in arbitrary dimensionality, Proceedings of the Thirtieth international conference on Very large data bases, p.744-755, August 31-September 03, 2004, Toronto, Canada
• 17: E. Weisstein. Platonic solid. In MathWorld. mathworld.wolfram.com/PlatonicSolid.html.
• 18: Congjun Yang , King-Ip Lin, An Index Structure for Efficient Reverse Nearest Neighbor Queries, Proceedings of the 17th International Conference on Data Engineering, p.485-492, April 02-06, 2001
• 19: Man Lung Yiu , Dimitris Papadias , Nikos Mamoulis , Yufei Tao, Reverse Nearest Neighbors in Large Graphs, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.540-553, April 2006 [doi>10.1109/TKDE.2006.67]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
approximation, geometric proximity problems, query processing, reverse proximity