Randomized approximate nearest neighbor search with limited adaptivity

Mingmou Liu, Xiaoyin Pan, Yitong Yin

We study the fundamental problem of approximate nearest neighbor search in $d$-dimensional Hamming space $\{0,1{\}}^d$. We study the complexity of the problem in the famous cell-prob…