面向近邻搜索的马尔科夫图哈希算法  

Efficient Hashing Method Based on Markov Graph for Nearest Neighbor Search

作　　者：刘弘[1] 江爱文[1] 王明文[1] 万剑怡[1] 

机构地区：[1]江西师范大学计算机信息工程学院,南昌330022

出　　处：《计算机科学与探索》2015年第7期861-868,共8页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金;江西省自然科学基金~~

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

关 键 词：最近邻搜索 MARKOV网络 Laplacian特征映射 哈希编码 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]