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

A Reverse k-nearest neighbor (RkNN) query returns all data objects that have the given query object in the set of their kNNs, where k is a query parameter. RkNN queries identify the "influence" of a query object on the whole data set which is an important information in many applications, including e.g. location-based services, recommendation systems, etc. RkNN queries serve also as basic operations in several data mining algorithms and are related to the concept of hubness in Machine Learning. Current techniques for efficiently supporting RkNN queries are mostly limited to the Euclidean distance as similarity measure and/or to simple computing environments. In this project, we aim at overcoming these limitations. We will develop techniques for processing RkNN queries using complex distance functions in Euclidean data spaces, metric spaces, and we even non-metric spaces. In addition, we will explore new methods for RkNN queries under constraints to the computing environment, such as in sensor networks (where energy consumption of the devices need to be optimized rather than I/O costs), in interactive services (where anytime/progressive query processing is required), as well as in client/server scenarios (where the constraint is on the authentication of the results).

• DFG Programme: Research Grants