黃金晶， 趙 雷

(1. 蘇州工業(yè)職業(yè)技術(shù)學(xué)院 軟件與服務(wù)外包學(xué)院， 江蘇 蘇州 215104;2. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 江蘇 蘇州 215006)

0 引 言

實(shí)驗(yàn)通常會(huì)產(chǎn)生大量的實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)數(shù)據(jù)中較為“突出”的數(shù)據(jù)往往具有較高的價(jià)值。如何從大量的實(shí)驗(yàn)數(shù)據(jù)中檢索出“突出”的數(shù)據(jù)，是一個(gè)值得研究的問(wèn)題。找到這些較為“突出”的數(shù)據(jù)，常常是實(shí)驗(yàn)結(jié)果處理過(guò)程中需要完成的工作。當(dāng)樣本點(diǎn)數(shù)量巨大且屬性眾多的時(shí)候，這項(xiàng)任務(wù)非常具有挑戰(zhàn)性。

利用多關(guān)鍵字查詢(xún)技術(shù)可以幫助用戶(hù)檢索需要的實(shí)驗(yàn)數(shù)據(jù)。Skyline查詢(xún)是解決多關(guān)鍵字查詢(xún)的有效方法之一。Skyline查詢(xún)是從數(shù)據(jù)集中選出不被支配的全部數(shù)據(jù)點(diǎn)，近年來(lái)在多目標(biāo)決策、用戶(hù)偏好查詢(xún)、可視化等方面應(yīng)用較為廣泛。然而，當(dāng)數(shù)據(jù)量較大時(shí)，Skyline查詢(xún)響應(yīng)的時(shí)間較長(zhǎng)；當(dāng)數(shù)據(jù)維度較高時(shí)，數(shù)據(jù)間較難產(chǎn)生支配關(guān)系，導(dǎo)致Skyline查詢(xún)返回的結(jié)果集較大，不易給出有價(jià)值的查詢(xún)結(jié)果。為解決這一問(wèn)題，Chan等[14]人提出了k-支配Skyline查詢(xún)，只要數(shù)據(jù)點(diǎn)在任意k維度上存在支配關(guān)系即可。但是k-支配Skyline查詢(xún)有可能產(chǎn)生循環(huán)支配的問(wèn)題，導(dǎo)致查詢(xún)沒(méi)有結(jié)果。

Top-k查詢(xún)是應(yīng)對(duì)多關(guān)鍵字查詢(xún)的另一種常用方法。Top-k查詢(xún)僅返回k個(gè)結(jié)果，可以有效解決結(jié)果集太大帶來(lái)的結(jié)果有效性問(wèn)題。但是，大多數(shù)top-k查詢(xún)需要借助評(píng)價(jià)函數(shù)。評(píng)價(jià)函數(shù)雖然可以體現(xiàn)用戶(hù)偏好，但是評(píng)價(jià)函數(shù)的確定具有一定的主觀性，結(jié)果未必是用戶(hù)滿(mǎn)意的。因此，不恰當(dāng)?shù)脑u(píng)價(jià)函數(shù)對(duì)結(jié)果集的有效性同樣可能產(chǎn)生較大的影響。

本文提出一種k*-支配Skyline查詢(xún)，將其運(yùn)用于實(shí)驗(yàn)數(shù)據(jù)檢索中。該查詢(xún)?cè)趥鹘y(tǒng)k-支配Skyline查詢(xún)中引入用戶(hù)偏好的優(yōu)先級(jí)，消除了k-支配存在循環(huán)支配的可能性，既能保證產(chǎn)生結(jié)果又能控制結(jié)果集的大小，同時(shí)查詢(xún)返回的結(jié)果也更加符合用戶(hù)的偏好。將用戶(hù)偏好的優(yōu)先級(jí)引入支配關(guān)系，是同時(shí)解決上述多個(gè)問(wèn)題的關(guān)鍵，也是本文最主要的創(chuàng)新點(diǎn)和貢獻(xiàn)。

1 相關(guān)研究

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

上述研究成果著重解決在大數(shù)據(jù)集或高維度數(shù)據(jù)集上Skyline計(jì)算的效率問(wèn)題，未能有效解決對(duì)于高維數(shù)據(jù)集上結(jié)果集較大、結(jié)果集有效性差的問(wèn)題。同時(shí)，上述研究成果對(duì)用戶(hù)偏好并未給予足夠的關(guān)注?；谏鲜鲈颍疚牡难芯繉⒅貜膬蓚€(gè)方面解決Skyline查詢(xún)結(jié)果集的有效性問(wèn)題，一方面既可保證產(chǎn)生結(jié)果集，又能控制結(jié)果集的大小，另一方面能滿(mǎn)足用戶(hù)偏好。

2 相關(guān)概念描述

本文在k-支配skyline的基礎(chǔ)上，提出了k*-支配skyline算法，下面首先對(duì)k-支配skyline的相關(guān)概念進(jìn)行描述。

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

定義2Skyline數(shù)據(jù)集。對(duì)于數(shù)據(jù)集D中的數(shù)據(jù)點(diǎn)p，若D中不存在能支配p的數(shù)據(jù)點(diǎn)，則p為D中的Skyline點(diǎn)。D中所有的Skyline點(diǎn)的集合就是Skyline數(shù)據(jù)集。

為便于展示，以2維空間舉例說(shuō)明Skyline數(shù)據(jù)集。在圖1中，不失一般性，設(shè)數(shù)值越小越好，則b點(diǎn)顯然支配e點(diǎn)。而a與b之間，盡管橫坐標(biāo)ab，因而它們之間不構(gòu)成支配關(guān)系。圖1中，a、b、c、d4個(gè)點(diǎn)組成了Skyline數(shù)據(jù)集。

圖1 skyline數(shù)據(jù)集舉例

定義3k-支配。對(duì)于d維數(shù)據(jù)集D中的點(diǎn)p和q，若存在k個(gè)維度使得p在這k維上的值都不差于q在這k維度的值，且在這k個(gè)維度上，至少有一個(gè)維度使得p的值優(yōu)于q，稱(chēng)p點(diǎn)k-支配q點(diǎn)[10]。

3 k*-支配Skyline查詢(xún)

3.1 k*-支配Skyline定義

由于k-支配可能存在循環(huán)支配的現(xiàn)象，比如表1所示的數(shù)據(jù)點(diǎn)，假定在每個(gè)維度上，屬性值越大越好。顯然p13-支配p2，p23-支配p3，p33-支配p4，而p4在d3、d4、d5維度上的值大于p1，因而p43-支配p1。

表1 3-支配舉例

為了消除循環(huán)支配，本文提出了一種新的k*-支配Skyline查詢(xún)，考慮用戶(hù)偏好的優(yōu)先級(jí)關(guān)系，使得查詢(xún)結(jié)果更加符合用戶(hù)的實(shí)際需求。對(duì)于每一個(gè)用戶(hù)來(lái)說(shuō)，查詢(xún)關(guān)鍵字的序列不同，偏好的重點(diǎn)不同，因而可以定義一個(gè)偏好優(yōu)先關(guān)系R。

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

為了更好的解釋關(guān)系R，下面以實(shí)例說(shuō)明。設(shè)兩個(gè)不同的用戶(hù)查詢(xún)x和y，在相同維度上的數(shù)值x={2,1,1,1,1}，y={2,1,0,1,1}，當(dāng)i=3時(shí)，x3>y3且x1=y1，x2=y2，則x和y滿(mǎn)足偏好優(yōu)先關(guān)系R，即x優(yōu)于y。

引理1R關(guān)系具有反自反性、反對(duì)稱(chēng)性和傳遞性。

證明

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

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

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

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

證畢。

k*-支配是在k-支配中加入了偏好優(yōu)先關(guān)系R。下面給出k*-支配的定義。

定義5k*-支配。在一個(gè)n維的數(shù)據(jù)集D={D1,D2,…,Dn}上，p1和p2為D上的數(shù)據(jù)點(diǎn)，如果p1k-支配p2且p1和p2之間滿(mǎn)足偏好優(yōu)先關(guān)系R，則稱(chēng)p1k*-支配p2。

定理1k*-支配不存在循環(huán)支配關(guān)系。

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

根據(jù)k*-支配的定義，px,1k*-支配px,2，說(shuō)明px,1k-支配px,2的同時(shí)偏好優(yōu)先級(jí)大于px,2，同理，px,m-1k*-支配px,m，說(shuō)明px,m-1k-支配pm的同時(shí)偏好優(yōu)先級(jí)大于pm，由引理1可知，R關(guān)系具有反對(duì)稱(chēng)性和傳遞性，說(shuō)明不滿(mǎn)足偏好優(yōu)先關(guān)系R，即px,m不能k*-支配px,1。

證畢。

定義6k*-支配Skyline。k*-支配Skyline是不被任何點(diǎn)k*-支配的數(shù)據(jù)點(diǎn)所組成的集合。

計(jì)算k*-支配Skyline是在k-支配Skyline的基礎(chǔ)上，需要引入屬性的優(yōu)先級(jí)關(guān)系。不同的用戶(hù)，可以指定不同的屬性?xún)?yōu)先級(jí)關(guān)系。在相同的數(shù)據(jù)集和相同的k值情況下，不同的屬性?xún)?yōu)先級(jí)情況下會(huì)查詢(xún)得到不同的結(jié)果。

