Skyline计算在许多领域具有潜在的应用价值,例如:多标准决策(multicriteria decision making)^[1]、空间位置导航服务(例如:在线地图服务)^[2]、商业数据分析(例如:超市位置选取、产品用户偏好分析)^{[3, 4]}、环境监测(例如:火灾温度、瓦斯浓度)^[5]等领域.

基本的Skyline计算方法可以分为两类:Skyline查询算法^{[2, 3]}和反向Skyline查询(RSQ)算法^{[4, 5, 6]}.Papadias等人^[1]首次提出基于分支界限的Skyline(branch and bound Skyline,简称BBS)算法,其主要思想依据维护的最小堆来访问索引节点,从而保证每次处理的节点(entry)与坐标原点具有最小距离,进而使得距离原点最近的数据对象为Skyline对象,然后继续这个搜索过程,将渐进地(progressive)获得其他的skyline对象,并使得整个算法具有最优的I/O效率^[1].进一步地,他们提出了扩展Skyline边界线为厚度为k的Skyline边界带,此即k-Skyband.当指定查询对象q时,基本的k-Skyband就成为了动态k-Skyband(DkSB),记为DkSB(q).显然,DkSB本质上是一种放松Skyline控制关系的计算,它使得不被任意其他对象的控制关系变成了最多可以被k个其他对象控制(k也表示边界线的厚度).Liu等人^[7]提出反向的k-Skyband(RkSB)查询算法,主要思想是修改BBS算法使得适应k-Skyband查询以及预计算方法和一些启发式的修剪策略.记查询对象q的RkSB为RkSB(q)).进一步地,Miao等人^[8]解决了不完整数据集上的k-Skyband查询.Feng等人^[9]则利用多核体系计算机并行计算k-Skyband查询.

然而,这些k-Skyband算法仅从查询对象q的正向角度考虑k-Skyband的查询需求,即要求查询的结果(例如: 对象p)在q的动态k-Skyband中(即p∈DkSB(q)),或者q的反向角度执行k-Skyband查询,即要求q处在某对象p的动态k-Skyband中(q∈DkSB(p)).因而,这些算法不能直接用来处理体现相互关系的应用.例如:个人匹配服务.事实上,考虑数据之间的相互关系是非常重要的.例如:文献[10]中提出的相互skyline即考虑了这种需求,因为返回的查询结果p既在查询对象q的skyline中,也在q的反向skyline当中.为此,本文提出了体现相互关系的k-Skyband查询类型,即相互k-Skyband(MkSB)查询.类似地,MkSB查询中返回的结果既在q的动态k-Skyband中,也在q的反向k-Skyband中.

MkSB查询在许多需要体现相互关系的应用场景中具有非常重要的意义.例如:考虑一个交友网站中的基于个性特征匹配的服务,且假定每个用户的爱好(喜欢音乐、体育、游戏等)表示用户的个性,每个用户某个爱好的喜欢程度表示为0~1之间的一个实数值(注意,不同用户的爱好程度可以相同).对于给定的查询用户q(例如: Bob),希望根据他的爱好找出的好朋友与他的志趣都比较接近,这样Bob可以发出一个k-Skyband来寻找这样的朋友.假定,返回的查询结果中有位称作Alice的女性朋友,Bob非常喜欢,且希望与她约会.那么,Alice是否愿意呢?如果Alice也发出一个k-Skyband查询,发现Bob并不在她的查询结果当中(这表明Bob相对她获取的查询结果中的其他人来说,Bob距离Alice的个性特性较远).Alice很可能会拒绝Bob的约会请求,因为她认为Bob并不符合她的个性特性.反之,如果Bob在Alice的查询结果当中,那么Alice则有可能接受Bob的约会申请.这是因为MkSB查询保证了Bob和Alice在个性特性上是相互匹配的.

显然,相互k-Skyband查询可以通过分别执行一次查询对象q的正向k-Skyband和反向k-Skyband,然后计算DkSB(q)和RkSB(q)的交集来实现.然而,这种简单的实现方法效率很低,存在大量冗余的I/O,不适合现实的应用场景.例如:具有较少能量和计算能力的传感器网络应用中^[11].另一方面,直接的MkSB查询返回的结果缺乏排序操作,使得用户不易选择.为此,本文进一步引入排序操作.例如:选取一个单调函数并取排序函数值最小的前m个数据对象作为结果,从而提出了排序的相互k-Skyband查询处理算法.本文利用了信息重用技术思想,将MkSB查询中的多次k-Skyband查询对应的R-teee搜索合并成单次搜索,并提出了一些高效修剪方法,很好地解决了MkSB查询效率问题.

本文的主要贡献如下:

(1) 提出了一种新颖的k-Skyband查询:相互的k-Skyband(MkSB),它满足了一些应用需求.

(2) 提出了3种MkSB查询算法:基本的MkSB(Basic MkSB,简称BMkSB)、动态的MkSB(MkSB based on Dynamic k-Skyband,简称DMkSB),以及基于窗口查询的MkSB(MkSB based on Window query,简称WMkSB).他们的主要思想包括:信息重用技术、提前终止方法以及一些高效修剪策略.

