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