Approximate nearest neighbor search in the Hamming cube

given a set of points in {0,1}^d, store it so that, for any query
element, the nearest point (in the L^1 sense) can be found quickly.
We describe a lower bound result of Chakrabarti, Chazelle, Gum and
Lvov that shows that at least log log d / log log log d queries are
necessary to answer such queries in the worst case. This result holds
in the cell probe model. This result appeared in STOC 1999.