Lower bounds for high dimensional nearest neighbor search and related problems
From MaRDI portal
Publication:2819560
DOI10.1145/301250.301330zbMath1346.68077MaRDI 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
68P10: Searching and sorting
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
An Improved Algorithm Finding Nearest Neighbor Using Kd-trees, Cell-probe lower bounds for the partial match problem, Indexability, concentration, and VC theory, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, A strong lower bound for approximate nearest neighbor searching, Text indexing with errors, On approximate nearest neighbors under \(l_\infty\) norm, Graph-theoretic multisample tests of equality in distribution for high dimensional data, Evaluating top-\(N\) queries in \(n\)-dimensional normed spaces