计算SKY的预排序分组算法

刘 萍

(甘肃民族师范学院计算机科学系，甘肃 合作 747000)

0 引言

S.Borzsony等在文献［1］中提出轮廓(Skyline)的概念，用来表述在多维的数据系统R中经过评估选出的占优的数据(元组)。多维评估的方法通常称为多元目标优化决策。假设R是有d维属性的数据系统，每一个属性的值都是能够比较优劣的域，通常用正实数表示属性的值。一般说来，一些属性值以大的数为优，另一些值则以小的数为优。以文献［1］中举的例子(很多文献都引用这个例子)为例，对于旅游胜地拿骚(巴哈马群岛)的旅馆，可以有多个指标来评估旅馆的优劣，如旅客关心的价格、旅馆到海滨的距离、旅馆的星级等。其中价格指标以小的数为优，星级指标以大的数为优。在旅游指南(列出所有旅馆的数据)中，游客不可能找到各项指标都占优的旅馆。旅客感兴趣的显然是这种旅馆，不存在一个在所有指标都超过它的旅馆。这种旅馆就是文献［1］中所说的旅馆集合中的Skyline。显然Skyline旅馆不是唯一的，这就方便旅客根据自己的偏爱做出选择。多元目标优化决策的应用非常广泛，促使了Skyline的研究。为了实现Skyline查询，文献［1］提出一种嵌套SQL查询(nested SQL query)。然而这种方法需要对于每一个旅馆和所有的旅馆作比较，开销太大，没有实用价值。因为实际应用的需要，近十多年出现很多计算效率高的Skyline的算法。

1 相关技术

设R是有d个属性D1，…，Dd的数据集合，R的数据简称为点。点x表示为x=(x1，…，xd)。对于任意两个点 x、y，如果 xi≤yi(i=1，…，d)，且存在 j使得xj＜yj，则称x支配y。如果不存在R中的点y支配x，则称x是R的Skyline点，简称为R的SP。R的子集合M的所有SP的集合记作SKY(M)。

1.1 BNL 算法

最早的算法是BNL算法［1］，简述如下。在主存中设置大小固定的窗口，R的点顺序进入检测。如果点x被窗口的一个点支配，x不可能是SP而被丢弃。如果x支配窗口中的一些点，这些点也被丢弃。如果x与窗口的点都互不支配，当窗口不满时，x插入窗口;否则x插入临时文件中。当所有点都被检测完毕，算法的一轮结束。下轮将临时文件(如果不空)的点顺序进入检测。如果某一轮结束时临时文件是空集，BNL算法结束，窗口的点集即为 SKY(R)。BNL算法有较好的效率，不足之处是已经进入临时文件的点在同一轮中没有机会和后进入的点比较，从而需要多轮计算。

1.2 SFS 算法

预排序算法(SFS算法)［2-3］是对BNL算法所作的改进。算法借助R上的单调分值函数f将R的点拓扑排序(将f值小的点排在前面)。如果点r排在t的后面，则r不可能支配t。和BNL算法一样，SFS算法设置窗口。当点x进入检测时，由于窗口中的点都排在x前，不可能被x支配。如果x被窗口的点支配，则x被丢弃，否则x必是R的SP而插入窗口。这就保证在窗口中的点都是SP。当R的点都被检测，算法结束。SFS算法的优点是不需要多轮检测，付出将R的点排成全序的代价。

1.3 其他算法

SKY查询算法已经得到很多研究，如分治算法、NN 算法、索引算法和位图算法［6］;BBS 算法［7］、分布数据的 Skyline 算法［8-9］;概率 Skyline 算法［10］;子空间Skyline算法［11-13］、数据流滑动窗口的 SKY算法［14-15］等。

1.4 本文的工作

本文所做的工作是对SFS算法的改进。SFS算法借助单调分值函数f将R的点排序，在本文中将排序的结果进一步分成若干组，每一组的点的f值相等，避免同一组中的点的比较。在排序的过程中附加分组，不需要增加额外的开销。主要的结论是:(1)分组算法所需要计算的比较支配次数≤m(n－m/2－1/2)(其中n是R的点的个数，m是R的SP的个数)。这个上界比较渐近复杂度精确。(2)分组算法比SFS算法减少的比较支配次数≥m(m－k)/2k，其中k是组数。在极端的情形下，k=m(每一个组只有一个SP)，分组算法和SFS算法相同。如果k=m/a(假设平均每组 a个SP)，则 m(m－k)/2k=m(a－1)/2。

2 分组迭代算法

2.1 分组

设f是R上单调分值函数，x，y∈R，如果x支配y，则 f(x)＜f(y)［2］。因此可将 R 的点按照 f的值拓扑排序，排在前面的点的f的值小。因此，如果R的点x排在y的前面，则y不可能支配x。因为R是有限集，所以f的值域是有限集。将这个集合中的数值排成升序:c1＜…＜ck，令 Ri={x|f(x)=ci}(i=1，…，k)，称为R关于单调分值函数f的分组。