(3) 设计了详尽的性能评价实验,实验结果表明,WMkSB算法通常能减少95%以上的冗余I/O成本,且具有最优的I/O效率.

本文第1节是问题的定义和描述.第2节介绍MkSB查询工作原理.第3节给出DMkSB和WMkSB算法.第4节通过实验对3种算法的性能进行比较验证.最后,第5节总结全文.

相互k-Skyband查询是一种对称的Skyline查询,体现了查询对象q和数据对象p之间的相互关系.其查询结果中的对象p同时出现在q的DkSB和RkSB中.

定义1(动态k-Skyband(DkSB)). 给定查询对象q,参数k和数据集P,对象q的DkSB查询(记为DkSB(q))返回一个最大子集R⊆P,使得R中的任意对象r∈R,最多被k个其他对象控制.

动态k-Skyband查询实质是将原数据集P相对于参考对象q映射形成新的数据集P′,然后在P′上执行k-Skyband运算.其中,k表示边界线(即skyline)的厚度.当k=0时,k-Skyband即是原始的Skyline计算.例如:图 1(a)中p₂的动态0-Skyband和1-Skyband查询结果分别为{p₃,p₅}和{p₃,p₅,p₁,p₄,q,p₆}.注意,D0SB(q)⊂D1SB(q).

图 1(Fig.1)

Fig.1 Illustration of 1-Skyband query 图 1 1-Skyband查询示例

定义2(反向k-Skyband(RkSB)). 给定查询对象q参数k和数据集P,q的RkSB查询(记为RkSB(q))返回一个最大子集R⊆P,使得R中的任意对象r∈R的动态k-Skyband(DkSB(r))包含q.

为了说明RkSB查询的执行过程,定义3给出了全局k-Skyband查询的概念.

定义3(全局k-Skyband(GkSB)). 给定查询对象q,参数k和d维的数据集P,对象q的GkSB查询(记为GkSB(q))返回q的各个坐标分区中的k-Skyband查询结果的并集.例如:图 1(b)中q的坐标分区I,II,III和IV的1-Skyband分别为{p₃,p₄},{p₇,p₉},{p₅,p₂}和{p₆,p₈},GkSB(q)={p₃,p₄,p₇,p₉,p₅,p₂,p₆,p₈},且G0SB(q)⊂G1SB(q).

事实上,根据定义2直接求q的RkSB具有较高的成本.通常是首先执行q的GkSB查询获得一个候选集S_c,然后为S_c中的每个对象o∈S_c执行o和q形成的窗口(记为w(o,q))查询^[4].如果窗口中包含不多于k个其他数据对象(o和q除外),则o为RkSB(q)的一个查询结果;否则,o不是RkSB(q)的查询结果.例如:图 1(b)中灰白色区域为对象p₅的1-Skyband的窗口w(p₅,q).由q出发联向p₅并延长获得q相对于p₅的对称点(记为q′),然后分别作经过q和q′的水平线和垂直线,获得两个交点q″和q′″,连接q″至q,再至q″′,最后至q′组成的矩形区域,即为w(p₅,q),它仅包含对象p₂,故p₅∈R1SB(q).而w(p₁,q)则包含了p₃和p₄,故p₁$ otin $R1SB(q).注意:上述定义1~定义3存在关系DkSB(q)⊆GkSB(q)且RkSB(q)⊆GkSB(q).

根据查询对象q的DkSB和RkSB定义,易获得q的相互k-Skyband(MkSB),其定义如下.

定义4(相互k-Skyband(MkSB)). 给定查询对象q,参数k和数据集P,对象q的MkSB查询(记为MkSB(q))检索出所有既在DkSB(q)中又在RkSB(q)中的数据对象.它可以表示为MkSB(q)={p∈P|p∈DkSB(q)^p∈ RkSB(q)}或MkSB(q)={p∈P|p∈DkSB(q)^q∈RkSB(p)}.

相互k-Skyband查询返回的结果可能太多,故一般用户只需要排序后的前m个结果,此即下面的定义5.

定义5(排序的相互k-Skyband(SMkSB)). 给定查询对象q,单调上升排序函数F,多维数据集P,参数k和m,SMkSB查询找出m(m≤|MkSB(q)|)个MkSB对象,使得它们组成的集合R⊆P有最低的分数score(R)=∑_p∈R F(p),其中,F(p)是对象p在函数F中的函数值.这里分数越低,结果越好.

基本的MkSB算法BMkSB遵循分支界限^[1]搜索框架,先获得DkSB查询结果,再应用参数m约束条件,然后获取最终结果.它首先以q为参考对象调用文献[1]中的动态k-Skyband^[1]搜索算法获得q的动态k-Skyband查询结果集合S_c,然后以o∈S_c为参考对象每次调用动态k-Skyband算法(实际上,它是反向的动态k-Skyband查询)获得o的动态k-Skyband查询结果集合S_rc,并判断是否q被S_rc中最多k个对象控制.如果是,则说明对象o是q的相互k-Skyband对象.然后,通过维护一个最多包含m个查询结果的队列S_r来实现MkSB的排序.当S_c中的所有对象都判断结束后,队列S_r中的所有数据对象即是查询对象q的排序值最小的m个相互k-Skyband对象.

