论文标题
用于近似k-nearest-neighbor的亚线性时间算法，并具有全质量保证
A Sub-linear Time Algorithm for Approximating k-Nearest-Neighbor with Full Quality Guarantee
论文作者
论文摘要
在本文中，我们提出了一种近似K-Nearest-neighbors问题的算法。根据现有研究，有两种近似标准。一个是距离标准，另一个是召回标准。所有以前的算法都遇到了一个问题，即两个近似标准没有理论保证。本文提出的算法统一了两种近似标准，并具有完全理论上的保证。此外，该算法的查询时间是亚线性的。据我们所知，这是第一种实现子线性查询时间和完整理论近似保证的算法。
In this paper we propose an algorithm for the approximate k-Nearest-Neighbors problem. According to the existing researches, there are two kinds of approximation criterion. One is the distance criteria, and the other is the recall criteria. All former algorithms suffer the problem that there are no theoretical guarantees for the two approximation criterion. The algorithm proposed in this paper unifies the two kinds of approximation criterion, and has full theoretical guarantees. Furthermore, the query time of the algorithm is sub-linear. As far as we know, it is the first algorithm that achieves both sub-linear query time and full theoretical approximation guarantee.
