1、h t t p:/ww w.j s j k x.c o mD O I:1 0.1 1 8 9 6/j s j k x.2 2 0 6 0 0 0 7 8到稿日期:2 0 2 2-0 6-0 8 返修日期:2 0 2 2-1 0-1 9基金项目:国家自然科学基金(6 2 0 7 2 0 8 2);中央高校基本科研业务费(N 2 2 1 6 0 1 5)T h i sw o r kw a ss u p p o r t e db y t h eN a t i o n a lN a t u r a l S c i e n c eF o u n d a t i o no fC h i n a(6 2 0
2、 7 2 0 8 2)a n dF u n d a m e n t a lR e s e a r c hF u n d s f o r t h eC e n t r a lU n i-v e r s i t i e s(N 2 2 1 6 0 1 5).通信作者:张岩峰(z h a n g y f m a i l.n e u.e d u.c n)L a y e r L S B:基于分层局部敏感B树的最近邻搜索丁际文刘卓锦王家兴张岩峰于 戈东北大学计算机科学与工程学院 沈阳1 1 0 1 6 7(d j wm a i l.n e u.e d u.c n)摘 要 最近邻搜索由于其广泛的应用已成为一
3、个重要的研究课题。传统的空间索引结构,如R-t r e e和K D-t r e e,可以在低维空间中高效地返回准确的最近邻搜索结果,但不适用于高维空间。局部敏感B树(L S B)将数据点哈希到可排序的一维值,并将它们排列成树状结构,这在不影响结果质量的前提下极大地提高了传统局部敏感哈希(L S H)所需的空间和查询效率。但是,L S B并没有考虑到数据分布,它在均匀的数据分布设置中表现良好,但在数据倾斜时表现出了不稳定的性能。针对这个问题,文中提出了L a y e r L S B,通过探索哈希值的密度对密集范围内的哈希值进行重建,使其分布更均匀,从而提高查询效率。相比L S B,L a y e
4、 r L S B索引在数据分布方面变得更有针对性,并构建了多层结构,与简单的重新哈希方法相比,多层方法会通过仔细选择组数和哈希函数来保证搜索质量。实验结果表明,在达到相同查询精度的情况下,查询成本最多可降低为原来的4 4.6%。关键词:最近邻搜索;分层结构;局部敏感哈希;局部敏感B树中图法分类号 T P 3 1 9 L a y e r L S B:N e a r e s tN e i g h b o r sS e a r c hB a s e do nL a y e r e dL o c a l i t yS e n s i t i v eB-t r e eD I NGJ i w e n,L
5、I UZ h u o j i n,WANGJ i a x i n g,Z HANGY a n f e n ga n dYUG eS c h o o l o fC o m p u t e rS c i e n c ea n dE n g i n e e r i n g,N o r t h e a s t e r nU n i v e r s i t y,S h e n y a n g1 1 0 1 6 7,C h i n a A b s t r a c t N e a r e s tn e i g h b o r s e a r c hh a sb e c o m eas i g n i f i
6、 c a n t r e s e a r c hp r o b l e md u e t o i t sw i d ea p p l i c a t i o n s.T r a d i t i o n a l s p a t i a l i n-d e xs t r u c t u r e ss u c ha sR-t r e ea n dK D-t r e ec a ne f f i c i e n t l yr e t u r na c c u r a t en e a r e s tn e i g h b o rs e a r c hr e s u l t si nl o w-d i m
7、 e n s i o n a ls p a c e,b u t t h e ya r en o t s u i t a b l e f o rh i g h-d i m e n s i o n a l s p a c e.L o c a l i t ys e n s i t i v eB-t r e e(L S B)h a s h e sd a t ap o i n t s t o t h e s o r t a b l eo n e-d i m e n s i o nv a l u e sa n da r r a n g e st h e mi nat r e e-l i k es t r
8、u c t u r e,w h i c hd r a m a t i c a l l yi m p r o v e st h es p a c ea n dq u e r ye f f i c i e n c yo ft h ep r e v i o u s l o c a l i t ys e n s i t i v eh a s h i n g(L S H)i m p l e m e n t a t i o n s,w i t h o u tc o m p r o m i s i n gt h er e s u l t i n gq u a l i t y.H o w e v e r,L
9、S Bf a i l st ot a k ed a t ad i s t r i b u t i o n i n t oa c c o u n t.I t p e r f o r m sw e l l i nau n i f o r md a t ad i s t r i b u t i o ns e t t i n g,b u t e x h i b i t su n s t a b l ep e r f o r m a n c ew h e nt h ed a t aa r es k e w e d.I nr e s p o n s et ot h i sp r o b l e m,t h
10、 i sp a p e rp r o p o s e sL a y e r L S B,w h i c hr e c o n s t r u c t st h eh a s hv a l u e s i nad e n s er a n g eb ye x p l o r i n gt h ed e n s i t yo f t h eh a s hv a l u e st om a k et h ed i s t r i b u t i o nm o r eu n i f o r m,s oa st oi m p r o v et h eq u e r ye f f i c i e n c
11、y.C o m p a r e dt oL S B,L a y e r L S B i n d i c e sb e c o m em o r e t a r g e t e d i n t e r m s o f d a t ad i s t r i b u t i o n,a n dam u l t i-l a y e r e ds t r u c t u r e i s c o n s t r u c-t e d.C o m p a r e dw i t ht h es i m p l er e h a s h i n gm e t h o d,t h em u l t i-l a y
12、e r e da p p r o a c hw i l ls t i l lg u a r a n t e et h es e a r c hq u a l i t yb yc a r e f u l l yc h o o s i n gt h en u m b e ro fg r o u p sa n dh a s hf u n c t i o n s.T h e r e s u l t s s h o wt h a t t h eq u e r yc o s t c a nb e r e d u c e dt o4 4.6%o f t h eo r i g i n a la tm o s
13、tw h e na c h i e v i n gt h es a m eq u e r ya c c u r a c y.K e y w o r d s N e a r e s tn e i g h b o rs e a r c h,L a y e r e ds t r u c t u r e,L o c a l i t ys e n s i t i v eh a s h i n g,L o c a l i t ys e n s i t i v eB-t r e e 最近邻(N e a r e s tN e i g h b o r,NN)搜索问题是一个在尺度空间中寻找最近点的优化问题,几十年
14、来一直是一个活跃的研究课题,已被广泛应用于模式识别、统计分类、推荐系统等。线性遍历查找是处理最近邻查询最直观的方法,但随着数据集的增长,开销也会增加。在低维空间中,基于空间划分方法的传统树索引结构,如R-t r e e1,S R-t r e e2,K D-t r e e3,可以高效返回准确的最近邻搜索结果,但不适用于高维空间4,因为存储开销和时间开销可能随维度呈指数增长。因此,许多学者 提 出 了 近 似 最 近 邻(A p p r o x i m a t e N e a r e s tN e i g h b o r,ANN)搜索来解决高维空间中的NN搜索问题,其主要思想是以牺牲可接受范围内的
15、准确度为代价来提高检索效率,并返回允许误差范围内的近似解。L S H是ANN搜索中的主流方法,其哈希函数具有这样一个特点:对象越接近,碰撞概率越大。但是单个哈希函数会影响哈希的质量,因此一般选择m个这样的哈希函数共同作用于每个对象,生成对应的复合哈希键。但是,如果m太大,碰撞的概率就会减小。为了弥补这种损失,一般会构建l个哈希函数组,每个组中包含m个哈希函数。这样做虽然可以提高准确性,但会产生高昂的查询开销和空间开销。针对这个问题,T a o等5提出了一种具有代表性的 基于 树结 构 的L S H索引结构局部敏感B树(L o c a l i t y-S e n s i t i v eB-t r
16、 e e,简称L S B)。与传统的L S H相比,L S B进一步降低了存储开销,提高了查询效率。L S B5利用z-o r d e r技术,将数据点映射为可排序的一维z-o r d e r值,并使用一种树形结构来维护它们,即局部敏感B树(L S B树),最近邻搜索则通过与查询点对应的B树节点开始的双向扩展过程来实现。此外,B树可以实现高效更新,并且空间消耗随数据集基数的增大呈线性增长。但是,L S B没有考虑到数据分布,它在均匀的数据分布设置中表现良好,但在数据倾斜时表现出了不稳定的性能。图1(a)为K D D数据集的哈希值(即z值)在固定范围下数据点密度的直方图,每个条形代表一个z-o r d e r值范围内的数据点数,可以看到数据点呈现比较严重的倾斜分布。当在L S B树上执行查询时,如图1(b)所示,如果查询点位于稀疏区域,则查询的错误率(E r r o rR a t i o,如式(2)所示)偏低且比较稳定,查询开销(即I/O次数)较低且也比较稳定。但是当查询点位于密集区域时,查询的错误率偏高且非常不稳定,查询开销也稍高并且波动范围较大。造成这一现象的主要原因是密集区域内的查