假设数据集P上的R-tree索引有log|T_P|层,最小堆尺寸为H₁,动态k-Skyband的数目为|R_d|,则BMkSB算法具有下面的定理.

定理1. 给定排序参数m,BMkSB算法的时间和空间复杂度分别为O((1+min(m,|R_d|))×log|T_P|)和O(2H₁).

证明:BMkSB执行动态k-Skyband查询需要O(log|T_P|)次I/O访问,使用一个尺寸为H₁的最小堆.另外,候选集中的每个对象p在执行反向动态k-Skyband同样需要O(log|T_P|)次I/O访问,尺寸为H₁的最小堆,这个查询过程最少需执行m次,最多|R_d|次.因此,其总时间复杂度为O((1+min(m,|R_d|))×log|T_P|),总空间复杂度为O(2H₁). □

注意,当需要排序的对象数目m>|R_d|时,BMkSB执行RkSB查询的实际次数为|R_d|;否则,m≤|R_d|时,BMkSB执行RkSB查询的实际次数为m,故其时间复杂度函数中应使用最小值min函数,而不是最大值max函数.

显然,BMkSB算法需两个步骤才能完成,即动态k-Skyband和反向k-Skyband,从而需多次访问R-tree树,存在大量冗余的I/O成本.下面将讨论改进它的基本原理.

BMkSB算法通过执行一次反向的k-Skyband,来判断是否q∈DkSB(p),从而判断候选对象p是否属于MkSB(q)(其中,p来自第1阶段获得的候选集S_c).显然,此过程需要一次完整的索引访问过程.事实上,如果能够将该索引(例如:R-tree)访问过程中的节点(中间索引节点或叶子的数据对象节点)信息(即最小边界矩阵MBR信息)保存下来,并能在后面的反向搜索过程中利用,那么MkSB查询将仅需一次完整的R-tree遍历.

考虑图 2中的动态1-Skyband(D1SB)查询过程.假设单调上升排序函数F(=min{L₁(e,q)})为节点e与q的L₁(坐标之差绝对值)距离最小值,即q与e的MBR的四条边的最小距离值.首先节点N₁(即e₁)和节点N₂(即e₂)被插入辅助堆H中.然后,访问节点e₁,最小堆H={e₂,e₃,e₄}.接着,由于F(e₂)=min{L₁(e₂,q)}=1.5小于F(e₃)=2,访问节点N₂(即e₂),最小堆H={e₃,e₅,e₆,e₄}.紧接着N₃(即e₃)被访问,数据节点a,b,c被插入H中.此时,数据节点c位于堆H={c,e₅,e₆,e₄,b,a}的顶部且不被任何对象控制,因而它成了动态1-Skyband结果集R_d的第1个元素.此时,将节点c相对q进行映射(图 2中二维空间中为左右、对角线和上下方向),得到c′,c′′,c′′′点(灰色圆点).进一步得到I,II,III,IV这4个阴影区域,即节点c相对于q的动态控制区域DDR_q(dynamic dominating region).由于节点N₄(即e₄),N₅(即e₅),N₆(即e₆)和点a完全包含在DDR(c)中,N₄,N₅,N₆和a被R_d={c}控制.接着扩展e₅,数据点f控制了a和e₄,故a和e₄被修剪.然后扩展节点e₆,/span>数据点i和j被R_d={c,f}控制,故i和j被修剪.最终,得到D1SB(q)的查询结果为R_d={c,f,b,g}.

图 2(Fig.2)

Fig.2 Dynamic dominating region of dynamic 1-Skyband query 图 2 动态1-Skyband的动态控制区域

上述动态1-Skyband搜索过程中辅助堆H内容和结果集R_d的变化情况见表 1.其中,堆的内容为(节点,节点与q之间的最小距离)对.带删除线的节点或数据点表示被R_d中至少两个数据点控制,从而可以修剪掉.

表 1(Table 1)

Table 1 The auxiliary heap content during dynamic 1-Skyband 表 1 动态1-Skyband搜索过程辅助堆的内容 Action Heap content( H) R d Access root ( e 1,1)( e 2,1.5) Null Expand e 1 ( e 2,1.5)( e 3,2)( e 4,4) Null Expand e 2 ( e 3,2)( e 5,2.5)( e 6,3.5)( e 4,4) Null Expand e 3 ( c,2.5)( e 5,2.5)( e 6,3.5)( e 4,4)( b,4)( a,7) { c} Expand e 5 ( f,3.5)( e 6,3.5) ( e 4,4)( b,4)( g,4.5) ( a,7) { c, f} Expand e 6 ( b,4) ( i,4.5)( g,4.5)( h,5.5) ( j,8.5) { c, f, b} Access g ( g,4.5) ( h,5.5) { c, f, b, g}

