Improved Space-efficient Approximate Nearest Neighbor Search Using Function Inversion

Abstract

Approximate nearest neighbor search (ANN) data structures have widespread applications in machine learning, computational biology, and text processing. The goal of ANN is to preprocess a set S so that, given a query q, we can find a point y whose distance from q approximates the smallest distance from q to any point in S. For most distance functions, the best-known ANN bounds for high-dimensional point sets are obtained using techniques based on locality-sensitive hashing (LSH). Unfortunately, space efficiency is a major challenge for LSH-based data structures. Classic LSH techniques require a very large amount of space, oftentimes polynomial in |S|. A long line of work has developed intricate techniques to reduce this space usage, but these techniques suffer from downsides: they must be hand tailored to each specific LSH, are often complicated, and their space reduction comes at the cost of significantly increased query times. In this paper we explore a new way to improve the spac

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymccauley2024improved

Related papers

• Lorann: Low-rank Matrix Factorization For Approximate Nearest Neighbor Search (2024)2.26
• Random Binary Trees For Approximate Nearest Neighbour Search In Binary Space (2017)2.26
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• A Multilabel Classification Framework For Approximate Nearest Neighbor Search (2019)0.00