Multidimensional reverse kNN search

Abstract Given a multidimensional point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following deficiencies: they (i) do not support arbitrary values of k, (ii) cannot deal efficiently with database updates, (iii) are applicable only to 2D data but not to higher dimensionality, and (iv) retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact RkNN processing with arbitrary values of k on dynamic, multidimensional datasets. Our methods utilize a conventional data-partitioning index on the dataset and do not require any pre-computation. As a second step, we extend the proposed techniques to continuous RkNN search, which returns the RkNN results for every point on a line segment. We evaluate the effectiveness of our algorithms with extensive experiments using both real and synthetic datasets.

多维反k最近邻查询 （摘要粗译）

摘要 给定一个多维点q，一个反k最近邻查询（RkNN）检索所有的数据点，q作为他们的k最近邻居。现存的处理这样查询的方法有着至少下面的一个缺点：他们（i）不支持任意k值,(ii)不能有效地处理数据更新，(iii)只能应用在2维数据不能用于更高的维度，并且（iv）只能检索近似结果。出于这些缺点，我们开发精确的RkNN算法动态处理任意k值，多维数据集。我们的方法在数据集中使用传统的数据分区索引并且不需要任何的预计算机。作为第二步，我们扩展了所提出技术在持续RkNN查询，在每一个线段点上，返回RkNN结果。我们通过大量的使用真实的和动态的数据集的实验估计了算法的效率。

＝＝＝＝＝＝＝＝＝

摘要粗译，仅供参考，欢迎指正交流。