Adaptive hash retrieval with kernel based similarity. (March 2018)

• Record Type: Journal Article
• Authors: Bai, Xiao; Yan, Cheng; Yang, Haichuan; Bai, Lu; Zhou, Jun; Hancock, Edwin Robert
• Is Part Of: Pattern recognition. Volume 75(2018:Mar.)
• Page Start: 136
• Page End: 148
• Publication Date: 2018-03
• Subjects: Hashing -- K-NN -- Kernel -- Binary indexing -- Normalized Euclidean distance; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.03.020
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We explore the idea of using normalization on the Gaussian kernel, and use this to construct a new similarity function which gives consistent retrieval results. The normalization takes the local distribution of data into consideration, and is suitable for k nearest neighbour search. This new similarity function is proved to give a positive semidefinitive (PSD) kernel. We present two unsupervised hashing methods which aim at reconstructing the kernel function using binary codes. The first method takes the global similarity of measure given by the kernel function into consideration. The second method is local and focuses on the similarity of pairs of data and can better capture semantically meaningful manifold structure. Both of these hashing methods give a training time which is linear with respect to the size of the training set, and gives a constant time for indexing using the proposed hash function. Moreover, we present a supervised hashing scheme based on subspace learning to improve semantic retrieval performance. Our third and final contribution is to make use of supervised information (class labels) based on the former unsupervised hashing framework to achieve semantically better results. Abstract: Indexing methods have been widely used for fast data retrieval on large scale datasets. When the data are represented by high dimensional vectors, hashing is often used as an efficient solution for approximate similarity search. When a retrieval task does not involve supervised training data, most hashing methods aim at preserving data similarity defined by a distance metric on the feature vectors. Hash codes generated by these approaches normally maintain the Hamming distance of the data in accordance with the similarity function, but ignore the local details of the distribution of data. This objective is not suitable for k-nearest neighbor search since the similarity to the nearest neighbors can vary significantly for different data samples. In this paper, we present a novel adaptive similarity measure which is consistent with k-nearest neighbor search, and prove that it leads to a valid kernel if the original similarity function is a kernel function. Next we propose a method which calculates hash codes using the kernel function. With a low-rank approximation, our hashing framework is more effective than existing methods that preserve similarity over an arbitrary kernel. The proposed similarity function, hashing framework, and their combination demonstrate significant improvement when compared with several alternative state-of-the-art methods.