Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Optimal Las Vegas Approximate Near Neighbors in p

Optimal Las Vegas Approximate Near Neighbors in p We show that approximate near neighbor search in high dimensions can be solved in a Las Vegas fashion (i.e., without false negatives) for ℓp (1≤ p≤ 2) while matching the performance of optimal locality-sensitive hashing. Specifically, we construct a data-independent Las Vegas data structure with query time O(dnρ) and space usage O(dn1+ρ) for (r, c r)-approximate near neighbors in Rd under the ℓp norm, where ρ = 1/cp + o(1). Furthermore, we give a Las Vegas locality-sensitive filter construction for the unit sphere that can be used with the data-dependent data structure of Andoni et al. (SODA 2017) to achieve optimal space-time tradeoffs in the data-dependent setting. For the symmetric case, this gives us a data-dependent Las Vegas data structure with query time O(dnρ) and space usage O(dn1+ρ) for (r, c r)-approximate near neighbors in Rd under the ℓp norm, where ρ = 1/(2cp - 1) + o(1).Our data-independent construction improves on the recent Las Vegas data structure of Ahle (FOCS 2017) for ℓp when 1 < p≤ 2. Our data-dependent construction performs even better for ℓp for all pε [1, 2] and is the first Las Vegas approximate near neighbors data structure to make use of data-dependent approaches. We also answer open questions of Indyk (SODA 2000), Pagh (SODA 2016), and Ahle by showing that for approximate near neighbors, Las Vegas data structures can match state-of-the-art Monte Carlo data structures in performance for both the data-independent and data-dependent settings and across space-time tradeoffs. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Optimal Las Vegas Approximate Near Neighbors in p

Wei, Alexander
ACM Transactions on Algorithms (TALG) , Volume 18 (1): 27 – Jan 22, 2022
Download PDF
27 pages

Loading next page...
 
/lp/association-for-computing-machinery/optimal-las-vegas-approximate-near-neighbors-in-p-PcbOW70swU
Publisher
Association for Computing Machinery
Copyright
Copyright © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3461777
Publisher site
See Article on Publisher Site

Abstract

We show that approximate near neighbor search in high dimensions can be solved in a Las Vegas fashion (i.e., without false negatives) for ℓp (1≤ p≤ 2) while matching the performance of optimal locality-sensitive hashing. Specifically, we construct a data-independent Las Vegas data structure with query time O(dnρ) and space usage O(dn1+ρ) for (r, c r)-approximate near neighbors in Rd under the ℓp norm, where ρ = 1/cp + o(1). Furthermore, we give a Las Vegas locality-sensitive filter construction for the unit sphere that can be used with the data-dependent data structure of Andoni et al. (SODA 2017) to achieve optimal space-time tradeoffs in the data-dependent setting. For the symmetric case, this gives us a data-dependent Las Vegas data structure with query time O(dnρ) and space usage O(dn1+ρ) for (r, c r)-approximate near neighbors in Rd under the ℓp norm, where ρ = 1/(2cp - 1) + o(1).Our data-independent construction improves on the recent Las Vegas data structure of Ahle (FOCS 2017) for ℓp when 1 < p≤ 2. Our data-dependent construction performs even better for ℓp for all pε [1, 2] and is the first Las Vegas approximate near neighbors data structure to make use of data-dependent approaches. We also answer open questions of Indyk (SODA 2000), Pagh (SODA 2016), and Ahle by showing that for approximate near neighbors, Las Vegas data structures can match state-of-the-art Monte Carlo data structures in performance for both the data-independent and data-dependent settings and across space-time tradeoffs.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jan 22, 2022

Keywords: Approximate near neighbor search

References

  • It is NP-hard to Verify an LSF on the Sphere
    [,
  • Optimal Las Vegas locality sensitive data structures
    [,
  • The fast Johnson–Lindenstrauss transform and approximate nearest neighbors
    [,
  • Almost k-wise vs
    [,
  • Algorithmic construction of sets for k-restrictions
    [,
  • Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
    [,
  • Nearest neighbors in high-dimensional spaces
    [,
  • Practical and optimal LSH for angular distance
    [,
  • Beyond locality-sensitive hashing
    [,
  • Approximate nearest neighbor search in high dimensions
    [,
  • Optimal hashing-based time-space trade-offs for approximate near neighbors
    [,
  • Optimal data-dependent hashing for approximate near neighbors
    [,
  • Tight lower bounds for data-dependent locality-sensitive hashing
    [,
  • Efficient exact set-similarity joins
    [,
  • New directions in nearest neighbor searching with applications to lattice sieving
    [,
  • Syntactic clustering of the web
    [,
  • Finding frequent items in data streams
    [,
  • A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
    [,
  • Set similarity search beyond MinHash
    [,
  • A randomized algorithm for closest-point queries
    [,
  • Simple analyses of the sparse johnson-lindenstrauss transform
    [,
  • Optimal approximate matrix product in terms of stable rank
    [,
  • Locality-sensitive hashing scheme based on p-stable distributions
    [,
  • Similarity search in high dimensions via hashing
    [,
  • Distance sensitive Bloom filters without false negatives
    [,
  • Approximate nearest neighbor: Towards removing the curse of dimensionality
    [,
  • Probability inequalities for sums of bounded random variables
    [,
  • Dimensionality reduction techniques for proximity problems
    [,
  • Extensions of Lipschitz maps into a Hilbert space
    [,
  • Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
    [,
  • Efficient search for approximate nearest neighbor in high dimensional spaces
    [,
  • Point location in arrangements of hyperplanes
    [,
  • Lower bounds on locality sensitive hashing
    [,
  • Splitters and near-optimal derandomization
    [,
  • Algorithms for High Dimensional Data
    [,
  • Optimal lower bounds for locality-sensitive hashing (except when q is tiny)
    [,
  • Locality-sensitive hashing without false negatives
    [,
  • Scalability and total recall with fast CoveringLSH
    [,
  • Approximate nearest neighbors search without false negatives for \ell _2 for c\gt \sqrt {\log \log n}
    [,
  • Improved approximate near neighbor search without false negatives for \ell _2
    [,