A Framework For Similarity Search With Space-time Tradeoffs Using Locality-sensitive Filtering

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 \(dn^\{\rho_q+o(1)\}\), update time \(dn^\{\rho_u+o(1)\}\), and space usage \(dn + n^\{1 + \rho_u + o(1)\}\). The space-time tradeoff is tied to the tradeoff between query time and update time, controlled by the exponents \(\rho_q, \rho_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 algori

Stats

• citations12
• S2 citations—
• github stars0
• HF likes0
• heat score8.35
• arxiv keychristiani2016a

Related papers

• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• Qwlsh: Cache-conscious Indexing For Processing Similarity Search Query Workloads In High-dimensional Spaces (2019)4.52
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
• Adaptive Prefiltering For High-dimensional Similarity Search: A Frequency-aware Approach (2025)0.00
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77