基于LSH的中文文本快速检索  

Fast Chinese Text Search Based on LSH

作　　者：蔡衡[1] 李舟军[1] 孙健 李洋 

机构地区：[1]北京航空航天大学计算机学院,北京100083 [2]新浪网技术(中国)有限公司研发中心-搜索-新技术部,北京100191

出　　处：《计算机科学》2009年第8期201-204,230,共5页Computer Science

基　　金：国家自然科学基金项目(60573057;90718017)资助

摘　　要：目前,高维数据的快速检索问题已经受到越来越多的关注。当向量空间的维度高于10时,R-tree,Kd-tree,SR-tree的检索效率反而不如线性检索,而位置敏感的哈希(Locality Sensitive Hashing,缩写为LSH)算法成功地解决了高维近邻数据的快速检索问题,因而受到国内外学术界的高度关注。首先介绍了LSH算法的基本原理和方法,然后使用多重探测的方法对二进制向量的LSH算法做了进一步改进。最后实现了这两种LSH算法,并通过详细的实验验证表明:在改进后的算法中,通过增加偏移量可以提高检索的召回率,而在不提高时间复杂度的情况下则可降低空间复杂度。The query of High dimension data attracts more and more attention. When dimension of a space vector is higher than 10, R-tree, Kd-tree, SR-tree and Quadtrees perform worse than linear query. However, Locality Sensitive hashing （LSH） algorithm successfully deals with this problem. Nowadays LSH is playing a more and more important role in high dimension query. In the paper, the basic algorithm and principle of LSH were introduced firstly, then binary vector LSH Search Algorithm was improved by means of the multi-probe. Finally, we implemented the two kinds of LSH algorithms. The experience we have designed verified that the revised algorithm has better performance than the original one in two aspects. On the one hand, as the increment of setover, the proportion of retrial recall enlarges. On the other hand, the complexity of space decreases without the change of time complexity.

关 键 词：高维数据 相似性检索 位置敏感的哈希 近邻 多重探测 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP391[自动化与计算机技术—计算机科学与技术]