Reverse k-nearest neighbor search in dynamic and general metric databases

ABSTRACT

In this paper, we propose an original solution for the general reverse k-nearest neighbor (RkNN) search problem. Compared to the limitations of existing methods for the RkNN search, our approach works on top of any hierarchically organized tree-like index structure and, thus, is applicable to any type of data as long as a metric distance function is defined on the data objects. We will exemplarily show how our approach works on top of the most prevalent index structures for Euclidean and metric data, the R-Tree and the M-Tree, respectively. Our solution is applicable for arbitrary values of k and can also be applied in dynamic environments where updates of the database frequently occur. Although being the most general solution for the RkNN problem, our solution outperforms existing methods in terms of query execution times because it exploits different strategies for pruning false drops and identifying true hits as soon as possible.

REFERENCES

• 1: Elke Achtert , Christian Böhm , Peer Kröger , Peter Kunath , Alexey Pryakhin , Matthias Renz, Approximate reverse k-nearest neighbor queries in general metric spaces, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183731]
• 2: 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]
• 3: E. Achtert, C. Böhm, P. Kröger, P. Kunath, A. Pryakhin, and M. Renz. Efficient reverse k-nearest neighbor estimation. In Proc. BTW, 2007.
• 4: 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
• 5: 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
• 6: 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
• 7: 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
• 8: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 9: Dimitris Papadias , Panos Kalnis , Jun Zhang , Yufei Tao, Efficient OLAP Operations in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.443-459, July 12-15, 2001
• 10: 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
• 11: 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]
• 12: I. Stanoi, D. Agrawal, and A. E. Abbadi. Reverse nearest neighbor queries for dynamic databases. In Proc. DMKD, 2000.
• 13: 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
• 14: 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]
• 15: 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