提出DADE方法，加速高维近邻搜索中的距离计算。
Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search
- 通过低维空间估计距离，替代精确计算
- 理论证明估计无偏，且可自适应确定维度
- 集成到IVF、HNSW等算法，显著提速
高维近似最近邻搜索（AKNN）是信息检索等应用的基础任务。现有AKNN算法通常分为候选生成和距离比较操作（DCOs）两部分，其中DCOs占据主要耗时。本文聚焦于加速这一关键环节，提出数据感知的距离估计方法DADE，通过在低维空间近似精确距离。理论上证明了DADE在数据分布下估计无偏，并在此基础上提出优化估计方案。同时设计假设检验方法，自适应确定达到足够置信度所需的维度数。将DADE集成至IVF、HNSW等主流AKNN算法中，大量实验验证其有效性与优越性。
原文摘要 · Abstract (English)
High-dimensional approximate $K$ nearest neighbor search (AKNN) is a fundamental task for various applications, including information retrieval. Most existing algorithms for AKNN can be decomposed into two main components, i.e., candidate generation and distance comparison operations (DCOs). While different methods have unique ways of generating candidates, they all share the same DCO process. In this study, we focus on accelerating the process of DCOs that dominates the time cost in most existing AKNN algorithms. To achieve this, we propose an Data-Aware Distance Estimation approach, called DADE, which approximates the exact distance in a lower-dimensional space. We theoretically prove that the distance estimation in DADE is unbiased in terms of data distribution. Furthermore, we propose an optimized estimation based on the unbiased distance estimation formulation. In addition, we propose a hypothesis testing approach to adaptively determine the number of dimensions needed to estimate the exact distance with sufficient confidence. We integrate DADE into widely-used AKNN search algorithms, e.g., IVF and HNSW, and conduct extensive experiments to demonstrate the superiority.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。