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

被引：12

作者：

蔡衡 ^{[1
]}

李舟军 ^{[1
]}

孙健 ^{[2
]}

李洋 ^{[2
]}

机构：

[1] 北京航空航天大学计算机学院

[2] 新浪网技术(中国)有限公司研发中心-搜索-新技术部

来源：

计算机科学 | 2009年 / 36卷 / 08期

关键词：

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

D O I：

暂无

中图分类号：

TP391.3 [检索机];

学科分类号：

081203 ; 0835 ;

摘要：

目前,高维数据的快速检索问题已经受到越来越多的关注。当向量空间的维度高于10时,R-tree,Kd-tree,SR-tree的检索效率反而不如线性检索,而位置敏感的哈希(Locality Sensitive Hashing,缩写为LSH)算法成功地解决了高维近邻数据的快速检索问题,因而受到国内外学术界的高度关注。首先介绍了LSH算法的基本原理和方法,然后使用多重探测的方法对二进制向量的LSH算法做了进一步改进。最后实现了这两种LSH算法,并通过详细的实验验证表明:在改进后的算法中,通过增加偏移量可以提高检索的召回率,而在不提高时间复杂度的情况下则可降低空间复杂度。

引用

页码：201 / 204+230 +230

页数：5

共 3 条

[1]

A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[C .2 R Weber,H Schek,S Blott. The 24th Int’l Conf on Very Large Data Bases . 1998

[2]

Randomized Algorithms andNLP:Using Locality Sensitive Hash Function for High SpeedNoun Clustering .2 Ravichandran D,Pantel P,Hovy E. Information Sciences Institute Universityof Southern California . 2004

[3]

MultiProbe LSH:Efficient Indexing for High Dimensional Similarity Search .2 Qin L,Josephson W,Wang Zhe,et al. Very large data bases archive proceedings Of the 33rd international conference on very large data bases . 2007

← 1 →