http://www.jsjkx.comDOI:10.11896/jsjkx.220600078到稿日期:2022-06-08返修日期:2022-10-19基金项目:国家自然科学基金(62072082);中央高校基本科研业务费(N2216015)ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(62072082)andFundamentalResearchFundsfortheCentralUni-versities(N2216015).通信作者:张岩峰(zhangyf@mail.neu.edu.cn)LayerLSB:基于分层局部敏感B树的最近邻搜索丁际文刘卓锦王家兴张岩峰于戈东北大学计算机科学与工程学院沈阳110167(djw@mail.neu.edu.cn)摘要最近邻搜索由于其广泛的应用已成为一个重要的研究课题。传统的空间索引结构,如R-tree和KD-tree,可以在低维空间中高效地返回准确的最近邻搜索结果,但不适用于高维空间。局部敏感B树(LSB)将数据点哈希到可排序的一维值,并将它们排列成树状结构,这在不影响结果质量的前提下极大地提高了传统局部敏感哈希(LSH)所需的空间和查询效率。但是,LSB并没有考虑到数据分布,它在均匀的数据分布设置中表现良好,但在数据倾斜时表现出了不稳定的性能。针对这个问题,文中提出了LayerLSB,通过探索哈希值的密度对密集范围内的哈希值进行重建,使其分布更均匀,从而提高查询效率。相比LSB,LayerLSB索引在数据分布方面变得更有针对性,并构建了多层结构,与简单的重新哈希方法相比,多层方法会通过仔细选择组数和哈希函数来保证搜索质量。实验结果表明,在达到相同查询精度的情况下,查询成本最多可降低为原来的44.6%。关键词:最近邻搜索;分层结构;局部敏感哈希;局部敏感B树中图法分类号TP319LayerLSB:NearestNeighborsSearchBasedonLayeredLocalitySensitiveB-treeDINGJiwen,LIUZhuojin,WANGJiaxing,ZHANGYanfengandYUGeSchoolofComputerScienceandEngineering,NortheasternUniversity,Shenyang110167,ChinaAbstractNearestneighborsearchhasbecomeasignificantresearchproblemduetoitswideapplications.Traditionalspatialin-dexstructuressuchasR-treeandKD-treecanefficientlyreturnaccuratenearestneighborsearchresultsinlow-dimensionalspace,buttheyarenotsuitableforhigh-dimensionalspace.LocalitysensitiveB-tree(LSB)hashesdatapointstothesortableone-dimensionvaluesandarrangestheminatree-likestructure,whichdramaticallyimprovesthespaceandqueryefficiencyofthepreviouslocalitysensitivehashing(LSH)implementations,withoutcompromisingtheresultingquality....
