計(jì)算SKY的預(yù)排序分組算法

劉 萍

(甘肅民族師范學(xué)院計(jì)算機(jī)科學(xué)系，甘肅 合作 747000)

0 引言

S.Borzsony等在文獻(xiàn)［1］中提出輪廓(Skyline)的概念，用來表述在多維的數(shù)據(jù)系統(tǒng)R中經(jīng)過評(píng)估選出的占優(yōu)的數(shù)據(jù)(元組)。多維評(píng)估的方法通常稱為多元目標(biāo)優(yōu)化決策。假設(shè)R是有d維屬性的數(shù)據(jù)系統(tǒng)，每一個(gè)屬性的值都是能夠比較優(yōu)劣的域，通常用正實(shí)數(shù)表示屬性的值。一般說來，一些屬性值以大的數(shù)為優(yōu)，另一些值則以小的數(shù)為優(yōu)。以文獻(xiàn)［1］中舉的例子(很多文獻(xiàn)都引用這個(gè)例子)為例，對(duì)于旅游勝地拿騷(巴哈馬群島)的旅館，可以有多個(gè)指標(biāo)來評(píng)估旅館的優(yōu)劣，如旅客關(guān)心的價(jià)格、旅館到海濱的距離、旅館的星級(jí)等。其中價(jià)格指標(biāo)以小的數(shù)為優(yōu)，星級(jí)指標(biāo)以大的數(shù)為優(yōu)。在旅游指南(列出所有旅館的數(shù)據(jù))中，游客不可能找到各項(xiàng)指標(biāo)都占優(yōu)的旅館。旅客感興趣的顯然是這種旅館，不存在一個(gè)在所有指標(biāo)都超過它的旅館。這種旅館就是文獻(xiàn)［1］中所說的旅館集合中的Skyline。顯然Skyline旅館不是唯一的，這就方便旅客根據(jù)自己的偏愛做出選擇。多元目標(biāo)優(yōu)化決策的應(yīng)用非常廣泛，促使了Skyline的研究。為了實(shí)現(xiàn)Skyline查詢，文獻(xiàn)［1］提出一種嵌套SQL查詢(nested SQL query)。然而這種方法需要對(duì)于每一個(gè)旅館和所有的旅館作比較，開銷太大，沒有實(shí)用價(jià)值。因?yàn)閷?shí)際應(yīng)用的需要，近十多年出現(xiàn)很多計(jì)算效率高的Skyline的算法。

1 相關(guān)技術(shù)

設(shè)R是有d個(gè)屬性D1，…，Dd的數(shù)據(jù)集合，R的數(shù)據(jù)簡稱為點(diǎn)。點(diǎn)x表示為x=(x1，…，xd)。對(duì)于任意兩個(gè)點(diǎn) x、y，如果 xi≤yi(i=1，…，d)，且存在 j使得xj＜yj，則稱x支配y。如果不存在R中的點(diǎn)y支配x，則稱x是R的Skyline點(diǎn)，簡稱為R的SP。R的子集合M的所有SP的集合記作SKY(M)。

1.1 BNL 算法

最早的算法是BNL算法［1］，簡述如下。在主存中設(shè)置大小固定的窗口，R的點(diǎn)順序進(jìn)入檢測。如果點(diǎn)x被窗口的一個(gè)點(diǎn)支配，x不可能是SP而被丟棄。如果x支配窗口中的一些點(diǎn)，這些點(diǎn)也被丟棄。如果x與窗口的點(diǎn)都互不支配，當(dāng)窗口不滿時(shí)，x插入窗口;否則x插入臨時(shí)文件中。當(dāng)所有點(diǎn)都被檢測完畢，算法的一輪結(jié)束。下輪將臨時(shí)文件(如果不空)的點(diǎn)順序進(jìn)入檢測。如果某一輪結(jié)束時(shí)臨時(shí)文件是空集，BNL算法結(jié)束，窗口的點(diǎn)集即為 SKY(R)。BNL算法有較好的效率，不足之處是已經(jīng)進(jìn)入臨時(shí)文件的點(diǎn)在同一輪中沒有機(jī)會(huì)和后進(jìn)入的點(diǎn)比較，從而需要多輪計(jì)算。

1.2 SFS 算法

預(yù)排序算法(SFS算法)［2-3］是對(duì)BNL算法所作的改進(jìn)。算法借助R上的單調(diào)分值函數(shù)f將R的點(diǎn)拓?fù)渑判?將f值小的點(diǎn)排在前面)。如果點(diǎn)r排在t的后面，則r不可能支配t。和BNL算法一樣，SFS算法設(shè)置窗口。當(dāng)點(diǎn)x進(jìn)入檢測時(shí)，由于窗口中的點(diǎn)都排在x前，不可能被x支配。如果x被窗口的點(diǎn)支配，則x被丟棄，否則x必是R的SP而插入窗口。這就保證在窗口中的點(diǎn)都是SP。當(dāng)R的點(diǎn)都被檢測，算法結(jié)束。SFS算法的優(yōu)點(diǎn)是不需要多輪檢測，付出將R的點(diǎn)排成全序的代價(jià)。

