On Large-Scale Retrieval: Binary or n-ary Coding?

Mahyar Najibi, Mohammad Rastegari, Larry S. DavisarXiv 2015 · OpenReview

Abstract

The growing amount of data available in modern-day datasets makes the need to efficiently search and retrieve information. To make large-scale search feasible, Distance Estimation and Subset Indexing are the main approaches. Although binary coding has been popular for implementing both techniques, n-ary coding (known as Product Quantization) is also very effective for Distance Estimation. However, their relative performance has not been studied for Subset Indexing. We investigate whether binary or n-ary coding works better under different retrieval strategies. This leads to the design of a new n-ary coding method, "Linear Subspace Quantization (LSQ)" which, unlike other n-ary encoders, can be used as a similarity-preserving embedding. Experiments on image retrieval show that when Distance Estimation is used, n-ary LSQ outperforms other methods. However, when Subset Indexing is applied, interestingly, binary codings are more effective and binary LSQ achieves the best accuracy.

Introduction

In the era of "Big Data," performing an exact Nearest Neighbor search is computationally prohibitive. To address this, researchers utilize Approximate Nearest Neighbor (ANN) search strategies, primarily categorized into two approaches:

  1. Fast Distance Estimation: This involves approximating the distance between points using compressed codes to bypass expensive floating-point calculations.
  2. Fast Subset Indexing: This utilizes data structures like hash tables or trees to prune the search space, focusing only on a promising subset of the database.

While binary coding is the industry standard for these tasks, $n$-ary coding (Product Quantization) has emerged as a powerful alternative for distance estimation. This paper investigates the performance of these coding styles under the Subset Indexing strategy and introduces a novel encoder, Linear Subspace Quantization (LSQ), designed to serve as a general-purpose similarity-preserving embedding.

Methodology: Linear Subspace Quantization (LSQ)

Existing coding methods generally fall into two categories: Subspace Clustering and Subspace Reduction. Subspace Clustering (e.g., Product Quantization) divides the feature space into independent subspaces and clusters each. Subspace Reduction (e.g., Iterative Quantization) reduces dimensionality before discretizing dimensions into bins.

Comparison of Subspace Clustering and Subspace Reduction techniques for feature discretization.

LSQ is proposed as a Subspace Reduction method. Unlike traditional $n$-ary encoders that assume subspace independence, LSQ learns a linear transformation that fits a quantized hyper-cube to the data distribution. The learning process involves a two-step iterative optimization: fixing the mapping to update the codebook (reconstruction), and then fixing the codebook to update the mapping via a Moore-Penrose pseudoinverse. Because LSQ is based on subspace reduction, the resulting discrete codes maintain a strong correlation with Euclidean distances in the original space, allowing them to be used directly as feature vectors.

Experimental Setup

The performance of LSQ was evaluated against standard benchmarks:

  • GIST1M: 1 million base feature vectors.
  • CIFAR10: 60,000 small images using raw pixel features.
  • ImageNet (ILSVRC2012): 500,000 training samples using deep features extracted via a ConvNet.

Key Insights and Results

The research reveals a critical "Right Tool for the Job" paradox: the optimal coding method is contingent upon the retrieval strategy. While $n$-ary coding (like LSQ) minimizes reconstruction error and dominates in Distance Estimation, binary coding is superior at preserving the relative ordering of neighbors, making it more effective for Subset Indexing.

Recall@R performance for 256-bit codes across CIFAR10, GIST1M, and ImageNet datasets, comparing LSQ variants against CK-means.

Key empirical findings include:

  • Distance Estimation: LSQ consistently outperformed CK-means and various binary coding methods across all datasets in terms of Recall@R.
  • Subset Indexing: Binary versions of LSQ achieved the highest accuracy, demonstrating that binary codes are more robust for hash-table-style lookups.
  • Efficiency: LSQ converges faster than competing algorithms like ITQ or OK-means and achieves a lower final reconstruction error.

Conclusion

While $n$-ary codes provide superior quantization accuracy, they are surprisingly less effective for ANN search when subset indexing is applied. This suggests that the geometric properties required for reconstruction differ from those required for efficient indexing. Future work may explore non-linear mapping functions or hybrid coding methods that attempt to bridge the gap between reconstruction accuracy and indexing efficiency.

Summary updated

Abstract

The growing amount of data available in modern-day datasets makes the need to efficiently search and retrieve information. To make large-scale search feasible, Distance Estimation and Subset Indexing are the main approaches. Although binary coding has been popular for implementing both techniques, n-ary coding (known as Product Quantization) is also very effective for Distance Estimation. However, their relative performance has not been studied for Subset Indexing. We investigate whether binary or n-ary coding works better under different retrieval strategies. This leads to the design of a new n-ary coding method, "Linear Subspace Quantization (LSQ)" which, unlike other n-ary encoders, can be used as a similarity-preserving embedding. Experiments on image retrieval show that when Distance Estimation is used, n-ary LSQ outperforms other methods. However, when Subset Indexing is applied, interestingly, binary codings are more effective and binary LSQ achieves the best accuracy.
BibTeX
@misc{najibi2015large,
  author = {Mahyar Najibi and Mohammad Rastegari and Larry S. Davis},
  title = {{On Large-Scale Retrieval: Binary or n-ary Coding?}},
  year = {2015},
  eprint = {1509.06066},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1509.06066},
}
Figure