Balanced Hashing

Hashing for nearest neighbor search has attracted considerable interest recently given its efficiency in speed and storage. Many methods follow a projection-quantization framework which firstly projects original data into low-dimensional compact space and secondly quantifies each projected dimension to 1 bit by thresholding. The variance of projected dimensions, however, may vary a lot so that quantifying them equivalently degrades the searching performance. In this paper, we put forward a novel method, dubbed Balanced hashing (BH), which finds adjustment functions to reproject the data such that the variance of dimensions can be balanced by directly and explicitly maximizing the degree of balance of data, while preserving important properties. Experiments on benchmarks demonstrate that BH can outperform several state-of-the-art methods.