High dimensional reverse nearest neighbor queries

ABSTRACT

Reverse Nearest Neighbor (RNN) queries are of particular interest in a wide range of applications such as decision support systems, profile based marketing, data streaming, document databases, and bioinformatics. The earlier approaches to solve this problem mostly deal with two dimensional data. However most of the above applications inherently involve high dimensions and high dimensional RNN problem is still unexplored. In this paper, we propose an approximate solution to answer RNN queries in high dimensions. Our approach is based on the strong correlation in practice between k-NN and RNN. It works in two phases. In the first phase the k-NN of a query point is found and in the next phase they are further analyzed using a novel type of query Boolean Range Query (BRQ). Experimental results show that BRQ is much more efficient than both NN and range queries, and can be effectively used to answer RNN queries. Performance is further improved by running multiple BRQ simultaneously. The proposed approach can also be used to answer other variants of RNN queries such as RNN of order k, bichromatic RNN, and Matching Query which has many applications of its own. Our technique can efficiently answer NN, RNN, and its variants with approximately same number of I/O as running a NN query.

REFERENCES

• 1: http://gist.cs.berkeley.edu.
• 2: J. V. Anil Maheshwari and N. Zeh. On reverse nearest neighbor queries. In Proceedings of the 14th Canadian Conference on Computational Geometry, University of Lethbridge, Alberta, Canada, Aug 2002.
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Efficiently Supporting Multiple Similarity Queries for Mining in Metric Databases, Proceedings of the 16th International Conference on Data Engineering, p.256, February 28-March 03, 2000
• 5: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Proceedings of the 15th International Conference on Data Engineering, p.440, March 23-26, 1999
• 6: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 7: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 8: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 9: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 10: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 11: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
• 12: 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
• 13: F. Korn, S. Muthukrishnan, and D. Srivastava. Reverse nearest neighbor aggregates over data streams. In Proceedings of the Int. Conf. on Very Large Data Bases, Hong Kong, China, Aug. 2002.
• 14: Christian A. Lang , Ambuj K. Singh, Accelerating High-Dimensional Nearest Neighbor Queries, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.109, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029711]
• 15: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 16: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 17: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 18: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 19: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 20: I. Stanoi, D. Agrawal, and A. El Abbadi. Reverse nearest neighbor queries for dynamic databases. In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD 2000) in conjunction with SIGMOD 2000, Dallas, USA, 2000.
• 21: Ioana Stanoi , Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Discovery of Influence Sets in Frequently Updated Databases, Proceedings of the 27th International Conference on Very Large Data Bases, p.99-108, September 11-14, 2001
• 22: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 23: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
boolean range, nearest neighbor, query, reverse nearest neighbor