RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search

近似最近邻搜索（ANNS）是许多应用程序的基本和关键组成部分，包括推荐系统和基于大型语言模型的应用程序。随着多模态神经模型的进步，这些模型将来自不同模态的数据转换为共享的高维空间特征向量，跨模态ANNS旨在使用来自一个模态（例如文本）的数据向量作为查询来从另一个模态（例如图像或视频）中检索最相似的项。然而，不同模态的嵌入之间存在固有的分布差距，跨模态查询成为基础数据的分布外（OOD）查询。因此，最先进的ANNS方法在OOD工作负载下表现不佳。在本文中，我们定量分析OOD工作负载的特性，以了解其ANNS效率。与单模态工作负载不同，我们揭示OOD查询在空间上偏离基础数据，OOD查询的k个最近邻在嵌入空间中相距较远。这种特性打破了现有ANNS方法的假设，并不匹配它们为高效搜索而设计的方式。通过OOD工作负载的洞察，我们提出了基于查询分布指导的pRojected bipartite Graph（RoarGraph），这是一种高效的ANNS图形索引。广泛的实验表明，RoarGraph在现代跨模态数据集上显著优于最先进的方法，在OOD查询的90％召回率下，搜索速度最多提高了3.56倍。

解决跨模态近似最近邻搜索中，跨模态查询数据的分布与基础数据的分布不一致导致现有方法性能较差的问题。

提出了一种基于查询数据分布指导的 ANNS 图索引方法 RoarGraph，能够有效地解决跨模态查询数据的分布偏差问题，相比现有方法具有更高的搜索效率。

RoarGraph 在现代跨模态数据集上的实验表明，相比现有方法，能够在 90% 召回率下实现高达 3.56 倍的搜索速度提升。论文提出的问题和解决方案都是新的，实验使用了多个现代的跨模态数据集，并开源了代码。

最近的相关研究包括 Cross-Modal Retrieval with Common Semantic Space、Learning to Hash for Indexing Big Data - A Survey 等。