Table 1 The auxiliary heap content during dynamic 1-Skyband 表 1 动态1-Skyband搜索过程辅助堆的内容

上述动态1-Skyband搜索过程中重用信息堆H_r内容和结果集R_d的变化情况见表 2.

表 2(Table 2)

Table 2 The reuse heap content during dynamic 1-Skyband表 2 动态1-Skyband搜索过程重用堆的内容 Action Heap content( H r) R d Access root ( e 1,1)( e 2,1.5) Null Expand e 1 ( e 2,1.5)( e 3,2)( e 4,4) Null Expand e 2 ( e 3,2)( e 5,2.5)( e 6,3.5)( e 4,4) Null Expand e 3 ( c,2.5)( e 5,2.5)( e 6,3.5)( e 4,4)( b,4)( a,7) { c} Expand e 5 ( c,2.5)( f,3.5)( e 6,3.5)( e 4,4)( b,4)( g,4.5)( a,7) { c, f} Expand e 6 ( c,2.5)( f,3.5)( e 6,3.5)( e 4,4)( b,4)( g,4.5)( i,4.5)( h,5.5)( a,7)( j,8.5) { c, f} Access b and g ( c,2.5)( f,3.5)( e 4,4)( b,4)( g,4.5)( i,4.5)( h,5.5)( a,7)( j,8.5) { c, f, b, g}

Table 2 The reuse heap content during dynamic 1-Skyband表 2 动态1-Skyband搜索过程重用堆的内容

上面的分析过程表明重用堆H_r的信息随着动态1-Skyband的执行,访问过程中的节点信息存储在H_r中,如果某节点仍需扩展,则该节点从H_r中被删除而其孩子节点被插入H_r,直到动态1-Skyband执行完成.例如: 访问节点N₃前H_r={e₃,e₅,e₆,e₄},访问节点N₃后,其孩子节点{a,b,c}被插入H_r中,而节点N₃={e₃}被删除,此时H_r={c,e₅,e₆,e₄,b,a}.

尽管文献[10]也使用了重用方法,但它们仅保存第1个动态1-Skyband结果之前访问的节点信息.例如:图 3中获得q的D1SB的第1个结果g后H_r={e₅,e₁,e₆}.然后,求得D1SB(q)={g,c,h,i}(图 3(a)中II区中虚线相连的点, 其中灰色圆点为其他分区在II分区中的映射点)的过程中堆H_r的内容不发生变化.然而本文的重用堆H_r随着整个相互1-Skyband执行完成而发生变化.例如:在求得c∈D1SB(q)时,H_r={e₅,e₃,e₆,e₄}.这样,执行对象c的窗口查询时不会产生新的I/O.然而,文献^[10]的信息重用方法却需1次I/O访问(因为e₃$ otin $H_r).

图 3(Fig.3)

Fig.3 Illustration the use of Hr 图 3 重用堆Hr使用实例

如果MkSB算法执行动态k-Skyband时将访问信息保存在重用堆H_r中.那么,它再执行多次反向动态k-Skyband就可以求得排序后的前m个相互k-Skyband的查询结果.

另一方面,相互k-Skyband可以在动态k-Skyband的候选结果集S_c的基础上,结合重用堆H_r的内容,通过执行窗口查询^[4]来求得最终的结果,即下面的定理2.

定理2. 给定查询对象q和多维数据集P,候选结果集S_c=DkSB(q),如果窗口查询w(p∈S_c,q)包含超过k个其他对象(p和q除外),则p不是相互k-Skyband对象.

证明:假设任意对象p∈MkSB(q),则有p∈DkSB(q),即p是q的动态k-Skyband.根据集合DkSB(q)和GkSB(q)的关系有:DkSB(q)⊆GkSB(q),又MkSB(q)⊆DkSB(q)⊆GkSB(q),故有p∈GkSB(q).根据已知条件知,GkSB对象p的窗口w(p,q)包括的其他对象个数超过k个,因而q相对于p被至少k+1个对象控制.换句话说,q不在p的DkSB查询结果当中.根据RkSB的定义知,p$ otin $RkSB(q).既然p∈DkSB(q)又p$ otin $RkSB(q),从而p$ otin $MkSB(q). □

定理2具有重要意义,它保证了在执行DkSB查询的基础上,通过窗口查询可以获得MkSB查询结果,而不必执行返回结果很多的GkSB查询.例如:图 3(a)中执行g∈D1SB(q)的窗口查询w(g,q)就可以判断g∈M1SB(q),即g是相互1-Skyband的结果.

既然,H_r可以在DkSB中使用,也可以在窗口查询中使用,可以证明下面的定理3是正确的.

定理3. 给定查询对象q和多维数据集P,如果使用前述重用堆H_r来保存q的DkSB执行过程中的节点信息,无论是通过多次窗口查询或RkSB查询来完成MkSB查询,MkSB算法不会产生漏报或多报.

