Papers › Practical linear-space Approximate Near Neighbors in high dimension
Practical linear-space Approximate Near Neighbors in high dimension
Georgia Avarikioti, Ioannis Z. Emiris, Ioannis Psarros, Georgios Samaras
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The c-approximate Near Neighbor problem in high dimensional spaces has been mainly addressed by Locality Sensitive Hashing (LSH), which offers polynomial dependence on the dimension, query time sublinear in the size of the dataset, and subquadratic space requirement. For practical applications, linear space is typically imperative. Most previous work in the linear space regime focuses on the case that c exceeds $1$ by a constant term. In a recently accepted paper, optimal bounds have been achieved for any c>1 \cite{ALRW17}. Towards practicality, we present a new and simple data structure using linear space and sublinear query time for any c>1 including c→1^+. Given an LSH family of functions for some metric space, we randomly project points to the Hamming cube of dimension logn, where n is the number of input points. The projected space contains strings which serve as keys for buckets containing the input points. The query algorithm simply projects the query point, then examines points which are assigned to the same or nearby vertices on the Hamming cube. We analyze in detail the query time for some standard LSH families. To illustrate our claim of practicality, we offer an open-source implementation in {\tt C++}, and report on several experiments in dimension up to 1000 and n up to 10⁶. Our algorithm is one to two orders of magnitude faster than brute force search. Experiments confirm the sublinear dependence on n and the linear dependence on the dimension. We have compared against state-of-the-art LSH-based library {\tt FALCONN}: our search is somewhat slower, but memory usage and preprocessing time are significantly smaller.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections