  Nearest neighbor search is known as a challenging issue that has been studied
for several decades. Recently, this issue becomes more and more imminent in
viewing that the big data problem arises from various fields. In this paper, a
scalable solution based on hill-climbing strategy with the support of k-nearest
neighbor graph (kNN) is presented. Two major issues have been considered in the
paper. Firstly, an efficient kNN graph construction method based on two means
tree is presented. For the nearest neighbor search, an enhanced hill-climbing
procedure is proposed, which sees considerable performance boost over original
procedure. Furthermore, with the support of inverted indexing derived from
residue vector quantization, our method achieves close to 100% recall with high
speed efficiency in two state-of-the-art evaluation benchmarks. In addition, a
comparative study on both the compressional and traditional nearest neighbor
search methods is presented. We show that our method achieves the best
trade-off between search quality, efficiency and memory complexity.
