Before revision:  0pt%DIFAUXCMD gives an algorithm for c-approximate nearest neighbor search without false negatives with the query time O(d^2) and the pre-processing time O(n^{O(\frac{1{c-1}})}), for c<2.}
After revision:  Combining the dimension reduction with the algorithm presented in \mbox{%DIFAUXCMD motwani0pt%DIFAUXCMD gives an algorithm for c-approximate nearest neighbor search without false negatives with the query time O(d^2) and the pre-processing time O(n^{O(\frac{1{c-1}})}), for c<2.}