Title: Tight Bounds for Approximate Nearest Neighbour Search
Speaker: Amit Chakrabarti, Dartmouth College
Date: March 22, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider the approximate nearest neighbour search problem (ANN) on the d-dimensional Hamming Cube. We show that a randomised cell probe algorithm that uses polynomial storage and poly(d) word size requires a worst case query time of Omega(log log d / log log log d). The approximation factor may be as loose as 2^{log^{1-eta} d} for any fixed eta > 0. This fills a major gap in the study of ANN since all earlier lower bounds either did not allow randomisation or did not allow approximation.
Generalising the dimension reduction techniques in the ANN algorithm of Kushilevitz et al., we then give a cell probe upper bound which matches the lower bound up to a constant, for any constant approximation factor eps > 0.
Our lower bound uses information theoretic techniques for communication complexity, a theme that has been prominent in recent research.
Joint work with Oded Regev.
See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html