Multimedia semantics-aware query-adaptive hashing with bits reconfigurability

In the past decade, locality-sensitive hashing (LSH) has gained a large amount of attention from both the multimedia and computer vision communities owing to its empirical success and theoretic guarantee in large-scale multimedia indexing and retrieval. Original LSH algorithms are designated for generic metrics such as Cosine similarity, l_n-norm and Jaccard index, which are later extended to support those metrics learned from user-supplied supervision information. One of the common drawbacks of existing algorithms lies in their incapability to be flexibly adapted to the metric changes, along with the inefficacy when handling diverse semantics (e.g., the large number of semantic object categories in the ImageNet database), which motivates our proposed framework toward reconfigurable hashing. The basic idea of the proposed indexing framework is to maintain a large pool of over-complete hashing functions, which are randomly generated and shared when indexing diverse multimedia semantics. For specific semantic category, the algorithm adaptively selects the most relevant hashing bits by maximizing the consistency between semantic distance and hashing-based Hamming distance, thereby achieving reusability of the pre-computed hashing bits. Such a scheme especially benefits the indexing and retrieval of large-scale databases, since it facilitates one-off indexing rather than continuous computation-intensive maintenance toward metric adaptation. In practice, we propose a sequential bit-selection algorithm based on local consistency and global regularization. Extensive studies are conducted on large-scale image benchmarks to comparatively investigate the performance of different strategies for reconfigurable hashing. Despite the vast literature on hashing, to our best knowledge rare endeavors have been spent toward the reusability of hashing structures in large-scale data sets.