k*-支配Skyline查詢在實驗數據檢索中的應用

黃金晶， 趙 雷

(1. 蘇州工業職業技術學院 軟件與服務外包學院， 江蘇 蘇州 215104;2. 蘇州大學 計算機科學與技術學院， 江蘇 蘇州 215006)

0 引 言

實驗通常會產生大量的實驗數據。實驗數據中較為“突出”的數據往往具有較高的價值。如何從大量的實驗數據中檢索出“突出”的數據，是一個值得研究的問題。找到這些較為“突出”的數據，常常是實驗結果處理過程中需要完成的工作。當樣本點數量巨大且屬性眾多的時候，這項任務非常具有挑戰性。

利用多關鍵字查詢技術可以幫助用戶檢索需要的實驗數據。Skyline查詢是解決多關鍵字查詢的有效方法之一。Skyline查詢是從數據集中選出不被支配的全部數據點，近年來在多目標決策、用戶偏好查詢、可視化等方面應用較為廣泛。然而，當數據量較大時，Skyline查詢響應的時間較長；當數據維度較高時，數據間較難產生支配關系，導致Skyline查詢返回的結果集較大，不易給出有價值的查詢結果。為解決這一問題，Chan等[14]人提出了k-支配Skyline查詢，只要數據點在任意k維度上存在支配關系即可。但是k-支配Skyline查詢有可能產生循環支配的問題，導致查詢沒有結果。

Top-k查詢是應對多關鍵字查詢的另一種常用方法。Top-k查詢僅返回k個結果，可以有效解決結果集太大帶來的結果有效性問題。但是，大多數top-k查詢需要借助評價函數。評價函數雖然可以體現用戶偏好，但是評價函數的確定具有一定的主觀性，結果未必是用戶滿意的。因此，不恰當的評價函數對結果集的有效性同樣可能產生較大的影響。

本文提出一種k*-支配Skyline查詢，將其運用于實驗數據檢索中。該查詢在傳統k-支配Skyline查詢中引入用戶偏好的優先級，消除了k-支配存在循環支配的可能性，既能保證產生結果又能控制結果集的大小，同時查詢返回的結果也更加符合用戶的偏好。將用戶偏好的優先級引入支配關系，是同時解決上述多個問題的關鍵，也是本文最主要的創新點和貢獻。

1 相關研究

Skyline查詢[1]由Borzsonyi等[1]于2001年引入數據查詢領域，提出塊嵌套循環(Block Nested Loop, BNL)算法以及分區回歸(Divide-and-Conquer, DC)算法，是數據庫、數據挖掘領域的經典研究問題，而后產生了很多新的高效算法。比如，Kossmann等[2]提出的近鄰查詢算法(Nearest Neighor, NN)，給出一種基于R-樹索引的計算方法；Tan等[3]提出了計算Skyline的位圖算法；Papadias等[4-5]提出了一種分支界限算法(Branch and Bound Skyline, BBS)；文獻[6-8]中討論了子空間的Skyline計算問題；Lian等[9]提出了在不確定的數據集上進行Skyline計算；Chen等[10]給出了索引方式的top-k空間關鍵字查詢的方法。當數據量大，數據源分布較多時，集中式環境下進行數據處理效率較低，Huang等[11]提出了分布式環境下的Skyline查詢；文獻[12-13]中分別給出了一種在海量數據集中使用MapReduce的高效Skyline查詢處理方法。在高維數據集中，數據點之間較難產生支配關系，Chan等[14]提出了k-支配skyline查詢，減少了高維空間中Skyline查詢返回的數據點；此外還有一系列對k-支配算法的改進，比如文獻[15]中提出了一種使用簡化預排序的k-支配skyline查詢算法；文獻[16]中提出了一種基于索引的高效k-支配skyline算法。

上述研究成果著重解決在大數據集或高維度數據集上Skyline計算的效率問題，未能有效解決對于高維數據集上結果集較大、結果集有效性差的問題。同時，上述研究成果對用戶偏好并未給予足夠的關注。基于上述原因，本文的研究將著重從兩個方面解決Skyline查詢結果集的有效性問題，一方面既可保證產生結果集，又能控制結果集的大小，另一方面能滿足用戶偏好。

