On the Evaluation Metric for Hashing

Qing-Yuan Jiang, Ming-Wei Li, Wu-Jun LiarXiv 2019 · OpenReview

Abstract Due to its low storage cost and fast query speed, hashing has been widely used for large-scale approximate nearest neighbor (ANN) search. Bucket search, also called hash lookup, can achieve fast query speed with a sub-linear time cost based on the inverted index table constructed from hash codes. Many metrics have been adopted to evaluate hashing algorithms. However, all existing metrics are improper to evaluate the hash codes for bucket search. On one hand, all existing metrics ignore the retrieval time cost which is an important factor reflecting the performance of search. On the other hand, some of them, such as mean average precision (MAP), suffer from the uncertainty problem as the ranked list is based on integer-valued Hamming distance, and are insensitive to Hamming radius as these metrics only depend on relative Hamming distance. Other metrics, such as precision at Hamming radius R, fail to evaluate global performance as these metrics only depend on one specific Hamming radius. In this paper, we first point out the problems of existing metrics which have been ignored by the hashing community, and then propose a novel evaluation metric called radius aware mean average precision (RAMAP) to evaluate hash codes for bucket search. Furthermore, two coding strategies are also proposed to qualitatively show the problems of existing metrics. Experiments demonstrate that our proposed RAMAP can provide more proper evaluation than existing metrics.

Introduction: The Blind Spots of Hashing Evaluation

Hashing is a cornerstone technique for fast approximate nearest neighbor (ANN) search, converting high-dimensional data into compact binary codes. For real-world applications, "bucket search" (or hash lookup) is the preferred retrieval method. It utilizes an inverted index to probe buckets within increasing Hamming radii of a query code, achieving sub-linear search times.

Despite its prevalence, the metrics used to evaluate hashing algorithms—primarily Mean Average Precision (MAP) and Precision/Recall at radius $R$—fail to capture the practical performance of bucket search. This paper identifies four critical flaws in these standard metrics:

  1. Time Blindness: Standard metrics ignore the exponential growth in time cost as the search radius expands.
  2. The Uncertainty Problem: Because Hamming distances are discrete integers, many items share the same distance, leading to arbitrary tie-breaking in ranked lists and unstable MAP scores.
  3. Relative vs. Absolute Distance: MAP evaluates the relative ordering of items but ignores the absolute Hamming distance. A model that places neighbors at distance 10 is scored the same as one that places them at distance 0, despite the massive difference in retrieval time.
  4. Local vs. Global Accuracy: Precision@R treats all items within a fixed radius equally, failing to reward models that cluster neighbors closer to the query.
Illustration of Hash Lookup based Retrieval and its associated time costs at increasing Hamming distances.

The Flaws Visualized

The "Uncertainty Problem" arises because items within the same Hamming ball are essentially unordered. As shown in Figure 2, different coding strategies can result in identical relative rankings but vastly different retrieval efficiencies. This highlights why relative distance metrics like MAP are insufficient for evaluating real-world utility.

Comparison of two coding strategies illustrating the uncertainty problem and the impact of absolute Hamming distance on retrieval.

Radius Aware Mean Average Precision (RAMAP)

To address these deficiencies, the authors propose Radius Aware Mean Average Precision (RAMAP). Unlike MAP, which relies on rank, RAMAP calculates precision at each Hamming radius $r$ (up to a maximum $R$) and incorporates a time-cost penalty.

This penalty is proportional to the number of buckets that must be searched at that radius, calculated as $\binom{Q}{r}$ for a code length $Q$. By averaging these penalized precisions, RAMAP rewards models that cluster true neighbors at very small absolute Hamming distances, directly reflecting their utility in a bucket search system.

Experimental Validation

The authors designed two specific coding strategies to expose the failures of traditional metrics:

  • Heuristic Strategy: Redundant bits (matching or mismatched) were appended to standard hash codes. This increases search time without adding information. While MAP and Precision@R remained unchanged, RAMAP correctly penalized the redundant codes.
  • Learning-based Strategy ($m$-DSH): The authors modified Deep Squared Hashing (DSH) to intentionally map similar items to a specific Hamming distance $m$ (e.g., 4, 8, or 12).

On the CIFAR-10 dataset, the results were striking. Standard MAP scores for DSH, 4-DSH, 8-DSH, and 12-DSH were virtually identical, suggesting they were equally effective. However, real-world retrieval time measurements showed that 12-DSH was exponentially slower than standard DSH. RAMAP was the only metric that correctly ranked these models (DSH > 4-DSH > 8-DSH > 12-DSH), matching the empirical time measurements.

Conclusion

Standard evaluation metrics for hashing are fundamentally disconnected from the operational realities of bucket search. By ignoring time costs and absolute distances, metrics like MAP can lead researchers to favor models that are practically unusable in production. RAMAP provides a more robust, time-aware alternative that aligns evaluation with real-world retrieval performance.

Summary updated

Abstract

Due to its low storage cost and fast query speed, hashing has been widely used for large-scale approximate nearest neighbor (ANN) search. Bucket search, also called hash lookup, can achieve fast query speed with a sub-linear time cost based on the inverted index table constructed from hash codes. Many metrics have been adopted to evaluate hashing algorithms. However, all existing metrics are improper to evaluate the hash codes for bucket search. On one hand, all existing metrics ignore the retrieval time cost which is an important factor reflecting the performance of search. On the other hand, some of them, such as mean average precision (MAP), suffer from the uncertainty problem as the ranked list is based on integer-valued Hamming distance, and are insensitive to Hamming radius as these metrics only depend on relative Hamming distance. Other metrics, such as precision at Hamming radius R, fail to evaluate global performance as these metrics only depend on one specific Hamming radius. In this paper, we first point out the problems of existing metrics which have been ignored by the hashing community, and then propose a novel evaluation metric called radius aware mean average precision (RAMAP) to evaluate hash codes for bucket search. Furthermore, two coding strategies are also proposed to qualitatively show the problems of existing metrics. Experiments demonstrate that our proposed RAMAP can provide more proper evaluation than existing metrics.
BibTeX
@misc{jiang2019evaluation,
  author = {Qing-Yuan Jiang and Ming-Wei Li and Wu-Jun Li},
  title = {{On the Evaluation Metric for Hashing}},
  year = {2019},
  eprint = {1905.10951},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.10951},
}
Figure