The ordinal relation preserving binary codes

Author-Highlights
• An effective and efficient binary coding framework which enjoys the merits of lookup-based and hamming-based methods is proposed.
• Relative error is proposed to preserve the relative sensitivity.
• The effective tangent planes are adopted as hashing functions to avoid computing the complex classification problem.
• The encoding error guarantees that the selected hashing functions have good performance.

Hashing algorithm has been widely used for efficient approximate nearest neighbor (ANN) search. Learning optimal hashing functions has been given focus and it is still a challenge. This paper aims to effectively and efficiently generate relative similarity preserving binary codes. Most existing hashing methods try to preserve the locality similarity by preserving direct distance similarity, while ignoring the relative similarity which advantages in ANN search. In this paper, this issue is solved by proposing the relative error which emphasizes that the ordinal relations in Hamming space and Euclidean space should be consistent with each other. We learn hashing projection functions via two steps. The first step adopts the lookup-based mechanism to find the optimal binary codes of training data, which can preserve the relative similarity and simultaneously adapt to data distribution. The binary codes in the first step are considered as supervision information in the second step. The objective of the second step is to learn hashing projection functions which can efficiently regenerate the binary codes in the first step. Aim to be in accordance with the property of data distribution, the hyper internal tangent planes of two specified spheres are chosen as hashing projection functions. Assisted by these projection functions, the time complexity of encoding process is greatly reduced. Experimental results on four public data sets demonstrate that our method outperforms many other state-of-the-art methods.