Lower bounds for high dimensional nearest neighbor search and related problems
From MaRDI portal
Publication:2819560
DOI10.1145/301250.301330zbMath1346.68077OpenAlexW2062539466MaRDI QIDQ2819560
Yuval Rabani, Allan Borodin, Rafail Ostrovsky
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301330
Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
A strong lower bound for approximate nearest neighbor searching ⋮ Graph-theoretic multisample tests of equality in distribution for high dimensional data ⋮ Indexability, concentration, and VC theory ⋮ Text indexing with errors ⋮ Tighter lower bounds for nearest neighbor search and related problems in the cell probe model ⋮ Evaluating top-\(N\) queries in \(n\)-dimensional normed spaces ⋮ Cell-probe lower bounds for the partial match problem ⋮ An Improved Algorithm Finding Nearest Neighbor Using Kd-trees ⋮ On approximate nearest neighbors under \(l_\infty\) norm
This page was built for publication: Lower bounds for high dimensional nearest neighbor search and related problems