证明:显然,H_r完整地保存了数据集P中的所有数据对象不同层次的索引信息.例如:图 3(a)中数据对象a,b, c为第0层的叶子节点,而数据对象d,e为第1层的中间索引节点e₄.这样,通过H_r一定可以访问到所有节点的MBR信息.定理2已经证明了通过窗口查询的方法可以获得MkSB,故而不会产生多报或漏报.另一方面,对于候选集S_c的某个对象p∈S_c,以p为参考对象并使用H_r也可以求得p的动态k-Skyband结果集合S_rc.根据定义2如果q∈S_rc,那么对象p就是一个MkSB对象.因此,这种方法也不会产生多报或漏报. □

定理3也是非常重要的,它保证了信息重用方法的正确性.这样,就可以合并MkSB的R-tree遍历成单次R-tree遍历,从而极大地降低I/O访问次数.

本节讨论重用堆H_r的空间复杂度.显然,前述方法的有效性依赖于SMkSB在第1阶段执行DkSB过程中H_r的空间复杂度.下面从理论上进行分析论证.

假设数据集P包含E个数据对象,索引中根节点包括α个节点,平均每个节点包括μ个孩子节点,索引包含L层,每次I/O操作页面可以容纳β个节点,则根节点需$\left\lceil {\alpha /\lambda } \right\rceil $次I/O访问,其他节点平均需$\left\lceil {\mu /\beta } \right\rceil $次I/O访问.易求出首个动态k-Skyband点需要的最小I/O次数为

$N\left( 1 \right) = \left\lceil {\alpha /\beta } \right\rceil + \left( {L + 1} \right) \times \left\lceil {\mu /\beta } \right\rceil $(1)

重用堆H_r的尺寸|H_r|至少如下面的公式(2):

$\left| {{H_r}} \right| = \alpha + \left( {L - 1} \right) \times \mu $(2)

同时索引层次满足下面的公式(3):

$E = \alpha + \alpha .\mu + \alpha .{\mu ^2} + \ldots + \alpha .{\mu ^{L - 1}}$(3)

联立等式(1)~等式(3)得到下面的公式(4)和公式(5):

$\left| {{H_r}} \right| = \alpha + \left( {\log _\mu ^{E \cdot \left( {\mu - 1} \right)/\alpha + 1} - 1} \right) \times \mu $(4)

$N\left( 1 \right) = \left\lceil {\alpha /\beta } \right\rceil + \left( {\log _\mu ^{E \cdot \left( {\mu - 1} \right)/\alpha + 1} - 1} \right) \times \left\lceil {\mu /\beta } \right\rceil $(5)

公式(4)和公式(5)分别反映了文献[10]重用堆的大小和I/O次数,它们的空间复杂度是比较低的.如果所有DkSB对象在一个节点,则本文重用堆H_r的最大尺寸与文献[10]的相同.否则,此时重用堆在后续的DkSB对象求出时可能会继续扩展,以至H_r继续增大,直到DkSB执行完.访问的I/O与此类似,每当节点扩展时,将存在I/O操作,但同时由于H_r变大,大部分的访问信息可以从H_r获得,从而以后需要的I/O操作将逐渐减少(虽然,总的I/O次数仍可能增加).

基于表 2的观察可以发现:在求得DkSB时,H_r中包含了很多数据对象.在这种情况下,一种方法是限定H_r中的第1层节点不能扩展,从而缩减H_r的尺寸.

排序的相互k-Skyband采用边搜索边修剪的方式实现,运用约束条件尽早终止计算,充分重用已有信息,最大限度减少I/O访问和CPU时间.

DMkSB算法的基本思路与BMkSB算法类似.主要不同之处在于:(1) DMkSB执行动态k-Skyband查询时会将运行过程中的访问信息保存在重用堆H_r中;(2) DMkSB在判断当前对象p∈DkSB(q)是否是相互k-Skyband而执行反向动态k-Skyband时使用H_r,极大地减少了I/O次数;(3) DMkSB边搜索边修剪可以在其第5行的DkSB(q)和第14行的DkSB(p)分别提前终止计算,而不像BMkSB完整地执行完它的DkSB(q)和反向DkSB(p). 前者可提前终止是因为当前节点e的低边界排序函数值LB_F(e)=min{F(x)|$\forall $x∈e}比查询结果中的第m个最小的排序函数值大,DkSB(q)不必要全部执行完;后者可提前终止是因为如果$(k+1)个对象p′∈D相对于p控制q, DkSB(p)不必要执行完.DMkSB执行DkSB(q)提前终止计算的推理体现在下面的定理4.

定理4. 给定排序函数F(.)和排序参数m,对象o₁,o₂,…,o_m是目前获得的m个MkSB结果对象,节点e的最小排序值LB_F(e)为min{F(x)|$\forall $x∈e},m_score表示m个结果对象中的最大排序函数值max{F(o_i)|o_i,$\forall $i∈[1,m]}. 如果满足条件LB_F(e)≥m_score,则可以安全地修剪掉节点e.