2 相關概念描述

本文在k-支配skyline的基礎上，提出了k*-支配skyline算法，下面首先對k-支配skyline的相關概念進行描述。

定義1支配。給定一個d維的數據集D={D1，D2,…,Dd},p、q為D中的數據點，p={p1,p2，…，pd},q={q1,q2,…,qd},若p在d個維度上的取值都不比q差，且至少有一個維度上的值比q好，則稱p支配q[1]。

定義2Skyline數據集。對于數據集D中的數據點p，若D中不存在能支配p的數據點，則p為D中的Skyline點。D中所有的Skyline點的集合就是Skyline數據集。

為便于展示，以2維空間舉例說明Skyline數據集。在圖1中，不失一般性，設數值越小越好，則b點顯然支配e點。而a與b之間，盡管橫坐標ab，因而它們之間不構成支配關系。圖1中，a、b、c、d4個點組成了Skyline數據集。

圖1 skyline數據集舉例

定義3k-支配。對于d維數據集D中的點p和q，若存在k個維度使得p在這k維上的值都不差于q在這k維度的值，且在這k個維度上，至少有一個維度使得p的值優于q，稱p點k-支配q點[10]。

3 k*-支配Skyline查詢

3.1 k*-支配Skyline定義

由于k-支配可能存在循環支配的現象，比如表1所示的數據點，假定在每個維度上，屬性值越大越好。顯然p13-支配p2，p23-支配p3，p33-支配p4，而p4在d3、d4、d5維度上的值大于p1，因而p43-支配p1。

表1 3-支配舉例

為了消除循環支配，本文提出了一種新的k*-支配Skyline查詢，考慮用戶偏好的優先級關系，使得查詢結果更加符合用戶的實際需求。對于每一個用戶來說，查詢關鍵字的序列不同，偏好的重點不同，因而可以定義一個偏好優先關系R。

