Factorized Binary Codes for Large-Scale Nearest Neighbor Search

Hashing algorithms for fast large-scale nearest neighbor search transform data points into compact binary codes by applying a set of learned or randomly generated hash functions. Retrieval accuracy generally increases with the number of hash functions, but increasing the number of hash functions also increases the storage requirements of the resulting binary codes. We present a novel factorized binary codes approach that uses an approximate matrix factorization of the binary codes to increase the number of hash functions while maintaining the original storage requirements. The proposed approach does not assume a particular algorithm for generating the hash functions, and requires only that we can discover and take advantage of correlations among the hash functions. Experiments on publicly available datasets suggest that factorized binary codes work particularly well for locality-sensitive hashing algorithms.