Variable-Length Hashing

Honghai Yu, Pierre Moulin, Hong Wei Ng, Xiaoli Li

Introduction

Large-scale similarity search is a cornerstone of modern information retrieval, enabling applications from image search to recommendation systems. To handle billions of entries, hashing techniques map high-dimensional data into compact binary strings. However, traditional hashing methods often struggle with a trade-off between storage efficiency and retrieval accuracy. This paper presents Variable-Length Hashing (VLH) and Block K-means Hashing (B-KMH), a dual approach that leverages redundancy to improve accuracy while using lossless compression to maintain a minimal storage footprint.

The Challenge: Redundancy and Rigidity

Most state-of-the-art hashing algorithms produce bits that are inherently correlated. This correlation leads to two primary issues:

  1. Storage Inefficiency: Redundant bits waste expensive memory and disk space.
  2. Distance Rigidity: Methods like K-means Hashing (KMH) use a fixed number of bits to represent clusters. This rigid mapping often fails to capture the true Euclidean distances between data points in the Hamming space.

Instead of viewing redundancy as a flaw, the authors propose a paradigm shift: use redundancy to better approximate data geometry, then compress it away for storage.

Methods

Variable-Length Hashing (VLH)

VLH is a framework designed to compress correlated hash codes without sacrificing search performance. Unlike standard entropy coding (e.g., Huffman), which becomes intractable for long codes, VLH partitions a $B$-bit code into $M$ smaller substrings. Each substring is compressed independently using nonsingular codes. Because these substrings are stored in separate hash tables within a Multi-Index Hashing (MIH) structure, the "prefix-free" requirement of standard coding is relaxed, allowing for tighter compression.

Block K-means Hashing (B-KMH)

B-KMH builds on the flexibility of VLH by deliberately adding "smart" redundancy. It uses more bits ($\beta$) than strictly necessary ($b$) to represent cluster centers. By increasing the bit-budget, the algorithm can find binary IDs that more accurately reflect the Euclidean distances between cluster centers, minimizing "Affinity Error."

Experimental Results

The proposed methods were evaluated on the SIFT1M and GIST1M benchmarks.

Compression Efficiency

VLH consistently outperforms standard Huffman coding. As shown in Figure 1, the expected code length for VLH is significantly lower than that of Huffman coding across various numbers of substrings ($M$). By jointly compressing more bits (smaller $M$), VLH achieves higher compression ratios.

Expected code length comparison and substring variation.

Retrieval Accuracy

On the SIFT1M dataset, B-KMH improved Recall@1000 from 0.90 to 0.97 compared to standard KMH. On GIST1M with 128-bit codes, it achieved perfect recall at $N=800$, outperforming established methods like ITQ and LSH.

Computational Overhead

A critical concern for any compression scheme is the decoding time during search. The authors found that the overhead of VLH is negligible. As illustrated in Figure 2, the time required for decoding is actually less than the time spent on Hamming distance computations. This ensures that storage savings do not come at the cost of search latency.

Analysis of candidate test cost and decoding overhead.

Conclusion

Variable-Length Hashing demonstrates that redundancy in hash codes can be a powerful tool rather than a hindrance. By combining B-KMH's ability to capture complex data geometries with VLH's efficient storage, the framework provides a scalable solution for high-accuracy similarity search. Future work may explore the application of VLH to other hashing architectures beyond K-means.

Summary updated

Abstract

Hashing has emerged as a popular technique for large-scale similarity search. Most learning-based hashing methods generate compact yet correlated hash codes. However, this redundancy is storage-inefficient. Hence we propose a lossless variable-length hashing (VLH) method that is both storage- and search-efficient. Storage efficiency is achieved by converting the fixed-length hash code into a variable-length code. Search efficiency is obtained by using a multiple hash table structure. With VLH, we are able to deliberately add redundancy into hash codes to improve retrieval performance with little sacrifice in storage efficiency or search complexity. In particular, we propose a block K-means hashing (B-KMH) method to obtain significantly improved retrieval performance with no increase in storage and marginal increase in computational cost.
BibTeX
@misc{yu2016variable,
  author = {Honghai Yu and Pierre Moulin and Hong Wei Ng and Xiaoli Li},
  title = {{Variable-Length Hashing}},
  year = {2016},
  eprint = {1603.05414},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1603.05414},
}
Figure