EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
M2LSH%3A基于LSH的高维数据近似最近邻查找算法 9 ^3 f" t3 O" u- X# Q& K9 I
摘要:在许多应用中, LSH(Locality Sensitive Hashing )以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本文提出了一种新的基于ISH 的解决方案(M2ISH,2 Layers Merging I.SH) ,对于数据分布不均匀的情况依然能得到一个比较好的查询效果.首先,将数据存放到具有计数功能的组合哈希向量表示的哈希桶中,然后通过二次哈希将这些桶号投影到一维空间,在此空间根据各个桶中存放的数据个数合并相邻哈希桶,使得新哈希桶中的数据量能够大致均衡.查询时仅访问有限个哈希桶,就能找到较优结果.本文给出了详细的理论分析,并通过实验验证了M2LSH的性能,不仅能减少访问时间,也可提高结果的正确率.
6 X9 j0 T; x3 T$ L$ a( x. c! {/ N关键词:近似最近邻;KNN查询;局部敏感哈希;高维数据# v# S# L& ~: S4 t
3 z/ p( V2 b% D1 ]9 Y1引言, Y; l2 r' H4 Y x
最近邻查询问题( nearest neighbor search problem)指在给定数据集中返回与查询对象距离最近的数据对象的问题.最近邻问题在不同领域都有广泛的应用,如:人工智能、信息检索、模式识别等.形式化地,最近邻查询指在给定有n个d维数据对象的数据集D中找到与5 W+ C M7 N% j# v
3 n7 r" v* a3 A& D
' d( [( r, C# |2 o8 y
5 f; t0 @8 R9 t; {6 C3 S | 
/1 
发表于 2021-5-28 10:12
收藏
淘帖
支持！
反对！