Reverse Nearest Neighbor Search in Metric Spaces 摘要粗译

Abstract—Given a set D of objects, a reverse nearest neighbor (RNN) query returns the objects o in D such that o is closer to a query object q than to any other object in D, according to a certain similarity metric. The existing RNN solutions are not sufficient because they either 1) rely on precomputed information that is expensive to maintain in the presence of updates or 2) are applicable only when the data consists of “Euclidean objects” and similarity is measured using the L2 norm. In this paper, we present the first algorithms for efficient RNN search in generic metric spaces. Our techniques require no detailed representations of objects, and can be applied as long as their mutual distances can be computed and the distance metric satisfies the triangle inequality. We confirm the effectiveness of the proposed methods with extensive experiments.

度量空间中的反最邻查询

摘要-给定一个数据集D的对象，一个反最近邻查询（RNN）返回D中这样的对象，o比D中的其它对象，更接近于查询对象q，根据确定相关度量。现存的RNN解决方案因为以下原因存在一定的不足 1）在更新的情况下维持信息需要依赖重新计算过于昂贵，或者2）只有在数据存在于欧氏对象时，相似性使用L2范式，才可以应用。本文中，我们提供的第一个算法可以有效地在通常的度量空间中进行RNN查询。我们的技术不需要表征对象的细节，并且可以应用在当他们的相互距离可以被计算或者距离满足三角不等式公理。我们通过大量的实验验证我们方案的有效性。

＝＝＝＝＝＝＝＝

以上摘要为粗译，请大家指正与交流。