SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index
Nearest neighbor searches in high-dimensional space have many important applications in domains such as data min-ing, and multimedia databases. The problem is challenging due to the phenomenon called “curse of dimensionality”. An alternative solution is to consider algorithms that returns a c-approximate nearest neighbor (c-ANN) with guaranteed probabilities. Locality Sensitive Hashing (LSH) is among the most widely adopted method, and it achieves high ef-ficiency both in theory and practice. However, it is known to require an extremely high amount of space for indexing, hence limiting its scalability. In this paper, we propose several surprisingly simple meth-ods to answer c-ANN queries with theoretical guarantees requiring only a single tiny index. Our methods are highly flexible and support a variety of functionalities, such as find-ing the exact nearest neighbor with any given probability. In the experiment, our methods demonstrate superior per-formance against the state-of-the-art LSH-based methods, and scale up well to 1 billion high-dimensional points on a single commodity PC. 1.