文献类型：期刊文章

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

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

出　　处：《计算机科学》

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

年　　份：2009

卷　　号：36

期　　号：8

起止页码：201-204

语　　种：中文

收录情况：BDHX、BDHX2008、CSA、CSCD、CSCD2011_2012、IC、JST、RCCSE、UPD、ZGKJHX、核心刊

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

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

分 类 号：TP311.13] TP391[计算机类]