  We present a new algorithm for the $c$--approximate nearest neighbor search
without false negatives for $l_2^d$. We enhance the dimension reduction method
presented in \cite{wygos_red} and combine it with the standard results of Indyk
and Motwani~\cite{motwani}. We present an efficient algorithm with Las Vegas
guaranties for any $c>1$. This improves over the previous results, which
require $c=\omega(\log\log{n})$ \cite{wygos_red}, where $n$ is the number of
the input points. Moreover, we improve both the query time and the
pre-processing time.
  Our algorithm is tunable, which allows for different compromises between the
query and the pre-processing times. In order to illustrate this flexibility, we
present two variants of the algorithm. The "efficient query" variant involves
the query time of $O(d^2)$ and the polynomial pre-processing time. The
"efficient pre-processing" variant involves the pre-processing time equal to
$O(d^{\omega-1} n)$ and the query time sub-linear in $n$, where $\omega$ is the
exponent in the complexity of the fast matrix multiplication.
  In addition, we introduce batch versions of the mentioned algorithms, where
the queries come in batches of size $d$. In this case, the amortized query time
of the "efficient query" algorithm is reduced to $O(d^{\omega -1})$.
