Title: EnhanceGraph: A Continuously Enhanced Graph-based Index for High-dimensional Approximate Nearest Neighbor Search Show Chinese title

Title: EnhanceGraph：一种用于高维近似最近邻搜索的持续增强图索引

Abstract: Recently, Approximate Nearest Neighbor Search in high-dimensional vector spaces has garnered considerable attention due to the rapid advancement of deep learning techniques. We observed that a substantial amount of search and construction logs are generated throughout the lifespan of a graph-based index. However, these two types of valuable logs are not fully exploited due to the static nature of existing indexes. We present the EnhanceGraph framework, which integrates two types of logs into a novel structure called a conjugate graph. The conjugate graph is then used to improve search quality. Through theoretical analyses and observations of the limitations of graph-based indexes, we propose several optimization methods. For the search logs, the conjugate graph stores the edges from local optima to global optima to enhance routing to the nearest neighbor. For the construction logs, the conjugate graph stores the pruned edges from the proximity graph to enhance retrieving of k nearest neighbors. Our experimental results on several public and real-world industrial datasets show that EnhanceGraph significantly improves search accuracy with the greatest improvement on recall from 41.74% to 93.42%, but does not sacrifices search efficiency. In addition, our EnhanceGraph algorithm has been integrated into Ant Group's open-source vector library, VSAG. Show Chinese abstract

Abstract: 最近，由于深度学习技术的快速发展，高维向量空间中的近似最近邻搜索引起了广泛关注。 我们观察到，在基于图的索引生命周期中会产生大量搜索和构建日志。 然而，由于现有索引的静态性质，这两种有价值的日志并未得到充分利用。 我们提出了EnhanceGraph框架，该框架将两种类型的日志整合到一种称为共轭图的新结构中。 然后利用共轭图来提高搜索质量。 通过理论分析和对基于图的索引局限性的观察，我们提出了几种优化方法。 对于搜索日志，共轭图存储从局部最优到全局最优的边，以增强对最近邻的路由。 对于构建日志，共轭图存储来自邻近图的剪枝边，以增强k最近邻的检索。 我们在多个公开和现实世界的工业数据集上的实验结果表明，EnhanceGraph显著提高了搜索准确性，召回率的提升最大，从41.74%提高到93.42%，但没有牺牲搜索效率。 此外，我们的EnhanceGraph算法已集成到蚂蚁集团的开源向量库VSAG中。