3.2 k*-支配Skyline算法

3.2.1樸素算法(NA)

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

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

由于偏好優(yōu)先關(guān)系具有傳遞性，若在遍歷集合數(shù)據(jù)的過(guò)程中，對(duì)數(shù)據(jù)點(diǎn)按偏好優(yōu)先關(guān)系R進(jìn)行排序，能對(duì)NA算法進(jìn)行剪枝，加快算法的運(yùn)行效率。

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

① 令C=?,L=?。

② 讀取數(shù)據(jù)集合D中的元素p，若D中沒(méi)有元素，則算法結(jié)束。

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

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

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

表2 數(shù)據(jù)集

具體步驟如下：

① 令C=?,L=?。

② 讀取p1，因?yàn)镃和L中沒(méi)有元素，直接將p1加入C集合中。

③ 讀取p2，掃描C中的數(shù)據(jù)點(diǎn)，p2的偏好優(yōu)先級(jí)大于p1，且p2能3-支配p1，因而將p1加入L中，掃描L中的元素，p1為新加入的元素，不重復(fù)比較，直接將p2插入C中。C中的元素為{p2}，L中的元素為{p1}。

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

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

⑥ 讀取p5，掃描C中的數(shù)據(jù)點(diǎn)，p5能3*-支配p3，將p3移出C集合，插入L集合。L中的元素為{p3、p2、p4、p1}。由于C中沒(méi)有元素，繼續(xù)掃描L中的元素，p3為新加入的元素，不重復(fù)計(jì)算，p2的偏好優(yōu)先關(guān)系小于p5，由于L是按照偏好優(yōu)先關(guān)系降序排列，其后的元素不再掃描，直接將p5插入C中。C中的元素為{p5}，L中的元素為{p3、p2、p4、p1}。

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

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

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

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

令為k*-支配skyline的結(jié)果集，PSPA算法的細(xì)節(jié)如下：

1. 令C=?；

2. forD中的每個(gè)元素pdo

3. flag=0；

4. forC中的每個(gè)元素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；

當(dāng)數(shù)據(jù)集中存在兩個(gè)完全相同的數(shù)據(jù)點(diǎn)時(shí)，由于偏好優(yōu)先關(guān)系不具有自反性，因而兩個(gè)相同點(diǎn)之間不存在k*-支配關(guān)系，根據(jù)算法該點(diǎn)不重復(fù)加入結(jié)果集。

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

具體步驟如下：

①C=?；

② 讀p1取，C集合中沒(méi)有元素，直接將p1加入C集合中；

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

表3 預(yù)排序后的數(shù)據(jù)集

{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}；

⑧ 此時(shí)D′中已經(jīng)沒(méi)有數(shù)據(jù)，算法結(jié)束，3*-支配Skyline的結(jié)果為{p5}，與前述算法求得的結(jié)果相同。

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

(a) 正相關(guān)分布

圖2 參數(shù)k變化時(shí)算法運(yùn)行時(shí)間

(a) 正相關(guān)分布

圖3 數(shù)據(jù)集size變化時(shí)算法運(yùn)行時(shí)間

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

(a) 正相關(guān)分布

(b) 獨(dú)立分布

(c) 反相關(guān)分布

圖4 維度d和參數(shù)k變化時(shí)算法運(yùn)行時(shí)間

5 結(jié) 語(yǔ)

在實(shí)驗(yàn)數(shù)據(jù)檢索中，使用傳統(tǒng)Skyline查詢(xún)，由于數(shù)據(jù)點(diǎn)之間較難產(chǎn)生支配關(guān)系，因而返回的數(shù)據(jù)點(diǎn)較多。在Skyline查詢(xún)的基礎(chǔ)上改進(jìn)形成的k-支配Skyline查詢(xún)，有可能會(huì)產(chǎn)生循環(huán)支配。本文提出了一種新的k*-支配Skyline查詢(xún)，在滿(mǎn)足k-支配的條件下還需滿(mǎn)足偏好優(yōu)先關(guān)系，使得數(shù)據(jù)點(diǎn)之間不存在循環(huán)支配。將k*-支配Skyline查詢(xún)用于實(shí)驗(yàn)數(shù)據(jù)的信息檢索，能有效的返回用戶(hù)的偏好數(shù)據(jù)，本文通過(guò)實(shí)驗(yàn)證明了算法的可行性。

參考文獻(xiàn)(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] 黃榮躍，趙雷．一種使用簡(jiǎn)化預(yù)排序的k-支配Skyline查詢(xún)算法[J]．小型微型計(jì)算機(jī)系統(tǒng)，2013，34(5):1054-1059．

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