Bridging Speed and Accuracy to Approximate $K$-Nearest Neighbor Search

在高维空间中进行近似K最近邻（AKNN）搜索是一个关键但具有挑战性的问题。 AKNN搜索的效率在很大程度上取决于距离的计算，这个过程显著影响运行时间。为了提高计算效率，现有的工作通常选择估计近似距离而不是计算精确距离，以减少AKNN搜索的准确性。最近的ADSampling方法尝试通过使用随机投影进行距离逼近，并基于误差界限调整这些逼近来提高准确性，来缓解这个问题。然而，ADSampling面临着有效性和通用性的限制，主要是由于其距离逼近的次优性和其严重依赖于随机投影矩阵来获得误差界限。在这项研究中，我们提出了一种新方法，它使用最优正交投影而不是随机投影，从而提供了改进的距离逼近。此外，我们的方法使用误差分位数而不是误差界限进行逼近调整，误差分位数的推导可以独立于投影矩阵进行，从而扩展了我们方法的通用性。广泛的实验证实了所提出方法的卓越效率和有效性。特别是，与ADSampling的最新方法相比，我们的方法在几乎没有准确性损失的情况下，在真实数据集上实现了1.6到2.1倍的加速。

论文旨在解决高维空间下的近邻搜索问题的效率和准确性问题，通过使用最优正交投影和误差分位数来提高距离估计的准确性和效率。

使用最优正交投影和误差分位数来提高距离估计的准确性和效率，相比于现有的基于随机投影的方法，提供了更好的距离估计和更广泛的适用性。

论文提出的方法在实验中表现出了比现有方法更高的效率和准确性，特别是相比于ADSampling方法，速度提高了1.6到2.1倍，几乎没有损失准确性。此外，论文还提供了详细的实验设计和数据集信息。

在该领域的相关研究还包括：1. ADSampling方法；2. 基于哈希的方法；3. 基于树的方法等。