An Efficient Feature Hashing Method Based On Markov Graph Model

With the rapid development of Internet, social network and video website have grasped more and more people’s eyes. With the explosion growth of the multimedia data, how to get or management this data has get more and more attention for many research committees. The fundamental retrieval methods cannot be satisfied for people’s need, due to the representation of these data are always high dimension and large scale. Therefore, large scale machine learning have been popular for solving these problems. And hashing is becoming increasingly popular for efficient retrieval for massive data. Hashing is a good technology which can find the best binary codes for original data representations, which preserve the similarities in Hamming space. There are two advantages: firstly, using hashing method can reduce the storage for large scale database; secondly, the Hamming distance can be calculated by binary codes. So hashing is always used in large scale data retrieval and managements.Nowadays, many algorithms of hashing are used random projection to make the similarity consistent between data points from original feature space to Hamming space. But these methods always get better performance for higher hash bits. Therefore, a lot of learning based hashing methods have been proposed.In this paper, we propose a novel hashing algorithm called Markov Random Walk Hashing, which can be efficient used in large scale data retrieval. According to Markov graph clustering, we construct the feature graph which can be present the relationship between all data points. Then random walk is done on the feature graph to receive the robust affinity matrix. At last we use laplacian eigemap method, and the binary hashing code can be generated by linear projection quickly.Due to the high time cost of graph construction, random walk on the graph and the eigemap, we propose a Landmark based random walk method for hash learning. Analysis and experimental both show that the new fast random walk hashing have higher performance than before.Experimental comparisons on four large scale public data set have demonstrate that our proposed method out performs the state-of-the- art methods.