EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
M2LSH%3A基于LSH的高维数据近似最近邻查找算法 2 ~. q. Q7 d6 j7 m
摘要:在许多应用中, LSH(Locality Sensitive Hashing )以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本文提出了一种新的基于ISH 的解决方案(M2ISH,2 Layers Merging I.SH) ,对于数据分布不均匀的情况依然能得到一个比较好的查询效果.首先,将数据存放到具有计数功能的组合哈希向量表示的哈希桶中,然后通过二次哈希将这些桶号投影到一维空间,在此空间根据各个桶中存放的数据个数合并相邻哈希桶,使得新哈希桶中的数据量能够大致均衡.查询时仅访问有限个哈希桶,就能找到较优结果.本文给出了详细的理论分析,并通过实验验证了M2LSH的性能,不仅能减少访问时间,也可提高结果的正确率.
! L2 o' R( ^# n: W关键词:近似最近邻;KNN查询;局部敏感哈希;高维数据$ b" z7 e( f3 \) d. {6 v3 w9 l8 A
. N; _6 E: U6 Y$ |( H, I* d
1引言 D1 T* b/ f+ _9 f5 I
最近邻查询问题( nearest neighbor search problem)指在给定数据集中返回与查询对象距离最近的数据对象的问题.最近邻问题在不同领域都有广泛的应用,如:人工智能、信息检索、模式识别等.形式化地,最近邻查询指在给定有n个d维数据对象的数据集D中找到与+ v) T2 Q. M) _/ S+ D/ z7 s S
/ z6 ~9 L0 P8 ^. Z/ t) ?
% ~8 b3 u# I) ]' u) `2 q' }2 v
" t* h$ ?6 S: m1 G( M% l | 
/1 
发表于 2021-5-28 10:12
收藏
淘帖
支持！
反对！