亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        k*-支配Skyline查詢?cè)趯?shí)驗(yàn)數(shù)據(jù)檢索中的應(yīng)用

        2018-05-21 07:42:09黃金晶
        實(shí)驗(yàn)室研究與探索 2018年4期
        關(guān)鍵詞:支配優(yōu)先排序

        黃金晶, 趙 雷

        (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è)值得研究的問題。找到這些較為“突出”的數(shù)據(jù),常常是實(shí)驗(yàn)結(jié)果處理過程中需要完成的工作。當(dāng)樣本點(diǎn)數(shù)量巨大且屬性眾多的時(shí)候,這項(xiàng)任務(wù)非常具有挑戰(zhàn)性。

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

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

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

        1 相關(guān)研究

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

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

        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好,則稱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維空間舉例說明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,稱p點(diǎn)k-支配q點(diǎn)[10]。

        3 k*-支配Skyline查詢

        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查詢,考慮用戶偏好的優(yōu)先級(jí)關(guān)系,使得查詢結(jié)果更加符合用戶的實(shí)際需求。對(duì)于每一個(gè)用戶來說,查詢關(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},滿足?i(1≤i≤n),有xi>yi,且?j(1≤j

        為了更好的解釋關(guān)系R,下面以實(shí)例說明。設(shè)兩個(gè)不同的用戶查詢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滿足偏好優(yōu)先關(guān)系R,即x優(yōu)于y。

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

        證明

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

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

        (3) 傳遞性。設(shè),都滿足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,即說明x和z之間滿足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之間滿足偏好優(yōu)先關(guān)系R,則稱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,說明px,1k-支配px,2的同時(shí)偏好優(yōu)先級(jí)大于px,2,同理,px,m-1k*-支配px,m,說明px,m-1k-支配pm的同時(shí)偏好優(yōu)先級(jí)大于pm,由引理1可知,R關(guān)系具有反對(duì)稱性和傳遞性,說明不滿足偏好優(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)系。不同的用戶,可以指定不同的屬性優(yōu)先級(jí)關(guān)系。在相同的數(shù)據(jù)集和相同的k值情況下,不同的屬性優(yōu)先級(jí)情況下會(huì)查詢得到不同的結(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ì)算量較大,稱其為樸素算法(Na?ve Algorithm,NA)。

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

        由于偏好優(yōu)先關(guān)系具有傳遞性,若在遍歷集合數(shù)據(jù)的過程中,對(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í)滿足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中沒有元素,則算法結(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中已沒有數(shù)據(jù)點(diǎn),說明C中沒有數(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)入步驟②;若不能,則說明p暫時(shí)不能被k*-支配,將其按升序加入R中,轉(zhuǎn)入步驟②。

        (2) 實(shí)例演示。為了更好的說明上述算法,下面舉例說明如何在表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中沒有元素,直接將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中沒有元素,繼續(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中已沒有元素,算法結(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集合中沒有元素,直接將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)沒有數(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ān)的參數(shù)來進(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可見,當(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可見,當(dāng)d和k確定時(shí),size對(duì)運(yùn)行時(shí)間的影響,在3種不同分布的數(shù)據(jù)集上大時(shí),算法的運(yùn)行效率會(huì)迅速下降。當(dāng)k與d相同時(shí),k*-支配Skyline查詢會(huì)退化成普通的Skyline查詢。綜上可以看出,k*-支配查詢中,k對(duì)算法效率的影響是最顯著的。對(duì)于維度較多的數(shù)據(jù)集而言,選取一個(gè)合適的且較小的k,既可以得到相對(duì)有效性更高的小結(jié)果集,同時(shí)也可以使查詢的時(shí)間大大縮短。而且,k*-支配關(guān)系不會(huì)成環(huán),查詢結(jié)果一定不為空集。

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

        (b) 獨(dú)立分布

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

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

        5 結(jié) 語

        在實(shí)驗(yàn)數(shù)據(jù)檢索中,使用傳統(tǒng)Skyline查詢,由于數(shù)據(jù)點(diǎn)之間較難產(chǎn)生支配關(guān)系,因而返回的數(shù)據(jù)點(diǎn)較多。在Skyline查詢的基礎(chǔ)上改進(jìn)形成的k-支配Skyline查詢,有可能會(huì)產(chǎn)生循環(huán)支配。本文提出了一種新的k*-支配Skyline查詢,在滿足k-支配的條件下還需滿足偏好優(yōu)先關(guān)系,使得數(shù)據(jù)點(diǎn)之間不存在循環(huán)支配。將k*-支配Skyline查詢用于實(shí)驗(yàn)數(shù)據(jù)的信息檢索,能有效的返回用戶的偏好數(shù)據(jù),本文通過實(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查詢算法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(5):1054-1059.

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

        猜你喜歡
        支配優(yōu)先排序
        排序不等式
        被貧窮生活支配的恐懼
        意林(2021年9期)2021-05-28 20:26:14
        恐怖排序
        跟蹤導(dǎo)練(四)4
        節(jié)日排序
        40年,教育優(yōu)先
        商周刊(2018年25期)2019-01-08 03:31:08
        多端傳播,何者優(yōu)先?
        刻舟求劍
        兒童繪本(2018年5期)2018-04-12 16:45:32
        基于決策空間變換最近鄰方法的Pareto支配性預(yù)測(cè)
        站在“健康優(yōu)先”的風(fēng)口上
        日韩精品中文一区二区三区在线| 中文字幕文字幕一区二区 | 在线不卡av天堂| 亚洲素人日韩av中文字幕| 日本av天堂一区二区三区| 少妇愉情理伦片高潮日本| 日日摸夜夜添夜夜添无码免费视频| 国产精品久久久久久久久久影院| 久久国产精品免费专区| 成视频年人黄网站免费视频| 色悠久久久久综合欧美99| 亚洲午夜无码视频在线播放| 快射视频网站在线观看| 在线观看的网站| 香蕉人妻av久久久久天天| 日本岛国大片不卡人妻| 自由成熟女性性毛茸茸应用特色 | 国产成人无精品久久久| 丝袜美腿一区在线观看| 久久精品亚洲精品国产色婷| 亚洲人成人77777网站| 国产在线AⅤ精品性色| 日本不卡一区二区三区在线视频 | 森中文字幕一区二区三区免费| 国产裸体xxxx视频在线播放| 麻豆久久五月国产综合| 日韩精品视频中文字幕播放| 中文亚洲av片不卡在线观看| 日日鲁鲁鲁夜夜爽爽狠狠视频97| 欧洲人体一区二区三区| 日本高清视频在线观看一区二区| 狠狠色综合7777久夜色撩人ⅰ| 日本免费人成视频播放| 午夜一区二区在线视频| 亚洲色偷偷综合亚洲avyp| 欧美亚洲日韩国产人成在线播放| 天堂网av在线| 99精品国产一区二区三区| 欧美天天综合色影久久精品| 无码人妻精品一区二区三区下载| 精品高清一区二区三区人妖|