A framework for similarity search with space-time tradeoffs using locality-sensitive filtering

DOI10.1137/1.9781611974782.3MaRDI QIDQ4575736zbMATH OpenOpenAlexFDO

Authors Tobias Christiani

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.02687

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 $d{n}^{h{o}_q+o(1)}$, update time $d{n}^{h{o}_u+o(1)}$, and space usage $dn+n^{1+h{o}_u+o(1)}$. The space-time tradeoff is tied to the tradeoff between query time and update time, controlled by the exponents $h{o}_q,h{o}_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 $el{l}_s^d$-space for $0<sleq2$ with query and update exponents $h{o}_q=frac{c}^s(1+lambda{)}^2(c^s+lambda{)}^2$ and $h{o}_u=frac{c}^s(1-lambda{)}^2(c^s+lambda{)}^2$ where $lambdain[-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.

Recommendations

• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Parameter-free locality sensitive hashing for spherical range reporting
• New directions in nearest neighbor searching with applications to lattice sieving
• Optimal Las Vegas approximate near neighbors in \(\ell_p\)
• A locality-sensitive hash for real vectors

Cited in

(12)

• Index structures for fast similarity search for real-valued vectors. I
• On spaced seeds for similarity search
• Lower bounds on lattice sieving and information set decoding
• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Lattice-based locality sensitive hashing is optimal
• Hypercube LSH for approximate near neighbors
• Graph-based time-space trade-offs for approximate near neighbors
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• On the hardness of approximate and exact (bichromatic) maximum inner product
• Polytopes, lattices, and spherical codes for the nearest neighbor problem
• Approximate similarity search under edit distance using locality-sensitive hashing
• Improved space-efficient approximate nearest neighbor search using function inversion

This page was built for publication: A framework for similarity search with space-time tradeoffs using locality-sensitive filtering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575736)