Defines CDuT and gives an exact quadratic algorithm in 1D plus three approximation algorithms in higher dimensions with runtimes O(mn^{2}ε^{-(d+1)}) and near-quadratic under separation assumptions, plus fine-grained complexity analysis.
Optimal Data-Dependent Hashing for Approximate Near Neighbors
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an $n$-point data set in a $d$-dimensional space our data structure achieves query time $O(d n^{\rho+o(1)})$ and space $O(n^{1+\rho+o(1)} + dn)$, where $\rho=\tfrac{1}{2c^2-1}$ for the Euclidean space and approximation $c>1$. For the Hamming space, we obtain an exponent of $\rho=\tfrac{1}{2c-1}$. Our result completes the direction set forth in [AINR14] who gave a proof-of-concept that data-dependent hashing can outperform classical Locality Sensitive Hashing (LSH). In contrast to [AINR14], the new bound is not only optimal, but in fact improves over the best (optimal) LSH data structures [IM98,AI06] for all approximation factors $c>1$. From the technical perspective, we proceed by decomposing an arbitrary dataset into several subsets that are, in a certain sense, pseudo-random.
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 2roles
background 1polarities
background 1representative citing papers
Quantum sieving for SVP in dimension 400 needs ~10^13 physical qubits and ~10^31 years under optimistic assumptions, offering no practical speedup over classical methods.
citing papers explorer
-
Approximate Algorithms for Chamfer Distance Under Translation
Defines CDuT and gives an exact quadratic algorithm in 1D plus three approximation algorithms in higher dimensions with runtimes O(mn^{2}ε^{-(d+1)}) and near-quadratic under separation assumptions, plus fine-grained complexity analysis.
-
On the practicality of quantum sieving algorithms for the shortest vector problem
Quantum sieving for SVP in dimension 400 needs ~10^13 physical qubits and ~10^31 years under optimistic assumptions, offering no practical speedup over classical methods.