Comparing apples to apples in the evaluation of binary coding methods
This work highlights overlooked evaluation practices in binary coding research, potentially affecting researchers and practitioners in information retrieval and machine learning, though it is incremental as it focuses on methodological improvements rather than new algorithms.
The paper addresses methodological issues in evaluating unsupervised binary coding methods for nearest neighbor search, showing that when fair comparison conditions are applied, simple methods like LSH and ITQ often outperform recent state-of-the-art methods such as MDSH and OK-means.
We discuss methodological issues related to the evaluation of unsupervised binary code construction methods for nearest neighbor search. These issues have been widely ignored in literature. These coding methods attempt to preserve either Euclidean distance or angular (cosine) distance in the binary embedding space. We explain why when comparing a method whose goal is preserving cosine similarity to one designed for preserving Euclidean distance, the original features should be normalized by mapping them to the unit hypersphere before learning the binary mapping functions. To compare a method whose goal is to preserves Euclidean distance to one that preserves cosine similarity, the original feature data must be mapped to a higher dimension by including a bias term in binary mapping functions. These conditions ensure the fair comparison between different binary code methods for the task of nearest neighbor search. Our experiments show under these conditions the very simple methods (e.g. LSH and ITQ) often outperform recent state-of-the-art methods (e.g. MDSH and OK-means).