SOAR: Improved Indexing for Approximate Nearest Neighbor Search
This paper introduces SOAR: Spilling with Orthogonality-Amplified Residuals, a novel data indexing technique for approximate nearest neighbor (ANN) search. SOAR extends upon previous approaches to ANN search, such as spill trees, that utilize multiple redundant representations while partitioning the data to reduce the probability of missing a nearest neighbor during search. Rather than training and computing these redundant representations independently, however, SOAR uses an orthogonality-amplified residual loss, which optimizes each representation to compensate for cases where other representations perform poorly. This drastically improves the overall index quality, resulting in state-of-the-art ANN benchmark performance while maintaining fast indexing times and low memory consumption.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Hybrid Approximate Nearest Neighbor Indexing and Search (HANNIS) for Large Descriptor Databases
In this paper, we present a novel method for efficient and effective retrieval of similar deep descriptors. Our new hybrid method for indexing and searching for the approximate nearest neighbors in high-dimensional large…
RetrievalEfficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search
Approximate nearest neighbor algorithms are used to speed up nearest neighbor search in a wide array of applications. However, current indexing methods feature several hyperparameters that need to be tuned to reach an ac…
Improving Bilayer Product Quantization for Billion-Scale Approximate Nearest Neighbors in High Dimensions
The top-performing systems for billion-scale high-dimensional approximate nearest neighbor (ANN) search are all based on two-layer architectures that include an indexing structure and a compressed datapoints layer. An in…
Data CompressionQuantizationApproximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper,…
Predictive Indexing for Fast Search
We tackle the computational problem of query-conditioned search. Given a machine-learned scoring rule and a query distribution, we build a predictive index by precomputing lists of potential results sorted based on an ex…
Retrievalscoring rule