Tighter bounds for nearest neighbor search and related problems in the cell probe model

DOI10.1145/335305.335350zbMath1296.68174OpenAlexW1992402998MaRDI QIDQ3192006

Omer Barkol, Yuval Rabani

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335350

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

A strong lower bound for approximate nearest neighbor searching ⋮ Is the \(k\)-NN classifier in high dimensions affected by the curse of dimensionality? ⋮ Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions ⋮ Indexability, concentration, and VC theory ⋮ Text indexing with errors ⋮ Cell-probe lower bounds for the partial match problem

This page was built for publication: Tighter bounds for nearest neighbor search and related problems in the cell probe model