A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov · 1999
We consider the nearest-neighbor problem over the d-cube: given a collection of points in {0, 1} d, find the one nearest to a query point (in the L 1 sense). We establish a lower bound of Ω(log log d/log log log d)ontheworst-casequery time. This result holds in the cell probe model with (any amount of) polynomial storage and word-size d O(1). The same lower bound holds for the approximate version of the problem, where the answer may be any point further than the nearest neighbor by a factor as large as 2 ⌊(log d)1−ε ⌋ , for any fixed ε>0. 1