Efficient Database Techniques for Reverse k-Nearest Neighbor Search

• Applicant: Professor Dr. Peer Kröger
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2011 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 195108173

Final Report Abstract

A reverse k-nearest neighbor (RkNN) query determines, for a given query object, those objects in a database that recognize the query object as one of their k-nearest neighbors (kNN). The result can be interpreted as a set of database objects that are ”influenced” by the query object. Efficient processing of this query is essential in a wide variety of applications such as location-based services, online information systems, etc., and serves as a basic operation in data mining algorithms. Previous query methods are based on estimates of the kNN distances of the individual data objects and usually use very restrictive assumptions regarding the similarity measure or the modeling of the data objects. The kNN distance approximations are used in particular for pruning, i.e. excluding database objects that are not part of the result. This project developed new methods to address some of the limitations of existing methods. In particular, a new multi-stage procedure was presented that uses the concept of intrinsic dimensionality to estimate the kNN distances. A new method was developed that learns the kNN distances using a machine learning method. Another result of the project closes an important gap in automatic query optimization with the development of an initial cost model for RkNN queries. In addition, a new partitioning method for indexing was presented within the project, which is based again on machine learning methods, particularly on clustering. Finally, the theoretical foundations for optimal pruning strategies were developed and formalized.

Publications

• Dimensional testing for reverse k -nearest neighbor search. Proceedings of the VLDB Endowment, 10(7), 769-780.
  Casanova, Guillaume; Englmeier, Elias; Houle, Michael E.; Kröger, Peer; Nett, Michael; Schubert, Erich & Zimek, Arthur
  
• k-Distance Approximation for Memory-Efficient RkNN Retrieval. Lecture Notes in Computer Science (2019), 57-71. Springer International Publishing.
  Berrendorf, Max; Borutta, Felix & Kröger, Peer
  
• Memory-Efficient RkNN Retrieval by Nonlinear k-Distance Approximation. 2020 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), 12(2020, 12), 387-390. IEEE.
  Obermeier, Sandra; Berrendorf, Max & Kroger, Peer
  
• A Cost Model for Reverse Nearest Neighbor Query Processing on R-Trees Using Self Pruning. Lecture Notes in Computer Science (2021), 45-53. Springer International Publishing.
  Borutta, Felix; Kröger, Peer & Renz, Matthias
  
• Towards a Learned Index Structure for Approximate Nearest Neighbor Search Query Processing. Lecture Notes in Computer Science (2021), 95-103. Springer International Publishing.
  Hünemörder, Maximilian; Kröger, Peer & Renz, Matthias
  
• Complete and Sufficient Spatial Domination of Multidimensional Rectangles. Spatial Gems, Volume 1 (2022, 8, 5), 25-32. ACM.
  Emrich, Tobias; Kriegel, Hans-Peter; Züfle, Andreas; Kröger, Peer & Renz, Matthias