Abstract. We propose theoretical and empirical improvements for twostage hashing methods. We first provide a theoretical analysis on the
quality of the binary codes and show that, under mild assumptions, a
residual learning scheme can construct binary codes that fit any neighborhood structure with arbitrary accuracy. Secondly, we show that with
high-capacity hash functions such as CNNs, binary code inference can
be greatly simplified for many standard neighborhood definitions, yielding smaller optimization problems and more robust codes. Incorporating
our findings, we propose a novel two-stage hashing method that significantly outperforms previous hashing studies on widely used image
retrieval benchmarks.