1.3 其他算法

SKY查詢算法已經(jīng)得到很多研究，如分治算法、NN 算法、索引算法和位圖算法［6］;BBS 算法［7］、分布數(shù)據(jù)的 Skyline 算法［8-9］;概率 Skyline 算法［10］;子空間Skyline算法［11-13］、數(shù)據(jù)流滑動(dòng)窗口的 SKY算法［14-15］等。

1.4 本文的工作

本文所做的工作是對(duì)SFS算法的改進(jìn)。SFS算法借助單調(diào)分值函數(shù)f將R的點(diǎn)排序，在本文中將排序的結(jié)果進(jìn)一步分成若干組，每一組的點(diǎn)的f值相等，避免同一組中的點(diǎn)的比較。在排序的過程中附加分組，不需要增加額外的開銷。主要的結(jié)論是:(1)分組算法所需要計(jì)算的比較支配次數(shù)≤m(n－m/2－1/2)(其中n是R的點(diǎn)的個(gè)數(shù)，m是R的SP的個(gè)數(shù))。這個(gè)上界比較漸近復(fù)雜度精確。(2)分組算法比SFS算法減少的比較支配次數(shù)≥m(m－k)/2k，其中k是組數(shù)。在極端的情形下，k=m(每一個(gè)組只有一個(gè)SP)，分組算法和SFS算法相同。如果k=m/a(假設(shè)平均每組 a個(gè)SP)，則 m(m－k)/2k=m(a－1)/2。

2 分組迭代算法

2.1 分組

設(shè)f是R上單調(diào)分值函數(shù)，x，y∈R，如果x支配y，則 f(x)＜f(y)［2］。因此可將 R 的點(diǎn)按照 f的值拓?fù)渑判?，排在前面的點(diǎn)的f的值小。因此，如果R的點(diǎn)x排在y的前面，則y不可能支配x。因?yàn)镽是有限集，所以f的值域是有限集。將這個(gè)集合中的數(shù)值排成升序:c1＜…＜ck，令 Ri={x|f(x)=ci}(i=1，…，k)，稱為R關(guān)于單調(diào)分值函數(shù)f的分組。

定理1 (1)Ri中的點(diǎn)互不支配。(2)設(shè)i＜j，則Rj的點(diǎn)不可能支配Ri的點(diǎn)。

證明:(1)設(shè)Ri的點(diǎn)x支配y，則f(x)＜f(y)。但f(x)=f(y)=ci，矛盾。(2)設(shè) x∈Ri，y∈Rj。因?yàn)?i＜j，則x排在y的前面，因此y不支配x。

令 M1=R1，Mi=Mi－1∪Ri(1 ＜ i≤k)。根據(jù)定理1，可以推出:(1)M1?SKY(R)。(2)Mi的點(diǎn)不被Ri+1∪…∪Rk的點(diǎn)支配。(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)的點(diǎn)支配}(1 ＜i≤k)。

證明:(1)因?yàn)镸1?SKY(R)，所以SKY(M1)=M1。(2)因?yàn)?Mi=Mi－1∪Ri，所以 x∈SKY(Mi)當(dāng)且僅當(dāng):當(dāng) x∈Mi－1時(shí) x 不被 Mi－1的點(diǎn)支配(x∈SKY(Mi－1));或當(dāng) x∈Ri時(shí) x 不被 Mi－1的點(diǎn)支配(因此 x不被SKY(Mi－1)的點(diǎn)支配)。因此x∈SKY(Mi)當(dāng)且僅當(dāng) x∈SKY(Mi－1)∪{x∈Ri|x 不被 SKY(Mi－1)的點(diǎn)支配}。

2.2 分組算法

上述定理提供了計(jì)算SKY(R)的迭代算法。從SKY(M1)=M1起，將 Ri中不被 SKY(Mi－1)的點(diǎn)支配的點(diǎn)添加到SKY(Mi－1)中，就得到SKY(Mi)。最后SKY(Mk)=SKY(R)。

輸入:數(shù)據(jù)集R，單調(diào)增函數(shù)f。

輸出:SKY(R)。

預(yù)備:根據(jù)f的值將R的點(diǎn)分成子集R1，…，Rk。

(1)S=R1;i=2;

(2)T=Ri;U=Φ;

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

(3.1)若有 S的點(diǎn)支配 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);算法結(jié)束。

3 分組算法的效率

3.1 比較次數(shù)的上界C(n，m)

在這一節(jié)將證明:設(shè)R有n個(gè)數(shù)據(jù)點(diǎn)，SKY(R)有m個(gè)點(diǎn)，用分組算法計(jì)算SKY(R)所需的數(shù)據(jù)間支配關(guān)系的比較次數(shù)C(n，m)的上界為m(n－m/2－1/2)，并且舉出例子表明可以達(dá)到這個(gè)上界。C(n，m)的這個(gè)估計(jì)值比起漸近復(fù)雜度要精確。

