面向Top-k快速查询的层次化LSH索引方法

被引：1

作者：

罗雄才 ^{[1
]}

高军 ^{[2
]}

机构：

[1] 北京大学信息科学技术学院

[2] 高可信软件技术教育部重点实验室(北京大学)

来源：

计算机研究与发展 | 2015年 / S1期

关键词：

层次化局部敏感哈希; Minhash; Top-k查询; 相似度图; 三角不等式;

D O I：

暂无

中图分类号：

TP391.3 [检索机];

学科分类号：

081203 ; 0835 ;

摘要：

局部敏感哈希(locality sensitive hashing,LSH)用于在海量高维数据中检索相似的数据项,它能高效地返回相似度大于用户给定阈值的数据对.但是,由于需要设置固定阈值,LSH无法直接处理Top-k相似查询.传统LSH索引算法需要设置一系列阈值,分别建立索引,时间和空间代价较大.提出了一种层次化的LSH索引算法,通过动态构建层次化相似度图,充分利用三角不等式,减少不必要的索引构建代价.具体来讲,首先通过高阈值构建相似度图,将高度相似的数据点抽象成"超点",再在"超点"上构建低阈值的相似度图.查询时,首先查询高阈值相似度图;数量不足时再查询低阈值相似度图.实验表明,相比传统LSH算法,本文方法在构建索引的时间和空间代价上减小一个数量级,查询更加高效.

引用

页码：56 / 63

页数：8