LayerLSB:基于分层局部敏感B树的最近邻搜索  

LayerLSB:Nearest Neighbors Search Based on Layered Locality Sensitive B-tree

作　　者：丁际文 刘卓锦 王家兴 张岩峰 于戈 DING Jiwen;LIU Zhuojin;WANG Jiaxing;ZHANG Yanfeng;YU Ge(School of Computer Science and Engineering,Northeastern University,Shenyang 110167,China)

机构地区：[1]东北大学计算机科学与工程学院,沈阳110167

出　　处：《计算机科学》2023年第4期32-39,共8页Computer Science

基　　金：国家自然科学基金(62072082);中央高校基本科研业务费(N2216015)。

摘　　要：最近邻搜索由于其广泛的应用已成为一个重要的研究课题。传统的空间索引结构,如R-tree和KD-tree,可以在低维空间中高效地返回准确的最近邻搜索结果,但不适用于高维空间。局部敏感B树(LSB)将数据点哈希到可排序的一维值,并将它们排列成树状结构,这在不影响结果质量的前提下极大地提高了传统局部敏感哈希(LSH)所需的空间和查询效率。但是,LSB并没有考虑到数据分布,它在均匀的数据分布设置中表现良好,但在数据倾斜时表现出了不稳定的性能。针对这个问题,文中提出了LayerLSB,通过探索哈希值的密度对密集范围内的哈希值进行重建,使其分布更均匀,从而提高查询效率。相比LSB,LayerLSB索引在数据分布方面变得更有针对性,并构建了多层结构,与简单的重新哈希方法相比,多层方法会通过仔细选择组数和哈希函数来保证搜索质量。实验结果表明,在达到相同查询精度的情况下,查询成本最多可降低为原来的44.6%。Nearest neighbor search has become a significant research problem due to its wide applications.Traditional spatial index structures such as R-tree and KD-tree can efficiently return accurate nearest neighbor search results in low-dimensional space,but they are not suitable for high-dimensional space.Locality sensitive B-tree(LSB)hashes data points to the sortable one-dimension values and arranges them in a tree-like structure,which dramatically improves the space and query efficiency of the previous locality sensitive hashing(LSH)implementations,without compromising the resulting quality.However,LSB fails to take data distribution into account.It performs well in a uniform data distribution setting,but exhibits unstable performance when the data are skewed.In response to this problem,this paper proposes LayerLSB,which reconstructs the hash values in a dense range by exploring the density of the hash values to make the distribution more uniform,so as to improve the query efficiency.Compared to LSB,LayerLSB indices become more targeted in terms of data distribution,and a multi-layered structure is constructed.Compared with the simple rehashing method,the multi-layered approach will still guarantee the search quality by carefully choosing the number of groups and hash functions.The results show that the query cost can be reduced to 44.6%of the original at most when achieving the same query accuracy.

关 键 词：最近邻搜索 分层结构 局部敏感哈希 局部敏感B树 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]