定理1 (1)Ri中的点互不支配。(2)设i＜j，则Rj的点不可能支配Ri的点。

证明:(1)设Ri的点x支配y，则f(x)＜f(y)。但f(x)=f(y)=ci，矛盾。(2)设 x∈Ri，y∈Rj。因为 i＜j，则x排在y的前面，因此y不支配x。

令 M1=R1，Mi=Mi－1∪Ri(1 ＜ i≤k)。根据定理1，可以推出:(1)M1⊆SKY(R)。(2)Mi的点不被Ri+1∪…∪Rk的点支配。(3)SKY(Mi)⊆SKY(R)(1＜i≤k)。

定理2(1)SKY(M1)=M1。(2)SKY(Mi)=SKY(Mi－1)∪{x∈Ri|x 不被 SKY(Mi－1)的点支配}(1 ＜i≤k)。

证明:(1)因为M1⊆SKY(R)，所以SKY(M1)=M1。(2)因为 Mi=Mi－1∪Ri，所以 x∈SKY(Mi)当且仅当:当 x∈Mi－1时 x 不被 Mi－1的点支配(x∈SKY(Mi－1));或当 x∈Ri时 x 不被 Mi－1的点支配(因此 x不被SKY(Mi－1)的点支配)。因此x∈SKY(Mi)当且仅当 x∈SKY(Mi－1)∪{x∈Ri|x 不被 SKY(Mi－1)的点支配}。

2.2 分组算法

上述定理提供了计算SKY(R)的迭代算法。从SKY(M1)=M1起，将 Ri中不被 SKY(Mi－1)的点支配的点添加到SKY(Mi－1)中，就得到SKY(Mi)。最后SKY(Mk)=SKY(R)。

输入:数据集R，单调增函数f。

输出:SKY(R)。

预备:根据f的值将R的点分成子集R1，…，Rk。

(1)S=R1;i=2;

(2)T=Ri;U=Φ;

(3)如果T≠Φ，取x∈T;

(3.1)若有 S的点支配 x，T=T－{x};回到(3);

(3.2)否则 U=U∪{x};T=T－{x};回到(3);

(4)如果T=Φ，S=S∪U;

(4.1)若 i＜k，i++;回到(2);

(4.2)若i=k，输出S=SKY(R);算法结束。

3 分组算法的效率

3.1 比较次数的上界C(n，m)

在这一节将证明:设R有n个数据点，SKY(R)有m个点，用分组算法计算SKY(R)所需的数据间支配关系的比较次数C(n，m)的上界为m(n－m/2－1/2)，并且举出例子表明可以达到这个上界。C(n，m)的这个估计值比起渐近复杂度要精确。

设R的分组中的每一个Ri的点的个数为ni，则有n1+…+nk=n(ni＞0)。设 Ri中插入 SKY(R)的点的个数为 mi，则有:(1)n1=m1;(2)0≤mi≤ni(i＞1);(3)m1+…+mk=m。适合这3个条件的m1，…，mk称为m的一个分布。在算法中，当计算到Ri时(i＞1)，已有 si=m1+ … +mi－1点在 SKY(Mi)中，因此Ri的每一个点要作的支配关系的比较次数是si，所以对于Ri的点要作的支配关系的比较次数是nisi。这表明计算SKY(R)所需的数据间支配关系的比较次数为:

定理3(1)当C(n，m)取最大值时，m的分布必然是:m1=n1，…，mj－1=nj－1，0≤mj＜ nj(j＞1)，mj+1=…=mk=0。(2)C(n，m)≤m(n－m/2－1/2)。

证明:(1)先证明:当C(n，m)取最大值时，如果m的分布使得存在j使得 mj＜nj，则mj+1=0。若不然，mj+1≠0，令正实数 a使得 mj+1≥a且 mj+a≤nj，令 hj=mj+a，hj+1=mj+1－ a，hi=mi(i≠j，j+1)，不难看出h1，…，hk仍然是m的分布。设C1(n，m)是对应这个分布所得的比较次数，则在2个和数中，只有i=j+1的项不同(因为mj+mj+1=hj+hj+1)。因此C1(n，m)－C(n，m)=nj+1(hj－mj)=nj+1a＞0。这就和C(n，m)最大矛盾。因此mj+1=0。再由于mj+1=0＜nj+1，又可以推出mj+2=…=mk=0。

(2)根据上述定理，可知当C(n，m)取最大值时:

①在第一个和式中 n1，…，nj－1换成 m1，…，mj－1，第j项的nj用nj－mj和mj代替，则第一个和式等于:

因为mi都是非负整数，所以m12+… +mj2≥m1+…+mj=m。因此上式≤(m2－m)/2+(nj－mj)(m －mj)。

②第二个和式等于:

证毕。

例1 设在R中所有 ni、mi都等于1，n=m=k，则C(n，m)=1+2+… +(k－1)=k(k－1)/2。因为m(n－m/2－1/2)=k(k－k/2－1/2)=k(k－1)/2。因此C(n，m)=m(n－m/2－1/2)。此例表明在定理3中给出的C(n，m)可以取得上界，因此定理3的上界估计是最好的。

