# A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering

arXiv: https://arxiv.org/abs/1605.02687 · HTML: https://mlsanity.com/paper/1605.02687/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2016.

## Built on by (most cited first, 3 of 3)

- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.01382/) (2022)
- [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021)

## Abstract (arXiv)

We present a framework for similarity search based on Locality-Sensitive Filtering (LSF), generalizing the Indyk-Motwani (STOC 1998) Locality-Sensitive Hashing (LSH) framework to support space-time tradeoffs. Given a family of filters, defined as a distribution over pairs of subsets of space with certain locality-sensitivity properties, we can solve the approximate near neighbor problem in d-dimensional space for an n-point data set with query time dnρq+o(1), update time dnρu+o(1), and space usage dn + n1 + ρu + o(1). The space-time tradeoff is tied to the tradeoff between query time and update time, controlled by the exponents ρq, ρu that are determined by the filter family. Locality-sensitive filtering was introduced by Becker et al. (SODA 2016) together with a framework yielding a single, balanced, tradeoff between query time and space, further relying on the assumption of an efficient oracle for the filter evaluation algorithm. We extend the LSF framework to support space-time tradeoffs and through a combination of existing techniques we remove the oracle assumption. Building on a filter family for the unit sphere by Laarhoven (arXiv 2015) we use a kernel embedding technique by Rahimi & Recht (NIPS 2007) to show a solution to the (r,cr)-near neighbor problem in ℓsd-space for 0 < s ≤ 2 with query and update exponents ρq=fraccs(1+λ)2(cs+λ)2 and ρu=fraccs(1-λ)2(cs+λ)2 where λ∈[-1,1] is a tradeoff parameter. This result improves upon the space-time tradeoff of Kapralov (PODS 2015) and is shown to be optimal in the case of a balanced tradeoff. Finally, we show a lower bound for the space-time tradeoff on the unit sphere that matches Laarhoven's and our own upper bound in the case of random data.