定義4R關系(偏好優先關系)。設有一個n維的數據集D={D1,D2,…,Dn}，不失一般性，設屬性順序S=(D1,D2,…,Dn)。有元組x={x1,x2,…,xn}和y={y1,y2,…，yn},如關系R={|x,y∈D}，滿足?i(1≤i≤n)，有xi>yi，且?j(1≤j

為了更好的解釋關系R，下面以實例說明。設兩個不同的用戶查詢x和y，在相同維度上的數值x={2,1,1,1,1}，y={2,1,0,1,1}，當i=3時，x3>y3且x1=y1，x2=y2，則x和y滿足偏好優先關系R，即x優于y。

引理1R關系具有反自反性、反對稱性和傳遞性。

證明

(1) 反自反性。二元關系，必然找不到一個維度i滿足xi>yi，因而不滿足R關系，即R關系具有反自反性。

(2) 反對稱性。設滿足R關系，則在1到n中能找到一個i使得i之前所有維度上x的值和y值相等，而在i維度上x的值大于y。那么顯然不能滿足R關系，即R關系具有反對稱性。

(3) 傳遞性。設，都滿足R關系，則以下關系式成立(i∈(1,n]，j∈(1,n])：

由上可得x1>z1，或?k∈(1,n]有x1=z1,x2=z2,…,xk-1=zk-1,xk>zk，即說明x和z之間滿足R關系，即R關系具有傳遞性。

證畢。

k*-支配是在k-支配中加入了偏好優先關系R。下面給出k*-支配的定義。

定義5k*-支配。在一個n維的數據集D={D1,D2,…,Dn}上，p1和p2為D上的數據點，如果p1k-支配p2且p1和p2之間滿足偏好優先關系R，則稱p1k*-支配p2。

定理1k*-支配不存在循環支配關系。

證明設存在一個維的數據集D={D1，D2,…,Dn},p1,p2,…,pn為D上的數據點，則不存在這樣一個序列(px,1,px,2,…,px,m)，當px,1k*-支配px,2，px,2k*-支配px,3，…，px,m-1k*-支配px,m時，有px,mk*-支配px,1。

根據k*-支配的定義，px,1k*-支配px,2，說明px,1k-支配px,2的同時偏好優先級大于px,2，同理，px,m-1k*-支配px,m，說明px,m-1k-支配pm的同時偏好優先級大于pm，由引理1可知，R關系具有反對稱性和傳遞性，說明不滿足偏好優先關系R，即px,m不能k*-支配px,1。

證畢。

定義6k*-支配Skyline。k*-支配Skyline是不被任何點k*-支配的數據點所組成的集合。

計算k*-支配Skyline是在k-支配Skyline的基礎上，需要引入屬性的優先級關系。不同的用戶，可以指定不同的屬性優先級關系。在相同的數據集和相同的k值情況下，不同的屬性優先級情況下會查詢得到不同的結果。

3.2 k*-支配Skyline算法

3.2.1樸素算法(NA)

對數據集D中的每一個數據點n，將其與D中的其他所有數據點進行比較，如果p不能被D中的其他數據點k*-支配，則p是k*-支配Skyline數據集中的點。該算法對數據集中的每一個p元素都需要計算集合中其他元素是否能k*-支配p，因而計算量較大，稱其為樸素算法(Na?ve Algorithm,NA)。

3.2.2插入排序剪枝算法(ISPA)

由于偏好優先關系具有傳遞性，若在遍歷集合數據的過程中，對數據點按偏好優先關系R進行排序，能對NA算法進行剪枝，加快算法的運行效率。

(1) 算法思想。根據k*-支配的定義，兩個數據點之間需要同時滿足k-支配和偏好優先關系R才是k*-支配。算法設置k*-支配skyline的候選集C和能被k*-支配的數據點組成的排除集L，其中C中的元素按照偏好優先關系升序排列，L中的元素按照偏好優先關系降序排列。對數據集合D中的數據求k*-支配Skyline的插入排序剪枝算法(InsertionSort Pruning Algorithm，ISPA)思想如下：

① 令C=?,L=?。

② 讀取數據集合D中的元素p，若D中沒有元素，則算法結束。

③ 讀取候選集C中的數據點r，如果偏好優先級rp，若r能k-支配p，則將p插入到L中；若不能繼續讀取C中下一個數據點，繼續判斷。如果r=p，意味著兩個數據點完全相同，去除該數據點，直接讀取D中下一個數據p。

④ 若C中已沒有數據點，說明C中沒有數據點能夠支配p。接著掃描L，看其中的數據點(除去③新加入的)能否k*-支配p。由于L中的元素按偏好優先關系降序排列，直接掃描優先級大于p的數據點。若能支配，則將p插入L中，轉入步驟②；若不能，則說明p暫時不能被k*-支配，將其按升序加入R中，轉入步驟②。

(2) 實例演示。為了更好的說明上述算法，下面舉例說明如何在表2所示數據集中，找出3*-支配Skyline的數據點集合。設屬性順序S=(d1,d2,d3,d4,d5,d6)。

表2 數據集

具體步驟如下：

① 令C=?,L=?。

② 讀取p1，因為C和L中沒有元素，直接將p1加入C集合中。

③ 讀取p2，掃描C中的數據點，p2的偏好優先級大于p1，且p2能3-支配p1，因而將p1加入L中，掃描L中的元素，p1為新加入的元素，不重復比較，直接將p2插入C中。C中的元素為{p2}，L中的元素為{p1}。

④ 讀取p3，掃描C中的數據點，p3能3*-支配p2，將p2插入L，而p3不能被L中的p13*-支配，將p3加入C中。C中的元素為{p3}，L中的元素為{p2、p1}。

⑤ 讀取p4，掃描C中的數據點，p3能3*-支配p4，將p4插入L中。C中的元素為{p3}，L中的元素為{p2、p4、p1}。

⑥ 讀取p5，掃描C中的數據點，p5能3*-支配p3，將p3移出C集合，插入L集合。L中的元素為{p3、p2、p4、p1}。由于C中沒有元素，繼續掃描L中的元素，p3為新加入的元素，不重復計算，p2的偏好優先關系小于p5，由于L是按照偏好優先關系降序排列，其后的元素不再掃描，直接將p5插入C中。C中的元素為{p5}，L中的元素為{p3、p2、p4、p1}。

⑦ 讀取p6，掃描C中的數據點，p5能3*-支配p6，將p6插入L集合。C中的元素為{p5}，L中的元素為{p3、p6、p2、p4、p1}。

⑧D中已沒有元素，算法結束。本例中3*-支配Skyline的結果為{p5}。

3.2.3預排序剪枝算法(Pre-sortingPruningAlgorithm,PSPA)

在ISPA算法中，候選集C和移除集L中的元素是按插入排序的方法進行排序的，因而時間復雜度為O(n2)。由于偏好優先關系R具有傳遞性，可以將數據集D按照偏好的優先關系進行升序排序，即排在前面的數據點優先級小于等于后面的數據點，根據k*-支配的定義，排在前面的數據點一定不可能k*-支配后面的數據點。整個數據集中最后一個數據點的偏好優先關系最高，不可能被其他數據點支配，所以k*-支配Skyline一定存在結果集。在對數據進行預排序時，可以使用堆排序、快速排序等方法，減小排序的時間復雜度。

令為k*-支配skyline的結果集，PSPA算法的細節如下：

1. 令C=?；

2. forD中的每個元素pdo

3. flag=0；

4. forC中的每個元素rdo

5. ifr被pk*支配 then

6. 將r移出C；

7. else ifp與r相等 then

8. flag=1；

9. end for

10. if (flag==0)

11. 將p加入到C中；

12. end for

13. returnC；

當數據集中存在兩個完全相同的數據點時，由于偏好優先關系不具有自反性，因而兩個相同點之間不存在k*-支配關系，根據算法該點不重復加入結果集。

使用改進算法對表2中的數據集D求3*-支配skyline數據點集合。首先對D集合進行預排序，結果如表3所示。設屬性順序S=(d1,d2,d3,d4,d5,d6)。

具體步驟如下：

①C=?；

② 讀p1取，C集合中沒有元素，直接將p1加入C集合中；

③ 讀取p4，C集合中有一個元素p1，p4能3*-支

表3 預排序后的數據集

{p4}；

④ 讀取p2，依次掃描C集合中的元素，p2不能3*-支配p4，因而將p2加入C集合，C={p4，p2}；

⑤ 讀取p6，依次掃描C集合中的元素，p6不能3*-支配p4，能3*-支配p2，因而將p2移除C集合，將p6加入C集合，C={p4，p6}；

⑥ 讀取p3，p3能3*-支配C集合中全部的元素，因而p4、p6全部被移出C集合，再將p3加入C中，C={p3}；

⑦ 讀取p5，p5能3*-支配p3，將p3移出C集合，將p3加入C集合，C={p5}；

⑧ 此時D′中已經沒有數據，算法結束，3*-支配Skyline的結果為{p5}，與前述算法求得的結果相同。

4 實驗及結果分析

為驗證算法的正確性和有效性，并研究其效率與各可變因素之間的關系，本文在Windows平臺上實現了上述算法。計算環境所用計算機的配置為8 GB內存、3.2 GHz主頻、i5-3470處理器。實驗使用正相關分布數據、獨立分布數據、反相關分布數據分別對算法進行了驗證，并通過改變相關的參數來進行算法的評估。設k表示k*-支配skyline中的k值，size表示數據集大小，d代表數據集D的維度。

(1) 參數k變化。隨著參數k的變化，算法在正相關分布、獨立分布和反相關分布數據中的性能如圖2所示，其中size為默認值300k，d為默認值15，k從9變化到14。

(2) 數據集size變化。隨著數據集大小的變化，算法在正相關分布、獨立分布和反相關分布數據中的性能如圖3所示，其中k為默認值11，d為默認值15。

(3) 維度d和參數k變化。圖4所示的是參數k和維度d變化時，算法的執行效率。

(a) 正相關分布

圖2 參數k變化時算法運行時間

(a) 正相關分布

圖3 數據集size變化時算法運行時間

由圖2可見，當size和d確定時，k對運行時間有顯著影響。同時可以看出，相對于正相關分布的數據集而言，k對獨立分布和反相關分布的數據集上運行時間的影響更顯著。由圖3可見，當d和k確定時，size對運行時間的影響，在3種不同分布的數據集上大時，算法的運行效率會迅速下降。當k與d相同時，k*-支配Skyline查詢會退化成普通的Skyline查詢。綜上可以看出，k*-支配查詢中，k對算法效率的影響是最顯著的。對于維度較多的數據集而言，選取一個合適的且較小的k，既可以得到相對有效性更高的小結果集，同時也可以使查詢的時間大大縮短。而且，k*-支配關系不會成環，查詢結果一定不為空集。

(a) 正相關分布

(b) 獨立分布

(c) 反相關分布

圖4 維度d和參數k變化時算法運行時間

5 結 語

在實驗數據檢索中，使用傳統Skyline查詢，由于數據點之間較難產生支配關系，因而返回的數據點較多。在Skyline查詢的基礎上改進形成的k-支配Skyline查詢，有可能會產生循環支配。本文提出了一種新的k*-支配Skyline查詢，在滿足k-支配的條件下還需滿足偏好優先關系，使得數據點之間不存在循環支配。將k*-支配Skyline查詢用于實驗數據的信息檢索，能有效的返回用戶的偏好數據，本文通過實驗證明了算法的可行性。

參考文獻(References)：

[1] Borzsonyi S, Kossmann D, Stocker K. The Skyline operator[C]∥ICDE. Heidelberg:IEEE, 2001:421-430.

[2] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: An online algorithm for Skyline queries[C]∥Proceedings of the 28th International Conference on Very Large Data Bases. Hong Kong:Springer, 2002:275-286.

[3] Tan K L, Eng P K, Ooi B C. Efficient progressive Skyline computation[C]∥Proceedings of the 27th International Conference on Very Large Data Bases. Roma:Springer, 2001:301-310.

[4] Papadias D, Tao Y, Fu G,etal. An optimal and progressive algorithm for Skyline queries[C]∥Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego: ACM Press, 2003: 467-478.

[5] Papadias D, Tao Y, Fu G,etal. Progressive Skyline computation in database systems[J]. ACM Transactions on Database Systems, 2005, 30(1): 41-82.

[6] Lee J, Hwang S. Toward efficient multidimensional subspace Skyline computation[J].The VLDB Journal, 2014, 23(1): 129-145.

[7] Li Y, Li Z, Dong M,etal. Efficient subspace Skyline query based on user preference using map reduce[J]. Ad Hoc Networks, 2015, 35:105-115.

[8] Zhao L, Yang Y, Zhou X. Continuous probabilistic subspace Skyline query processing using grid projections[J]. Journal of Computer Science Technology, 2014, 29(2):332-344.

[9] Lian X, Chen L. Efficient processing of probabilistic group subspace Skyline queries in uncertain databases[J].Information System, 2013,38(3):265-285.

[10] Chen L, Cong G, Jensen C S,etal. Spatial Keyword query processing: An experimental evaluation[J]. PVLDB, 2013, 6(3): 217-228.

[11] Huang Z, Zhang J, Liu Z,etal．Skyline recommendation in distributed networks[J]. The International Arab Journal of Information Technology, 2017,14(3):372-379.

[12] Park Y, Min J, Shim K, Efficient processing of Skyline queries using map reduce[J].IEEE Transactions on Knowledge and Data Engineering, 2017,29(5):1031-1044.

[13] Song B, Liu A, Ding L. Efficient top-k Skyline computation in map reduce[C]∥Proceedings of the12thWeb Information System and Application Conference. Jinan: IEEE,2015:67-70.

[14] Chan C Y, Jagadish H V, Tan K L. Finding k-dominant Skylines in high dimensional space[C]∥Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. Chicago:ACM, 2006:503-514.

[15] 黃榮躍，趙雷．一種使用簡化預排序的k-支配Skyline查詢算法[J]．小型微型計算機系統，2013，34(5):1054-1059．

[16] 印鑒，姚樹宇，薛少鍔,等．一種基于索引的高效k-支配Skyline算法[J]．計算機學報，2010，33(7):1236-1245．