劉 萍

(甘肅民族師范學院計算機科學系，甘肅 合作 747000)

0 引言

S.Borzsony等在文獻［1］中提出輪廓(Skyline)的概念，用來表述在多維的數據系統(tǒng)R中經過評估選出的占優(yōu)的數據(元組)。多維評估的方法通常稱為多元目標優(yōu)化決策。假設R是有d維屬性的數據系統(tǒng)，每一個屬性的值都是能夠比較優(yōu)劣的域，通常用正實數表示屬性的值。一般說來，一些屬性值以大的數為優(yōu)，另一些值則以小的數為優(yōu)。以文獻［1］中舉的例子(很多文獻都引用這個例子)為例，對于旅游勝地拿騷(巴哈馬群島)的旅館，可以有多個指標來評估旅館的優(yōu)劣，如旅客關心的價格、旅館到海濱的距離、旅館的星級等。其中價格指標以小的數為優(yōu)，星級指標以大的數為優(yōu)。在旅游指南(列出所有旅館的數據)中，游客不可能找到各項指標都占優(yōu)的旅館。旅客感興趣的顯然是這種旅館，不存在一個在所有指標都超過它的旅館。這種旅館就是文獻［1］中所說的旅館集合中的Skyline。顯然Skyline旅館不是唯一的，這就方便旅客根據自己的偏愛做出選擇。多元目標優(yōu)化決策的應用非常廣泛，促使了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算法的優(yōu)點是不需要多輪檢測，付出將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)

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

4 結束語

多維數據系統(tǒng)的Skyline是非常有實用意義的概念，因此各種算法層出不窮。在各種算法中，預排序算法有很多優(yōu)點。本文提出的在排序基礎上的分組算法提高了計算效率，有很大的實用價值。但是分組算法仍然有值得進一步研究的方面，如比較支配關系次數的上界的估值還不夠精細，各種不同的單調分值函數對于分組個數的影響等，有待今后繼續(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，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.