Improved Search in Hamming Space Using Deep Multi-Index Hashing

Hanjiang Lai, Yan Pan, Si Liu, Zhenbin Weng, Jian Yin

TL;DR

This paper introduces a novel deep learning architecture for efficient and accurate image retrieval using binary hash codes. By integrating a multi-index hashing (MIH) mechanism with deep neural networks and introducing novel "balanced constraints," the method significantly speeds up search times while maintaining competitive retrieval accuracy compared to existing methods.

What Problem Does This Paper Address?

Nearest neighbor (NN) search is crucial for large-scale image retrieval. While deep learning has revolutionized image representation, efficiently searching through the vast number of binary hash codes generated by these models remains a challenge. Existing deep hashing methods often produce binary codes that are not uniformly distributed in the Hamming space. This non-uniformity leads to inefficient search, as many candidate codes might need to be examined, negating the speed benefits of hashing. The paper aims to bridge this gap by developing a deep hashing method that simultaneously learns powerful image representations and ensures uniformly distributed binary codes for fast and accurate retrieval.

Methods

The proposed approach, Deep Multi-Index Hashing (DMIH), builds upon the Multi-Index Hashing (MIH) technique. MIH partitions binary codes into multiple substrings, with each substring indexing a separate hash table, thereby accelerating search. The core innovation of DMIH lies in its integration of MIH within a deep neural network architecture and the introduction of two novel "balanced constraints" to address the non-uniformity issue:

  • Feature-Level Balancing: This constraint aims to make the bits within each substring of the binary code as uniformly distributed as possible. It enforces that the Hamming distances between binary codes in each substring are balanced.
  • Instance-Level Balancing: This constraint focuses on ensuring that the hash table buckets themselves are balanced. It penalizes buckets that contain too many candidate items, which would otherwise lead to slow search.

The architecture consists of a deep network (e.g., AlexNet) for feature extraction, followed by a "slice layer" that divides the intermediate features into multiple substrings, corresponding to the MIH structure. The similarity-preserving loss function is augmented with these two balancing constraints to learn both effective image representations and uniformly distributed binary codes.

Datasets

The paper evaluates its method on two widely-used benchmark datasets:

  • SVHN (Street View House Numbers): Contains over 600,000 images of house numbers with 10 classes.
  • NUS-WIDE: A large-scale dataset with 269,648 images and associated tags from Flickr, covering 81 concepts. For fair comparison, the authors selected 21 frequent labels, each with at least 5,000 images.

No new benchmarks were introduced.

Key Insights and Ideas

  • The "Curse of Non-Uniformity": The paper highlights that even powerful deep representations can lead to inefficient search if the resulting binary codes are not uniformly distributed in the Hamming space. This is a critical insight that motivates the proposed balancing mechanisms.
  • Synergy of Deep Learning and MIH: By embedding the MIH mechanism directly into a deep learning framework, DMIH achieves a more holistic optimization. This end-to-end approach allows for simultaneous learning of image representations and balanced hash codes, unlike previous methods that might apply rebalancing as a post-processing step.
  • Dual Balancing for Comprehensive Improvement: The introduction of both feature-level and instance-level balancing constraints addresses different facets of the non-uniformity problem, leading to more robust and efficient search. The effectiveness of each constraint can depend on the specific data distribution.

Key Results

The proposed DMIH method demonstrates significant improvements in search speed while maintaining comparable retrieval performance:

  • Speedup: DMIH achieves substantial speedups compared to linear scan and even a baseline deep hashing method (DeepHash). For example, on the SVHN dataset with 96-bit codes, DMIH achieves a speedup factor of 92.46 for 1-NN search, significantly outperforming DeepHash's 9.96. Similar impressive speedups are observed on the NUS-WIDE dataset.
  • Performance: The paper shows that DMIH achieves comparable Mean Average Precision (MAP) and precision-recall curves to baseline methods, indicating that the speed improvements do not come at the cost of retrieval accuracy.
  • Effectiveness of Constraints: Experiments show that both feature-level and instance-level constraints are beneficial, with their relative importance varying depending on the dataset. The instance-level constraint is particularly useful for SVHN, while the feature-level constraint is more impactful for NUS-WIDE.

Limitations and Future Work

  • Limitations: The paper acknowledges that the effectiveness of the balanced constraints can depend on the data distribution. While the proposed method shows strong results, it's possible that for certain datasets or feature representations, the non-uniformity might be less pronounced or require different balancing strategies.
  • Future Work: The authors plan to extend their work by applying DMIH to different network architectures and hashing methods to further explore the impact of the proposed balanced constraints. They also aim to accelerate the feature extraction process, which is a common bottleneck in deep learning-based retrieval systems.

Summary updated

Abstract

Similarity-preserving hashing is a widely used method for nearest neighbor search in large-scale image retrieval tasks. Considerable research has been conducted on deep-network-based hashing approaches to improve the performance. However, the binary codes generated from deep networks may be not uniformly distributed over the Hamming space, which will greatly increase the retrieval time. To this end, we propose a deep-network-based multi-index hashing (MIH) for retrieval efficiency. We first introduce the MIH mechanism into the proposed deep architecture, which divides the binary codes into multiple substrings. Each substring corresponds to one hash table. Then, we add the two balanced constraints to obtain more uniformly distributed binary codes: 1) balanced substrings, where the Hamming distances of each substring are equal for any two binary codes and 2) balanced hash buckets, where the sizes of each bucket are equal. Extensive evaluations on several benchmark image retrieval data sets show that the learned balanced binary codes bring dramatic speedups and achieve comparable performance over the existing baselines.
BibTeX
@article{lai2019improved,
  author = {Hanjiang Lai and Yan Pan and Si Liu and Zhenbin Weng and Jian Yin},
  title = {{Improved Search in Hamming Space Using Deep Multi-Index Hashing}},
  journal = {IEEE Trans. Circuits Syst. Video Technol.},
  year = {2019},
  url = {https://openreview.net/forum?id=GQ3b1SZxKD},
}
Figure