Coding for Random Projections and Approximate Near Neighbor Search
  This technical note compares two coding (quantization) schemes for random
projections in the context of sub-linear time approximate near neighbor search.
The first scheme is based on uniform quantization while the second scheme
utilizes a uniform quantization plus a uniformly random offset (which has been
popular in practice). The prior work compared the two schemes in the context of
similarity estimation and training linear classifiers, with the conclusion that
the step of random offset is not necessary and may hurt the performance
(depending on the similarity level). The task of near neighbor search is
related to similarity estimation with importance distinctions and requires own
study. In this paper, we demonstrate that in the context of near neighbor
search, the step of random offset is not needed either and may hurt the
performance (sometimes significantly so, depending on the similarity and other
parameters).
