go back
go back
Volume 18, No. 3
Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search
Abstract
High-dimensional approximate 𝐾 nearest neighbor search (AKNN) is a fundamental task for various applications, including informa-is a fundamental task for various applications, including information retrieval. Most existing algorithms for AKNN can be decom-tion 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 al-of DCOs that dominates the time cost in most existing AKNN algorithms. To achieve this, we propose an D ata - A ware D istance E stimation 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 dis-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 ex-search algorithms, e.g., IVF and HNSW , and conduct extensive experiments to demonstrate the superiority.
PVLDB is part of the VLDB Endowment Inc.
Privacy Policy