证明:既然节点e的任意数据对象的最小排序值LB_F(e)都比m_score大,那么一定存在至少m个结果对象o₁,o₂,…,o_m的分数值比e中的任意对象的分数值小.因此,节点e可以安全地修剪掉. □

DMkSB的详细算法描述见算法1.

算法1. DMkSB(T,k,F,m,q,S_r).

输入: /*T: index; k and m: skyband and ranked parameter; F(.): preference function; q: query object*/;

输出: S_r: result set.

1. S_r=Ø,S_c=Ø,H=Ø,H_r=Ø,m_score=+∞;

2. Insert root into H and H_r with (e,mindist(e,q));

3. WHILE H is not empty DO

4.   Pop the entry (e,mindist(e,q)) of H;

5.   IF LB_F(e)≥m_score THEN BREAK;

6.   IF e is not contained in (k+1) DDR_q(o∈S_c) THEN

7.     IF e is an intermediate entry THEN

8.       FOR each child entry e_i∈e DO

9.        IF e_i$ otin $k+1 DDR_q(o∈S_c) THEN

10.         Insert (e_i,minidist(e_i,q)) into H;

11.        Insert all e_i∈e into H_r, Delete e from H_r;

12.   ELSE //e is a data object

13.     S_c=S_c$ cup ${e}; //e is a DkSB object w.r.t. q

14.     rflag=RDkSB(T,k,e,q,H_r);

15.     IF rflag==TRUE THEN

16.       IF |S_r|<m THEN

17.         S_r=S_r$ cup $e}; //e is a MkSB object w.r.t. q

18.         Update m_score using largest score in S_r;

19.       ELSE //|S_r|≥m

20.        let o′ be the object in S_r with m-th smallest score;

21.        IF F(e)<m_score THEN

22.        S_r=S_r$ cup ${e};

23.        Remove o′ from S_r;

24.        Update m_score using new m-th smallest score;

25. RETURN S_r;

DMkSB执行动态k-Skyband的方法是:判断节点e是否完全包含在求得的DkSB候选集合S_c中的k+1个数据对象o∈S_c的动态控制区域DDR_q(o)中(算法第6行和第9行).显然,如果节点e⊆DDR_q(o),则e被o动态控制.第11行更新重用堆H_r,即从中删除当前节点e,并将e的所有孩子节点e_i∈e插入H_r中.为了提高H_r更新效率, 可以采用二分搜索方法.第13行添加对象e到DkSB候选集合S_c中,第14行以e为参考对象,使用重用堆H_r,调用反向DkSB查询算法RDkSB(行14),判断是否存在对象p′相对当前对象e∈DkSB(q)控制q.如果存在,则该算法返回FALSE,并保存到变量rflag中;否则rflag为真(行15),然后算法在第16行~第24行实现对获得的最多m个查询结果的排序和动态更新.其中,RDkSB算法伪代码描述如算法2所示.

算法2. RDkSB(T,k,p,q,H_r).

输入: /*T: index; k: skyband parameter; p: candidate object∈DkSB(q); q: query object; H_r: reuse heap*/;

输出: rflag: an Boolean value whether q is dominated k+1 object w.r.t current object p∈DkSB(q).

1. S_c=Ø,H=Ø; //S_c—result set of RkSB(q)

2. WHILE H_r is not empty DO

3.   Pop the entry (e,mindist(e,q)) of H_r;

4.   Push the entry (e,mistdist(e,p)) into H;

5~13. Lines 3~4, 6~10, and 12~13 of DMkSB but q is replaced by p in lines 4, 6, 9 and 10

14.     IF $(k+1) points in e dominates q w.r.t. p THEN

15.       BREAK, RETURN FALSE;

16. RETURN TRUE;

RDkSB算法的最好优先(best first)搜索框架与算法DMkSB类似.算法的2~4行将重用堆中的信息弹出,并根据DkSB(q)中的当前候选对象p重新计算节点e的最小距离mistdist(e,p),然后插入搜索辅助堆H中.注意,由于是以p为参考对象进行动态DkSB查询,因而第5行~第13行使用p代替q计算节点e的最小距离mindist(e, p)和动态控制区域DDR_p(o∈S_c).第14行判断当前节点e是否存在k+1个对象相对于p控制q.如果是,根据k-Skyband定义,则当前候选对象p一定不是MkSB对象,从而可以终止计算(行15),并返回FALSE;否则,计算出所有的RkSB对象,并返回TRUE(行16),因为q∈DkSB(p).

从DMkSB算法的描述和分析中,容易得到下面的I/O性能定理5.

定理5. 假定q的DkSB查询包含|R_d|个数据对象,排序函数参数为m,则BMkSB算法从磁盘装入访问H_r中实体1+min(m,|R_d|)次,而DMkSB算法仅仅装入1次.

