Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors
Patrick Iff, Paul Bruegger, Marcin Chrapek, Maciej Besta, Torsten Hoefler
文本、图像、音频和视频嵌入模型的进步推动了多个领域的进展,包括检索增强生成、推荐系统、车辆/人员重识别和人脸识别。这些领域的许多应用需要一种高效的方法来检索在嵌入空间中接近给定查询且满足基于项目属性的过滤条件的项目,这一问题被称为过滤近似最近邻搜索(FANNS)。在本工作中,我们对FANNS方法进行了全面的调查和分类,并分析了文献中如何进行基准测试。通过这样做,我们发现了当前FANNS领域的一个关键挑战:缺乏多样化和真实的数据集,特别是来自最新基于transformer的文本嵌入模型的数据集。为了解决这个问题,我们引入了一个新颖的数据集,包含来自arXiv存储库的270多万篇研究论文摘要的嵌入向量,并附带11个真实世界属性,如作者和类别。我们在新数据集上对多种FANNS方法进行了基准测试,发现每种方法都有独特的优势和局限性;没有单一方法在所有场景中表现最佳。例如,ACORN支持各种过滤类型并在不同规模的数据集上表现可靠,但通常被更专业的方法超越。SeRF在有序属性的范围过滤上表现出色,但无法处理分类属性。Filtered-DiskANN和UNG在中等规模数据集上表现优异,但在大规模数据集上失败,这凸显了基于transformer的嵌入带来的挑战,这些嵌入通常比早期嵌入大一个数量级以上。我们得出结论:不存在普遍最优的方法。
Advances in embedding models for text, image, audio, and video drive progress across multiple domains, including retrieval-augmented generation, recommendation systems, vehicle/person reidentification, and face recognition. Many applications in these domains require an efficient method to retrieve items that are close to a given query in the embedding space while satisfying a filter condition based on the item's attributes, a problem known as Filtered Approximate Nearest Neighbor Search (FANNS)....