3.2 分组算法和SFS算法的比较

如果在SFS算法中，所利用的单调分值函数f使得每一个组只有一个点，分组算法与SFS算法相同。如果分组的个数k＜n，则分组算法比SFS算法的效率高。

定理4 分组算法比SFS算法减少比较支配次数≥m(m－k)/2k。

证明:在SFS算法中，Ri的ni个点的顺序和已经在SKY的点中比较了支配关系，在这些点中，有mi个SP在算法中需要作比较支配检测，而在分组算法中，可免除这种检测，因而，可减少(mi－1)mi/2个比较支配次数，因此，分组算法减少比较支配次数等于:

因为m12+…+mk2的最小值在m1=…=mk=m/k时取得，因此，上式≥m(m－k)/2k。

3.3 分组算法的意义

如果在计算中，分组的个数k较少，则分组算法就有显著的优点。如果数据集R的属性比较多，并且每一个属性的取值较多，则单调分值函数f的不同值也就比较多，分组的个数k也就较多。但在实际计算中，一些属性的取值很少，如饭店的等级，通常只有3个。对于取值较多的属性(如距离)也能够根据需要将属性的值划分为少数几个区段，以这几个区段的中值为属性的取值，就可以使属性取值的个数减少。对于用户来说，差别不大的属性值是可以接受的。因此，在实际计算中，总是可以使得分组的个数很少。另一方面，在实际应用中，用户能够根据自己的需求在前几个分组的SP点中选取自己需要的点，不必等待所有的SP都计算出来。这就表明，分组算法更适合用户的需求。

4 结束语

多维数据系统的Skyline是非常有实用意义的概念，因此各种算法层出不穷。在各种算法中，预排序算法有很多优点。本文提出的在排序基础上的分组算法提高了计算效率，有很大的实用价值。但是分组算法仍然有值得进一步研究的方面，如比较支配关系次数的上界的估值还不够精细，各种不同的单调分值函数对于分组个数的影响等，有待今后继续研究。

［1］Borzsony S，Kossmann D，Stocker K.The skyline operator［C］//Proceedings of the 17th IEEE International Conference on Data Engineering.2001:421-430.

［2］Chomicki J，Godfrey P，Gryz J，et al.Skyline with Presorting［R］.York University，2002.

［3］Chomicki J，Godfrey P，Gryz J，et al.Skyline with presorting［C］//Proceedings of the 19th IEEE International Conference on Data Engineering.2003:717-719.

［4］Kung H T，Luccio F，Preparata F P.On finding the maxima of a set of vectors［J］.Journal of the Association for Computing Machinery，1975，22(4):469-476.

［5］Bentley J L，Kung H T，Schkolnick M，et al.On the average number of maxima in a set of vectors and applications［J］.Journal of the Association for Computing Machinery，1978，25(4):536-543.

［6］Tan K L，Eng P K，Ooi B C.Efficient progressive skyline computation［C］//Proceedings of the 27th IEEE International Conference on Very Large Data Bases.Rome，Italy，2001:301-310.

［7］Papadias D，Tao Y，Fu G，et al.Progressive skyline computation in database systems［J］.ACM Transactions on Database Systems，2005，30(1):41-82.

［8］Balke W-T，Guntzer U，Zheng J X.Efficient distributed skylining for Web information systems［C］//Proceedings of the 9th IEEE International Conference on Extending Database Technology.Crete，Greece，2004:256-273.

［9］Hose K.Processing skyline queries in P2P systems［C］//Proceedings of VLDB 2005 PhD Workshop.Trondheim，Norway，2005:36-40.

［10］Pei J，Jiang B，Lin X，et al.Probabilistic skylines on uncertain data［C］//Proceedings of the 33rd IEEE International Conference on Very Large Data Bases.Vienna，Austria，2007:15-26.

［11］Vlachou A，Doulkeridis C，Kotidis Y，et al.SKYPEER:Efficient subspace skyline computation over distributed data［C］//Proceedings of the 23rd IEEE International Conference on Data Engineering.2007:416-425.

［12］Tao Y，Xiao X，Pei J.SUBSKY:Efficient computation of skylines in subspaces［C］//Proceedings of the 22nd IEEE International Conference on Data Engineering.2006.

［13］Pei J，Yuan Y，Lin X，et al.Towards multidimensional subspace skyline analysis［J］.ACM Transactions on Database Systems，2006，31(4):1335-1381.

［14］Tao Y，Papadias D.Maintaining sliding window skylines on data streams［J］.IEEE Transactions on Knowledge and Data Engineering，2006，18(3):377-391.

［15］Lin X，Yuan Y，Wang W，et al.Stabbing the skyline:Efficient skyline computation over sliding windows［C］//Proceedings of the 21st IEEE International Conference on Data Engineering.2005:502-513.