WMkSB的实现框架与DMkSB完全一致.不同之处在于:它通过调用窗口查询,以当前DkSB(q)的候选对象p与q的窗口w(p,q)是否包含k+1其他数据对象o∈w(p,q)来判断p是否是MkSB对象(定理2),并利用重用堆H_r信息和实现提前终止计算.其实质是利用窗口查询来代替反向的DkSB计算(例如:DkSB(p),其中,p∈ DkSB(q)).仅替换DMkSB算法第14行中的RDkSB函数为k-Skyband窗口查询函数SBWinQ,便可以得到算法3.需要说明的是,尽管DMkSB和WMkSB算法中代码区别较少,但是他们的实现方法的原理完全不同,WMkSB的实现原理体现在定理2.

算法3. WMkSB(T,k,F,m,q,S_r).

输入: /*T: index; k and m: skyband and ranked parameter; F(.): preference function; q: query object*/;

输出: S_r: result set.

1~25. Lines 1~25 of DMkSB but the function RDkSB of line 14 is replaced by the function of window query SBWinQ

SBWinQ利用重用信息时,可使用RDkSB算法中行第2行~第4行的代码.而它判断窗口w(p,q)是否包含k+1其他对象(例如:图 3中g点的窗口w(g,q)不包含其他对象,故是一个MkSB对象),则可以使用类似BBS算法的R-tree索引遍历过程,而需要将控制关系的判断语句更改为节点的MBR是否与w(p,q)相交或包含w(p,q)这种位置关系的判断语句即可,并使用布尔查询方法:即遇到k+1个其他数据对象p′(p′≠p^p′≠q)∈w(p,q)时,立刻终止计算,并返回FALSE.从WMkSB算法的描述分析中,可以得到类似于定理5的关于WMkSB算法的I/O性能定理.

实验采用真实数据集NBA^[12]、Hou^[12](抽取前三维组成实际数据集),它们分别包含了5维17K、6维127K个数据对象以及服从不同分布特性的合成数据集Correlated(Corr)和Independent(Indep),数据空间为[1, 10000]. 查询对象q从数据集中随机选取50个,实验结果取50次运行的平均值.除了排序参数m(排序的查询结果数目)实验外,所有实验中排序参数m设置为16,排序函数F为min{L₁(x,q)|$\forall $x∈e}.实验通过两个重要的性能指标I/O访问次数和CPU运行时间(不包括I/O时间)来评估BMkSB,DMkSB和WMkSB的性能(由于目前未出现同类算法,故本文算法未与其他算法比较).

其他参数设置如下.R-tree页面尺寸和cache块大小为4 096字节.实验在双核3.2GHz、500G硬盘的PC机上运行,编程语言为C++.注意,实验绘图中的折线表示I/O访问次数,对应左边的对数纵坐标,柱状图表示CPU运行时间,对应右边的纵坐标(其中,数据维度变化实验中使用对数坐标).绘图中的RHS表示重用堆包含索引节点的数目.需要说明的是,类似于文献[6]和文献[12]中的R-tree实现代码,本文的R-tree代码也是基于磁盘实现(即访问1次索引节点将产生1次I/O操作).

(1) 参数k的影响

第1组实验比较算法在真实数据集上随参数k大小(skyband厚度参数)的性能(cache块数目为0).图 4的实验结果反映:随着k的增大,BMkSB和DMkSB算法I/O节点访问次数和CPU运行时间(单位:s)都逐渐增大;然而WMkSB的I/O成本和CPU时间逐渐减少且有最小的成本.实际上,当k的值由0分别增加到1,2,3和4时,3种算法在NBA和Hou数据集上的相互k-Skyband的数目分别为13,13,27,36,46,以及15,15,31,42,53.这也在一定程度上解释了图 4中I/O成本和CPU时间的增长趋势.3种算法的I/O次数分别处在不同的数量级上,其中DMkSB的I/O次数仅与排序参数m处于一个数量级.这是因为MkSB结果对象在k较小(例如:k=1)时,一般处于索引的同一节点上;同时重用堆技术的使用减少了大量的冗余I/O访问.例如:k=4时,WMkSB减少了BMkSB算法99.14%以上的I/O.

图 4(Fig.4)

Fig.4 Performance on real datasets vs. k (cache blocks=0) 图 4 算法在真实数据集上随k变化的性能(cache块数目=0)

(2) 数据集尺寸(s)的影响

第2组实验比较算法在真实数据集上随着数据集尺寸s变化的性能.参数k固定为2,cache块数目为0.图 5的实验结果反映:增大数据集尺寸,3种算法的I/O成本和CPU运行时间沿着增长趋势扩大.但有趣的现象是3种算法的局部性能可能下降.这是因为,I/O访问不仅与数据尺寸相关,也与数据分布和q的位置有关.由于使用了重用技术,故DMkSB的I/O成本稍差于WMkSB却比BMkSB好得多.

图 5(Fig.5)

Fig.5 Performance on real datasets vs. dataset size (k=2, b=0) 图 5 算法在真实数据集上随数据集尺寸变化的性能(k=2, b=0)

(3) Cache块数目(b)的影响

