@Aiger2013], and the scale of its database has been increasing rapidly in recent times. Furthermore, to achieve more accurate retrieval results, high-dimensional features such as Fisher Vectors [@Perronnin2007; @Perronnin2010] and VLAD [@Jegou2012] are being used in the computer vision community. To achieve feasible retrieval with such features, highly efficient ANN search methods is necessarily needed.

Vector Quantization based methods are widely used and actively studied for ANN. For high-dimensions, Product Quantization [@Jegou2011] and its family are the state-of-the-art methods [@Ge2013]. It reduces high-dimensional vector space into direct product of small subspaces. Then a clustering is applied for each subspace to obtain representative vectors (quantizers). Although product quantization based methods are applicable to high-dimensional features, it is still not easy to obtain good quantizer in some cases, and a random rotation often needed before PQ is expensive in high-dimensions. And the floating-point distance calculation needed for retrieval is also expensive compared to binary-based methods [@Gong2013].

Binary hashing is one of the most commonly used techniques for efficient retrieval [@Jain2008; @Wang2010; @Wang2010b; @He2012], recognition [@Torralba2008a], and other problems[@Jegou2012; @Chaudhry2010]. It is a series of methods that transforms real-valued feature vectors into binary-valued ones. Binary-valued vectors are highly favorable for large-scale or high-dimensional 