Isotropic Hashing Weihao Kong,Wu-Jun Li Shanghai Key Laboratory of Scalable Computing and Systems Department of Computer Science and Engineering,Shanghai Jiao Tong University,China {kongweihao,liwujun)@cs.sjtu.edu.cn Abstract Most existing hashing methods adopt some projection functions to project the o- riginal data into several dimensions of real values,and then each of these projected dimensions is quantized into one bit(zero or one)by thresholding.Typically,the variances of different projected dimensions are different for existing projection functions such as principal component analysis(PCA).Using the same number of bits for different projected dimensions is unreasonable because larger-variance dimensions will carry more information.Although this viewpoint has been widely accepted by many researchers,it is still not verified by either theory or experiment because no methods have been proposed to find a projection with equal variances for different dimensions.In this paper,we propose a novel method,called isotrop- ic hashing(IsoHash),to learn projection functions which can produce projected dimensions with isotropic variances (equal variances).Experimental results on real data sets show that IsoHash can outperform its counterpart with different vari- ances for different dimensions,which verifies the viewpoint that projections with isotropic variances will be better than those with anisotropic variances. 1 Introduction Due to its fast query speed and low storage cost,hashing [1,5]has been successfully used for approximate nearest neighbor(ANN)search [28].The basic idea of hashing is to learn similarity- preserving binary codes for data representation.More specifically,each data point will be hashed into a compact binary string,and similar points in the original feature space should be hashed into close points in the hashcode space.Compared with the original feature representation,hashing has two advantages.One is the reduced storage cost,and the other is the constant or sub-linear query time complexity [28].These two advantages make hashing become a promising choice for efficient ANN search in massive data sets[1,5,6,9,10.14,15,17,20,21,23,26.29,30,31,32,33,34. Most existing hashing methods adopt some projection functions to project the original data into several dimensions of real values,and then each of these projected dimensions is quantized into one bit(zero or one)by thresholding.Locality-sensitive hashing(LSH)[1,5]and its extension- s [4,18,19,22,25]use simple random projections for hash functions.These methods are called data-independent methods because the projection functions are independent of training data.Anoth- er class of methods are called data-dependent methods,whose projection functions are learned from training data.Representative data-dependent methods include spectral hashing(SH)[31],anchor graph hashing(AGH)[21].sequential projection learning(SPL)[29],principal component analy- sis [13]based hashing (PCAH)[7],and iterative quantization (ITQ)[7,8].SH learns the hashing functions based on spectral graph partitioning.AGH adopts anchor graphs to speed up the com- putation of graph Laplacian eigenvectors,based on which the Nystrom method is used to compute projection functions.SPL leans the projection functions in a sequential way that each function is designed to correct the errors caused by the previous one.PCAH adopts principal component anal- ysis (PCA)to learn the projection functions.ITQ tries to learn an orthogonal rotation matrix to refine the initial projection matrix learned by PCA so that the quantization error of mapping the dataIsotropic Hashing Weihao Kong, Wu-Jun Li Shanghai Key Laboratory of Scalable Computing and Systems Department of Computer Science and Engineering, Shanghai Jiao Tong University, China {kongweihao,liwujun}@cs.sjtu.edu.cn Abstract Most existing hashing methods adopt some projection functions to project the o￾riginal data into several dimensions of real values, and then each of these projected dimensions is quantized into one bit (zero or one) by thresholding. Typically, the variances of different projected dimensions are different for existing projection functions such as principal component analysis (PCA). Using the same number of bits for different projected dimensions is unreasonable because larger-variance dimensions will carry more information. Although this viewpoint has been widely accepted by many researchers, it is still not verified by either theory or experiment because no methods have been proposed to find a projection with equal variances for different dimensions. In this paper, we propose a novel method, called isotrop￾ic hashing (IsoHash), to learn projection functions which can produce projected dimensions with isotropic variances (equal variances). Experimental results on real data sets show that IsoHash can outperform its counterpart with different vari￾ances for different dimensions, which verifies the viewpoint that projections with isotropic variances will be better than those with anisotropic variances. 1 Introduction Due to its fast query speed and low storage cost, hashing [1, 5] has been successfully used for approximate nearest neighbor (ANN) search [28]. The basic idea of hashing is to learn similarity￾preserving binary codes for data representation. More specifically, each data point will be hashed into a compact binary string, and similar points in the original feature space should be hashed into close points in the hashcode space. Compared with the original feature representation, hashing has two advantages. One is the reduced storage cost, and the other is the constant or sub-linear query time complexity [28]. These two advantages make hashing become a promising choice for efficient ANN search in massive data sets [1, 5, 6, 9, 10, 14, 15, 17, 20, 21, 23, 26, 29, 30, 31, 32, 33, 34]. Most existing hashing methods adopt some projection functions to project the original data into several dimensions of real values, and then each of these projected dimensions is quantized into one bit (zero or one) by thresholding. Locality-sensitive hashing (LSH) [1, 5] and its extension￾s [4, 18, 19, 22, 25] use simple random projections for hash functions. These methods are called data-independent methods because the projection functions are independent of training data. Anoth￾er class of methods are called data-dependent methods, whose projection functions are learned from training data. Representative data-dependent methods include spectral hashing (SH) [31], anchor graph hashing (AGH) [21], sequential projection learning (SPL) [29], principal component analy￾sis [13] based hashing (PCAH) [7], and iterative quantization (ITQ) [7, 8]. SH learns the hashing functions based on spectral graph partitioning. AGH adopts anchor graphs to speed up the com￾putation of graph Laplacian eigenvectors, based on which the Nystrom method is used to compute ¨ projection functions. SPL leans the projection functions in a sequential way that each function is designed to correct the errors caused by the previous one. PCAH adopts principal component anal￾ysis (PCA) to learn the projection functions. ITQ tries to learn an orthogonal rotation matrix to refine the initial projection matrix learned by PCA so that the quantization error of mapping the data 1