Tighter bounds for nearest neighbor search and related problems in the cell probe model
Omer Barkol, Yuval Rabani · 2000
We prove new lower bounds for nearest neighbor search in the Hamming cube.Our lower bounds are for randomized, two-sided error, algorithms in Yao's cell probe model.Our bounds are in the form of a tradeoff among the number of cells, the size of a cell, and the search time.For example, suppose we are searching among n points in the d dimensional cube, we use poly(n, d) cells, each containing poly(d, log n) bits.We get a lower bound of ~2(d/log n) on the search time, a significant improvement over the recent bound of ft(log d) of Borodin et al.This should be contrasted with the upper bound of O(loglogd) for approximate search (and O(1) for a decision version of the problem; our lower bounds hold in that case).By previous results, the bounds for the cube imply similar bounds for nearest neighbor search in high dimensional Euclidean space, and for other geometric problems.