Title: Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities Show Chinese title

Title: 具备自适应感知能力的基于图的近似最近邻搜索赋能

Abstract: Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces finds extensive applications in databases, information retrieval, recommender systems, etc. While graph-based methods have emerged as the leading solution for ANNS due to their superior query performance, they still face several challenges, such as struggling with local optima and redundant computations. These issues arise because existing methods (i) fail to fully exploit the topological information underlying the proximity graph G, and (ii) suffer from severe distribution mismatches between the base data and queries in practice. To this end, this paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness, as a lightweight and adaptive module atop the graph-based indexes to accelerate ANNS. Specifically, GATE formulates the critical problem to identify an optimal entry point in the proximity graph for a given query, facilitating faster online search. By leveraging the inherent clusterability of high-dimensional data, GATE first extracts a small set of hub nodes V as candidate entry points. Then, resorting to a contrastive learning-based two-tower model, GATE encodes both the structural semantics underlying G and the query-relevant features into the latent representations of these hub nodes V. A navigation graph index on V is further constructed to minimize the model inference overhead. Extensive experiments demonstrate that GATE achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes. Show Chinese abstract

Abstract: 在高维空间中的近似最近邻搜索 (ANNS) 广泛应用于数据库、信息检索、推荐系统等领域。 尽管基于图的方法由于其卓越的查询性能已成为 ANNS 的主要解决方案，但它们仍然面临一些挑战，例如陷入局部最优解和冗余计算等问题。 这些问题的产生是因为现有方法未能充分利用底层接近图 G 的拓扑信息，并且在实际应用中基数据与查询之间存在严重的分布不匹配。 为了解决这些问题，本文提出了 GATE（高阶自适应拓扑和查询感知的临近图），作为一个轻量级且自适应的模块，置于基于图的索引之上以加速 ANNS。 具体来说，GATE 将问题形式化为确定接近图中给定查询的最佳入口点，从而加快在线搜索速度。 通过利用高维数据的固有聚类特性，GATE 首先提取一小组枢纽节点 V 作为候选入口点。 然后，借助对比学习的双塔模型，GATE 将接近图 G 的结构语义以及与查询相关的特征编码到这些枢纽节点 V 的潜在表示中。进一步构建了一个在 V 上的导航图索引以最小化模型推理开销。 大量实验表明，GATE 相比最先进的基于图的索引，在查询性能上实现了 1.2 到 2.0 倍的加速。