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