SOAR: Improved Indexing for Approximate Nearest Neighbor Search
This work addresses the need for efficient and accurate nearest neighbor search in large-scale data applications, representing an incremental improvement over existing methods like spill trees.
The paper tackles the problem of approximate nearest neighbor search by introducing SOAR, a data indexing technique that uses an orthogonality-amplified residual loss to optimize redundant representations, resulting in state-of-the-art benchmark performance with fast indexing and low memory consumption.
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.