DARTH：通过提前终止实现声明式召回，用于近似最近邻搜索

《Proceedings of the ACM on Management of Data》：DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search

DARTH通过自适应早期终止策略优化近似最近邻搜索，在满足用户定义召回率的同时实现速度显著提升，HNSW平均加速6.8倍，IVF平均加速13.6倍。

　　

摘要

近似最近邻搜索（ANNS）在性能和召回率（即结果质量）之间存在固有的权衡。每种ANNS算法都提供其自身的参数，以便应用程序能够影响搜索的召回率/性能权衡。这种情况存在双重问题：首先，应用程序开发者必须通过实验来调整这些参数，以针对每种用例获得所需的召回率。这一过程通常需要大量工作；更糟糕的是，所选参数可能对某些查询产生良好的召回率，但对复杂查询的召回率却很低。为了解决这些问题，我们提出了DARH方法，该方法利用目标声明式召回率。DARH通过在ANNS索引的基础上采用自适应提前终止策略来实现目标声明式召回率。通过广泛的实验，我们证明DARH能够有效满足用户定义的召回率目标，同时显著提升搜索速度：对于HNSW算法，速度提升高达14.6倍（平均值：6.8倍；中位数：5.7倍）；对于IVF算法，速度提升高达41.8倍（平均值：13.6倍；中位数：8.1倍）。

可用格式

您可以通过以下格式查看完整内容：

PDF