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