第3组实验比较算法在真实数据集上随cache块数目b变化的性能(k=2).图 6的实验结果体现了重用方法远比增加cache大小的方法更能减少I/O次数.例如:在Hou上,16K的cache仅能减少1.56%的I/O访问,而DMkSB和WMkSB的重用技术却分别减少88.67%和96.68%的I/O访问.因为cache基于局部性原理来保存节点信息, 常常下次访问的节点并不存在cache中.另一方面, 重用技术的运用减少了许多不必要的计算,使得WMkSB比DMkSB快3~5倍,比BMkSB快至少10倍以上.

图 6(Fig.6)

Fig.6 Performance on real datasets vs. cache blocks (k=2) 图 6 算法在真实数据集上随cache块数目变化的性能(k=2)

(4) 排序参数(m)的影响

第4组实验比较排序参数m(要求返回的查询结果数目)在真实数据集上对各种算法的影响.图 7中的实验结果表明,3种算法都将随着m的增加,I/O次数和CPU运行时间都将增大,但是算法WMkSB具有最好的性能. BMkSB和DMkSB算法在参数m增大到32之后,I/O次数将缓慢增长;而WMkSB算法在m增大到16后,在16~32的范围内,I/O次数较快速地增长.这是因为m较小时,WMkSB返回的结果可以在一个节点上找到.

图 7(Fig.7)

Fig.7 Performance on real datasets vs. m (k=2, b=0) 图 7 算法在真实数据集上随m变化的性能(k=2, b=0)

(1) 参数k的影响

第1组实验评估算法在512K尺寸3维的合成数据集上随着k变化的性能.图 8的实验结果表明:增大k,实验结果和现象及原因与图 4类似.WMkSB仍具有与参数m一个数量级的I/O访问次数.

图 8(Fig.8)

Fig.8 Performance on synthetic datasets vs. k (b=0) 图 8 算法在合成数据集上随k变化的性能(b=0)

(2) 数据集大小s(size)的影响

第2组实验比较算法在3维的合成数据集上随着数据集尺寸s变化时的性能.数据集尺寸分别为128K, 256K,512K,1024K和2048K,参数k=2,b=0.图 9的实验结果和相应的现象及原因类似于图 5.

图 9(Fig.9)

Fig.9 Performance on synthetic datasets vs. s (k=2, b=0) 图 9 算法在合成数据集上随s变化的性能(k=2, b=0)

(3) Cache块数目b(cache blocks)的影响

第3组实验报告512K大小3维的合成数据集随着b变化的性能(k=2).图 10中的实验结果及相应现象及原因类似于图 6:与使用H_r相比,增大b仅能很少程度上减少I/O访问次数,仅当cache较大的时才有较为明显的效果(例如:b=32);但对CPU运行时间几乎没有影响.WMkSB最优I/O性能充分表明了重用信息策略的优势.

图 10(Fig.10)

Fig.10 算法在合成数据集上随b变化的性能(k=2) 图 10 Performance on synthetic datasets vs. b (k=2)

(4) 数据维度d的影响

第4组实验比较算法在512K的合成数据集上随着维度d变化的性能(k=2,b=0).从图 11的实验结果中可以看出,随着d的增大,BMkSB算法的I/O次数明显地增大,DMkSB缓慢增大,而WMkSB算法仅仅轻微增大.在5维情形的Indep数据集上,DMkSB减少了BMkSB算法98.6%的I/O次数,而WMkSB又减少了DMkSB算法96.1%的I/O次数,总体上WMkSB仅有BMkSB算法0.055%的I/O访问.另一方面,WMkSB算法在Indep上,其CPU运行速度比BMkSB快1780倍,比DMkSB也快了13倍.这说明维度d对算法性能有较大影响.由于Corr对角线分布、Indep均匀分布,Corr比Indep具有更多I/O访问.

图 11(Fig.11)

Fig.11 Performance on synthetic datasets vs. d (k=2, b=0) 图 11 算法在合成数据集上随着维度d变化的性能(k=2, b=0)

(5) 排序参数(m)的影响

第5组实验评估合成数据集上排序参数m对各种算法的影响(数据集尺寸为512K,维度为3).图 12中的实验结果及相应现象及原因类似于图 7:WMkSB在I/O成本和CPU运行时间都优于其他两种算法.

图 12(Fig.12)

Fig.12 Performance on synthetic datasets vs. m (k=2, b=0) 图 12 算法在合成数据集上随着m变化的性能(k=2, b=0)

相互k-Skyband查询从对称角度设计应用,在商业数据分析、个性化匹配等方面具有重要的应用价值.本文提出了3种高效的排序相互k-Skyband查询算法:BMkSB,DMkSB和WMkSB.算法采用BF搜索策略,利用重用堆思想和尽早终止计算等方法,极大地减少了算法的冗余I/O访问,加速了CPU的运行效率.最后,实验和理论分析都证明了基于窗口查询和信息重用的WMkSB算法在skyband厚度、数据集大小和维度以及排序参数m上, 都具有最优的性能.WMkSB是目前为止最优的相互k-Skyband查询算法:在I/O效率上,它几乎保持了O(m)的线性I/O访问次数.