Abstract: Hashing coding is becoming increasingly popular for efficient nearest neighbor search in massive database, due to its high efficiency. However, the exiting hashing methods cannot achieve a satisfied performance with low hash bits because of less original information. To address this problem, this paper proposes a novel method called hashing with Markov random walk graph. Firstly, the method generates sparse representation for high dimensional vectors, then builds the semantic network between the sparse coding by Markov random walk. After that the projection function can be found by Laplacian eigenmap method and the binary hashing coding can be generated by linear projection quickly. Experimental comparisons on two large datasets demonstrate that the proposed method outperforms the state-of-the-art methods.

Key words: nearest neighbor search, Markov network, Laplacian eigenmap, hashing coding

摘要： 基于哈希编码的算法，由于其高效性，已经成为海量数据高维特征最近邻搜索的研究热点。目前存在的普遍问题是，当哈希编码长度较低时，原始特征信息保留不是很充分，从而导致检索结果不理想。为了解决这一问题，提出了一种基于Markov网络的有效哈希编码算法。该算法首先根据稀疏编码策略进行特征重构，通过Markov随机游走的方式构建特征之间的语义网络关系图，然后根据Laplacian特征映射求出投影函数，最后进行快速的线性投影二值化编码。在公开数据集上与主流算法进行了性能比较，实验结果表明该算法具备良好的检索性能。

关键词: 最近邻搜索, Markov网络, Laplacian特征映射, 哈希编码