Distance Comparison Operators for Approximate Nearest Neighbor Search: Exploration and Benchmark

高维向量的近似最近邻搜索(ANNS)已经成为各种机器学习任务中基本且必要的组成部分。先前的研究表明，距离比较操作是ANNS的瓶颈，它决定了查询和索引的性能。为了克服这个挑战，最近提出了一些新颖的方法。基本思想是用较少的计算估计实际距离，以损失精度为代价。在此启发下，我们还提出了一些经典技术和深度学习模型也可以适应这个目的。在本文中，我们系统地分类了已经或可以用于加速距离估计的技术。为了帮助用户了解不同技术的优缺点，我们设计了一个公平和全面的基准测试，Fudist使用相同的基础索引实现这些技术，并在16个真实数据集上使用多个评估指标进行评估。作为一个独立和便携式库，Fudist与特定的索引结构正交，因此可以轻松地在当前的ANNS库中使用，以实现显著的改进。

本论文旨在解决高维向量的近似最近邻搜索（ANNS）中距离比较操作的瓶颈问题，并提出一些新的方法来加速距离估计。

论文提出了一些经典技术和深度学习模型来加速距离估计，以减少计算量，但会导致精度损失。

论文系统地分类了可用于加速距离估计的技术，并设计了一个公平全面的基准测试Fudist，用于评估这些技术在16个真实数据集上的性能表现。Fudist是一个独立且可移植的库，可以轻松地与当前的ANNS库结合使用以实现显著的性能提升。

最近的相关研究包括：《Product Quantization for Nearest Neighbor Search》、《Learning to Hash for Indexing Big Data - A Survey》等。