基于LSH的高维大数据k近邻搜索算法

发布时间：2017-10-20 22:40

  本文关键词：基于LSH的高维大数据k近邻搜索算法

  更多相关文章： 高维数据k近邻 局部敏感哈希 MapReduce 冲突计数排序

【摘要】：局部敏感哈希(LSH)及其变体是解决高维数据k近邻(k NN)搜索的有效算法.但是,随着数据规模的日趋庞大,传统的集中式LSH算法结构已经不能够满足大数据时代的需求.本文分析传统LSH方案的不足之处,拓展AND-OR结构,提出通过索引而不比较原始数据直接实现高维大数据k近邻搜索算法C2SLSH.理论分析和实验证明,C2SLSH在分布式平台下具有稳定的可扩展性,在保证同等精确率的情况下,处理速度大约是现有方法的3倍.
【作者单位】： 宁波大学信息科学与工程学院;
【关键词】： 高维数据k近邻 局部敏感哈希 MapReduce 冲突计数排序
【基金】：国家自然科学基金(No.61472194,No.61572266) 浙江省自然科学基金(No.LY13F020040) 宁波市自然科学基金(No.2014A610023) “信息与通信工程”浙江省重中之重学科开放基金
【分类号】：TP311.13
【正文快照】： 1引言随着网络规模的扩大,数据,尤其是高维数据呈爆炸式增长[1~3].从这些海量数据中搜索近似对象是很多应用的关键,如近似检索、推荐系统、k近邻问题等.通过构造索引,如R-tree[4]、K-D tree[5]等,可快速找到查询对象的近邻或近似对象.然而,随着数据维度的增加,这些算法的效率，

本文编号：1069818