設(shè)R的分組中的每一個(gè)Ri的點(diǎn)的個(gè)數(shù)為ni，則有n1+…+nk=n(ni＞0)。設(shè) Ri中插入 SKY(R)的點(diǎn)的個(gè)數(shù)為 mi，則有:(1)n1=m1;(2)0≤mi≤ni(i＞1);(3)m1+…+mk=m。適合這3個(gè)條件的m1，…，mk稱為m的一個(gè)分布。在算法中，當(dāng)計(jì)算到Ri時(shí)(i＞1)，已有 si=m1+ … +mi－1點(diǎn)在 SKY(Mi)中，因此Ri的每一個(gè)點(diǎn)要作的支配關(guān)系的比較次數(shù)是si，所以對(duì)于Ri的點(diǎn)要作的支配關(guān)系的比較次數(shù)是nisi。這表明計(jì)算SKY(R)所需的數(shù)據(jù)間支配關(guān)系的比較次數(shù)為:

定理3(1)當(dāng)C(n，m)取最大值時(shí)，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)先證明:當(dāng)C(n，m)取最大值時(shí)，如果m的分布使得存在j使得 mj＜nj，則mj+1=0。若不然，mj+1≠0，令正實(shí)數(shù) a使得 mj+1≥a且 mj+a≤nj，令 hj=mj+a，hj+1=mj+1－ a，hi=mi(i≠j，j+1)，不難看出h1，…，hk仍然是m的分布。設(shè)C1(n，m)是對(duì)應(yīng)這個(gè)分布所得的比較次數(shù)，則在2個(gè)和數(shù)中，只有i=j+1的項(xiàng)不同(因?yàn)閙j+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)根據(jù)上述定理，可知當(dāng)C(n，m)取最大值時(shí):

①在第一個(gè)和式中 n1，…，nj－1換成 m1，…，mj－1，第j項(xiàng)的nj用nj－mj和mj代替，則第一個(gè)和式等于:

因?yàn)閙i都是非負(fù)整數(shù)，所以m12+… +mj2≥m1+…+mj=m。因此上式≤(m2－m)/2+(nj－mj)(m －mj)。

②第二個(gè)和式等于:

證畢。

例1 設(shè)在R中所有 ni、mi都等于1，n=m=k，則C(n，m)=1+2+… +(k－1)=k(k－1)/2。因?yàn)閙(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的上界估計(jì)是最好的。

3.2 分組算法和SFS算法的比較

如果在SFS算法中，所利用的單調(diào)分值函數(shù)f使得每一個(gè)組只有一個(gè)點(diǎn)，分組算法與SFS算法相同。如果分組的個(gè)數(shù)k＜n，則分組算法比SFS算法的效率高。

定理4 分組算法比SFS算法減少比較支配次數(shù)≥m(m－k)/2k。

證明:在SFS算法中，Ri的ni個(gè)點(diǎn)的順序和已經(jīng)在SKY的點(diǎn)中比較了支配關(guān)系，在這些點(diǎn)中，有mi個(gè)SP在算法中需要作比較支配檢測，而在分組算法中，可免除這種檢測，因而，可減少(mi－1)mi/2個(gè)比較支配次數(shù)，因此，分組算法減少比較支配次數(shù)等于:

因?yàn)閙12+…+mk2的最小值在m1=…=mk=m/k時(shí)取得，因此，上式≥m(m－k)/2k。

3.3 分組算法的意義

如果在計(jì)算中，分組的個(gè)數(shù)k較少，則分組算法就有顯著的優(yōu)點(diǎn)。如果數(shù)據(jù)集R的屬性比較多，并且每一個(gè)屬性的取值較多，則單調(diào)分值函數(shù)f的不同值也就比較多，分組的個(gè)數(shù)k也就較多。但在實(shí)際計(jì)算中，一些屬性的取值很少，如飯店的等級(jí)，通常只有3個(gè)。對(duì)于取值較多的屬性(如距離)也能夠根據(jù)需要將屬性的值劃分為少數(shù)幾個(gè)區(qū)段，以這幾個(gè)區(qū)段的中值為屬性的取值，就可以使屬性取值的個(gè)數(shù)減少。對(duì)于用戶來說，差別不大的屬性值是可以接受的。因此，在實(shí)際計(jì)算中，總是可以使得分組的個(gè)數(shù)很少。另一方面，在實(shí)際應(yīng)用中，用戶能夠根據(jù)自己的需求在前幾個(gè)分組的SP點(diǎn)中選取自己需要的點(diǎn)，不必等待所有的SP都計(jì)算出來。這就表明，分組算法更適合用戶的需求。

4 結(jié)束語

多維數(shù)據(jù)系統(tǒng)的Skyline是非常有實(shí)用意義的概念，因此各種算法層出不窮。在各種算法中，預(yù)排序算法有很多優(yōu)點(diǎn)。本文提出的在排序基礎(chǔ)上的分組算法提高了計(jì)算效率，有很大的實(shí)用價(jià)值。但是分組算法仍然有值得進(jìn)一步研究的方面，如比較支配關(guān)系次數(shù)的上界的估值還不夠精細(xì)，各種不同的單調(diào)分值函數(shù)對(duì)于分組個(gè)數(shù)的影響等，有待今后繼續(xù)研究。

［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，F(xiàn)u 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.