Efficient Database Techniques for Reverse k-Nearest Neighbor Search

反向k近邻（RkNN）查询返回在其knn集合中具有给定查询对象的所有数据对象，其中k是查询参数。RkNN查询识别查询对象对整个数据集的“影响”，这在许多应用中是一个重要的信息，例如基于位置的服务、推荐系统等。RkNN查询也可以作为一些数据挖掘算法的基本操作，并且与机器学习中的中心概念相关。当前有效支持RkNN查询的技术大多局限于欧几里得距离作为相似性度量和/或简单的计算环境。在这个项目中，我们的目标是克服这些限制。我们将开发在欧几里德数据空间、度量空间甚至非度量空间中使用复距离函数处理RkNN查询的技术。此外，我们将探索在计算环境约束下的RkNN查询的新方法，例如在传感器网络中（需要优化设备的能耗而不是I/O成本），在交互式服务中（需要随时/渐进式查询处理），以及在客户机/服务器场景中（约束是对结果的身份验证）。

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).