Improved space-efficient approximate nearest neighbor search using function inversion

DOI10.4230/LIPICS.ESA.2024.88MaRDI QIDQ7253157zbMATH OpenFDO

Authors Samuel McCauley

Publication date 26 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2024.88

zbMATH Keywords

data structuresfunction inversionlocality-sensitive hashingrandomized algorithmssimilarity searchspace efficiency

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A cryptanalytic time-memory trade-off
• A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A vector space model for automatic indexing
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Approximate similarity search under edit distance using locality-sensitive hashing
• Beyond locality-sensitive hashing
• Data structures meet cryptography: 3SUM with preprocessing
• Entropy based nearest neighbor search in high dimensions
• Faster compression methods for a weighted graph using locality sensitive hashing
• Graph-based time-space trade-offs for approximate near neighbors
• Hardness of approximate nearest neighbor search
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• Locality-sensitive hashing of curves
• Locality-sensitive hashing scheme based on p-stable distributions
• Nearest neighbor pattern classification
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• Optimal data-dependent hashing for approximate near neighbors
• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Optimal Las Vegas locality sensitive data structures
• Parameter-free locality sensitive hashing for spherical range reporting
• Probabilistic polynomials and Hamming nearest neighbors
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Revisiting time-space tradeoffs for function inversion
• Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
• Rigorous Time/Space Trade-offs for Inverting Functions
• Set similarity search beyond MinHash
• The function-inversion problem: barriers and opportunities
• The geometry of graphs and some of its algorithmic applications
• Time and space efficient collinearity indexing

This page was built for publication: Improved space-efficient approximate nearest neighbor search using function inversion

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