海量數(shù)據(jù)上有效的top-kSkyline查詢算法*

韓希先，宋 翠，戈韻如，高 宏，李建中

哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001

1 引言

在決策支持等多個(gè)應(yīng)用中，Skyline查詢是一種十分重要的查詢類型，它在潛在的巨大的數(shù)據(jù)空間中返回用戶感興趣的數(shù)據(jù)[1-3]。給定屬性集合作為Skyline準(zhǔn)則，Skyline查詢返回不被其他元組支配的所有元組。確切地說(shuō)，元組t1支配元組t2，如果t1的所有Skyline準(zhǔn)則中的屬性值都不大于t2的對(duì)應(yīng)屬性值，并且在其中至少一個(gè)屬性上，t1在該屬性值小于t2在該屬性值。Skyline查詢的優(yōu)點(diǎn)在于，它不需要特定的評(píng)分函數(shù)，并且不受維度之間不同標(biāo)度的影響。

由于其實(shí)際應(yīng)用的重要性，Skyline查詢已經(jīng)引起了研究人員的廣泛關(guān)注。人們提出了一系列的算法來(lái)處理Skyline查詢[1-8]。不同于top-k等返回固定數(shù)量結(jié)果的查詢，Skyline查詢返回的結(jié)果數(shù)量依賴于元組數(shù)量、Skyline準(zhǔn)則的屬性數(shù)量和數(shù)據(jù)分布[2]。分析發(fā)現(xiàn)Skyline查詢的結(jié)果數(shù)量隨著維度m的增大而指數(shù)級(jí)增長(zhǎng)，尤其在海量數(shù)據(jù)上，即使m的值不是很大，查詢結(jié)果數(shù)量也較多。在返回較多Skyline結(jié)果的情況下，用戶很難在其中找到有用的信息。如何限制Skyline查詢返回的結(jié)果數(shù)量，幫助用戶快速地找到需要的數(shù)據(jù)就變成了一個(gè)很有趣的問(wèn)題。

現(xiàn)有的具有大小限制的Skyline查詢算法可以分為如下幾類：基于點(diǎn)排序方法[9-12]、基于放松支配關(guān)系方法[13-15]和基于k-代表選擇方法[16-20]。其中，基于放松支配關(guān)系方法放松了傳統(tǒng)的支配定義，例如kdominant關(guān)系或ε-支配，從而可以丟棄更多的候選元組，減少了Skyline查詢的結(jié)果數(shù)量。本文考慮的Skyline查詢主要基于傳統(tǒng)的支配定義?；趉-代表選擇方法通過(guò)選擇Skyline查詢結(jié)果的滿足指定原則的k子集，使得選擇的k個(gè)Skyline點(diǎn)的整體度量最大化，例如支配最多的點(diǎn)，或者最大化偏好其中一個(gè)點(diǎn)的概率?；趉-代表選擇問(wèn)題基本都是NP-hard問(wèn)題，只能提供近似的查詢結(jié)果。本文主要考慮準(zhǔn)確算法?；邳c(diǎn)排序方法通過(guò)對(duì)Skyline點(diǎn)指定一個(gè)大小度量，例如Skyline frequency、Skyline點(diǎn)的興趣度或者用戶指定的偏好等，選擇其中的度量值最大的k個(gè)結(jié)果。本文考慮基于點(diǎn)排序方法來(lái)計(jì)算top-kSkyline結(jié)果。

通過(guò)對(duì)現(xiàn)有工作的分析，發(fā)現(xiàn)現(xiàn)有的top-kSkyline算法忽略一個(gè)非常直觀而且有效的基于傳統(tǒng)支配關(guān)系的元組重要性的度量，即支配分?jǐn)?shù)度量[21-23]。給定一個(gè)元組，該元組的支配分?jǐn)?shù)定義為該元組支配的其他元組的數(shù)量。支配分?jǐn)?shù)度量給元組定義了一個(gè)自然的順序。支配分?jǐn)?shù)越高，則表示該元組在數(shù)據(jù)空間中的位置越好，其重要性也越大。自然地，通過(guò)對(duì)Skyline的查詢結(jié)果根據(jù)其支配分?jǐn)?shù)的大小排序，top-kSkyline查詢選擇其中支配分?jǐn)?shù)最大的k個(gè)Skyline元組。

本文考慮海量數(shù)據(jù)top-kSkyline查詢。本文先提出一個(gè)baseline算法來(lái)解決top-kSkyline問(wèn)題，即計(jì)算表T的Skyline結(jié)果，然后再執(zhí)行一輪表掃描來(lái)計(jì)算Skyline元組的支配分?jǐn)?shù)，返回支配分?jǐn)?shù)最大的k個(gè)Skyline元組。在海量數(shù)據(jù)上，baseline算法需要維護(hù)較多的Skyline元組，從而在計(jì)算支配分?jǐn)?shù)時(shí)帶來(lái)較大的計(jì)算費(fèi)用。同時(shí)，利用全表掃描來(lái)計(jì)算查詢結(jié)果也導(dǎo)致較大的I/O費(fèi)用?；谝陨系姆治?，本文提出RSTS（ranked Skyline with table scan）算法來(lái)有效計(jì)算top-kSkyline結(jié)果，該算法不需要為特定的屬性組合構(gòu)建索引結(jié)構(gòu)，只需要利用對(duì)預(yù)排序表的順序掃描來(lái)有效返回查詢結(jié)果。RSTS算法對(duì)數(shù)據(jù)表T執(zhí)行預(yù)排序操作獲得表PT（presorted table），按照對(duì)有序列表執(zhí)行round-robin掃描的順序排列PT的元組。RSTS算法的執(zhí)行可以分為兩個(gè)階段。在階段1，RSTS算法掃描表PT來(lái)獲得查詢結(jié)果的候選元組，當(dāng)然，候選元組肯定是Skyline元組。在階段2，RSTS算法同樣采用對(duì)表PT的順序掃描來(lái)計(jì)算候選元組的支配分?jǐn)?shù)，并利用在掃描過(guò)程得到的信息繼續(xù)剪切候選元組。本文分析證明，RSTS算法具有早結(jié)束特點(diǎn)，即該算法不需要掃描PT的所有元組就可以獲得查詢結(jié)果，還給出RSTS算法在階段1和階段2的掃描深度的理論分析。為減少階段1需要維護(hù)的候選元組數(shù)量，本文提出有效的候選元組剪切規(guī)則，丟棄那些肯定不是查詢結(jié)果的Skyline元組，理論剪切效果證明，剪切規(guī)則可以丟棄絕大多數(shù)候選Skyline元組。本文執(zhí)行較廣泛實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，RSTS算法可以有效計(jì)算top-kSkyline查詢。

本文的主要貢獻(xiàn)如下所示：

（1）提出一個(gè)新的基于表掃描的RSTS算法來(lái)有效處理海量數(shù)據(jù)top-kSkyline查詢；

（2）分析表明，RSTS算法具有早結(jié)束特點(diǎn)，并且提出其掃描深度的分析；

（3）提出剪切算法有效減少候選元組的數(shù)量；

（4）利用較全面實(shí)驗(yàn)評(píng)價(jià)RSTS算法性能。

2 相關(guān)工作

2.1 傳統(tǒng)的Skyline算法

現(xiàn)有的Skyline算法可以分為兩大類：基于索引的方法和一般性方法。基于索引的算法利用索引來(lái)減少需要探索的空間并返回結(jié)果。NN（nearest neighbor search）算法[4]利用預(yù)構(gòu)建的R-樹(shù)來(lái)計(jì)算Skyline結(jié)果。利用基于分支界定策略，BBS（branch and bound Skyline）算法[5]改進(jìn)了NN算法同一節(jié)點(diǎn)的重復(fù)讀取和空間負(fù)載高的問(wèn)題。SUBSKY算法[6]利用一個(gè)特定的距離函數(shù)將多維數(shù)據(jù)轉(zhuǎn)換為一維數(shù)據(jù)，并且以B-樹(shù)索引來(lái)讀取有序元組，可以較快地結(jié)束算法執(zhí)行。

一般性方法不需要額外的數(shù)據(jù)結(jié)構(gòu)，而是直接在數(shù)據(jù)表上執(zhí)行。分治算法[1,7]將數(shù)據(jù)表劃分為多個(gè)數(shù)據(jù)塊，遞歸地計(jì)算每個(gè)塊的部分Skyline結(jié)果，然后通過(guò)合并操作來(lái)獲得數(shù)據(jù)表的Skyline結(jié)果。SFS（sort-filter-Skyline）算法[8]先根據(jù)與Skyline準(zhǔn)則相符的順序?qū)?shù)據(jù)表執(zhí)行排序操作，再掃描排序表的元組維護(hù)候選Skyline結(jié)果，保證插入內(nèi)存緩沖區(qū)的候選結(jié)果肯定是Skyline結(jié)果。LESS（linear elimination sort for Skyline）算法[2]整合排序操作和Skyline計(jì)算，從而減少SFS算法的排序費(fèi)用，改進(jìn)SFS算法的性能。

2.2 結(jié)果數(shù)量限制的Skyline算法

現(xiàn)有的結(jié)果數(shù)量限制的Skyline算法可以分為如下幾類：點(diǎn)排序、放松支配關(guān)系和k-代表選擇。

點(diǎn)排序：Chan等[9]提出一個(gè)新的度量Skyline frequency來(lái)對(duì)不同屬性子集返回的Skyline點(diǎn)進(jìn)行比較和排序，提出有效的近似算法來(lái)計(jì)算Skyline frequency最大的k個(gè)元組。Vlachou等[10]提出基于初始數(shù)據(jù)空間的所有非空子空間中的被支配Skyline點(diǎn)數(shù)量的Skyline點(diǎn)興趣度的概念，Skyline點(diǎn)的所有子空間支配關(guān)系被映射成一個(gè)加權(quán)有向圖Skyline graph，提出SKYRANK框架，基于鏈接的排序技術(shù)來(lái)對(duì)基于加權(quán)有向圖的Skyline點(diǎn)進(jìn)行比較和排序。Lee等[11]引入高維空間中的個(gè)性化top-kSkyline查詢，提出基于用戶指定的定性偏好關(guān)系的telescope算法對(duì)Skyline結(jié)果進(jìn)行排序。Gao等[12]不但提出Skyline對(duì)象的一個(gè)新的排序準(zhǔn)則，通過(guò)考慮一個(gè)Skyline點(diǎn)支配元組數(shù)量以及這些被支配的元組的累計(jì)權(quán)重來(lái)識(shí)別最重要的Skyline對(duì)象。而且提出基于R-tree的RB（reuse based algorithm）算法來(lái)計(jì)算最重要Skyline對(duì)象，首先通過(guò)現(xiàn)有基于R-tree算法來(lái)計(jì)算Skyline對(duì)象，然后通過(guò)在計(jì)算Skyline對(duì)象過(guò)程中緩存的中間結(jié)點(diǎn)和數(shù)據(jù)對(duì)象來(lái)計(jì)算Skyline對(duì)象的分?jǐn)?shù)。

放松支配關(guān)系：Chan等[13]提出一個(gè)新的概念kdominant Skyline，將支配的定義放松到k-支配，給定具有屬性維度M的表，如果存在k個(gè)屬性(k≤M)作為Skyline準(zhǔn)則，使得p支配q，稱元組pk-支配另一個(gè)元組q。k-dominant Skyline查詢返回所有沒(méi)有被k-支配的元組。Koltun等[14]引入近似支配代表的概念來(lái)解決Skyline查詢的較多輸出結(jié)果問(wèn)題。Xia等[15]提出ε-支配關(guān)系，放松傳統(tǒng)的Skyline支配關(guān)系，方便地調(diào)整Skyline查詢結(jié)果的數(shù)量。

k-代表選擇：Lin 等[16]提出 top-krepresentative Skyline查詢，該查詢返回k個(gè)Skyline點(diǎn)，最大化數(shù)據(jù)表中被其中某個(gè)Skyline點(diǎn)支配的元組數(shù)量。Lee等[17]提出一個(gè)新的技術(shù)來(lái)選擇可以最小化基于空間劃分的Skyline計(jì)算中的比較操作數(shù)量的費(fèi)用優(yōu)化的點(diǎn)（pivot point），并提出基于由pivot point構(gòu)建的skytree的貪心算法來(lái)計(jì)算top-krepresentative Skyline查詢。Tao等[18]提出基于距離的representative Skyline查詢，返回可以最好地描述所有Skyline點(diǎn)的可能的折衷的k個(gè)Skyline點(diǎn)，并最小化非代表Skyline點(diǎn)和其最近的代表Skyline點(diǎn)的最大距離。Sarma等[19]提出一個(gè)新的方法來(lái)定義representative Skyline，其目標(biāo)是找到k個(gè)Skyline點(diǎn)，最大化一個(gè)隨機(jī)用戶偏好其中某個(gè)Skyline結(jié)果的概率。Magnani等[20]考慮代表性Skyline查詢問(wèn)題，并引入一個(gè)方法同時(shí)考慮所有元組的重要性及其多樣性。

討論：本文討論基于傳統(tǒng)支配關(guān)系的結(jié)果數(shù)量限制的Skyline算法。放松支配關(guān)系方法放松了傳統(tǒng)的支配關(guān)系，而k-代表選擇方法返回近似結(jié)果，并且k-代表選擇方法返回的查詢結(jié)果彼此之間本質(zhì)上都是平等的，本文希望返回結(jié)果之間存在次序關(guān)系。因此，本文重點(diǎn)集中于點(diǎn)排序算法。本文提出的支配分?jǐn)?shù)度量方法不同于其他點(diǎn)排序方法，大多數(shù)現(xiàn)有方法無(wú)法直接計(jì)算本文提出的問(wèn)題。Gao等[12]提出的方法最接近于本文考慮的問(wèn)題，但是RB算法需要在特定的屬性組合上構(gòu)建R-tree結(jié)構(gòu)，要實(shí)際覆蓋所有的屬性組合就需要構(gòu)建和所有屬性數(shù)量成指數(shù)關(guān)系的R-tree，這是顯然不實(shí)際的，RB算法的實(shí)際應(yīng)用就受到較大限制。此外，該算法主要面向內(nèi)存數(shù)據(jù)集，在處理海量數(shù)據(jù)時(shí)，該算法需要涉及較多的I/O費(fèi)用。

3 預(yù)備知識(shí)

給定具有n個(gè)記錄的表T(A1,A2…,AM),?t∈T，令t.Ai表示元組t的屬性Ai的值。不失一般性，令A(yù)Ssky={A1,A2,…,Am}表示查詢涉及到的Skyline準(zhǔn)則，元組間的支配關(guān)系定義在ASsky。?t1,t2∈T，稱t1支配t2(表示為t1?t2)，如果?i(1≤i≤m),t1.Ai≤t2.Ai，并且?i(1≤i≤m),t1.Ai＜t2.Ai。

?t∈T，t的支配值dom(t)表示為T中被t支配的元組數(shù)量，即dom(t)=|{t'∈T|t?t'}|。

定義1（Top-kSkyline查詢）給定表T以及Skyline準(zhǔn)則ASsky，令SKYT表示表T上的Skyline查詢結(jié)果，top-kSkyline查詢返回SKYT的一個(gè)k-子集R，使得?t1∈R，?t2∈(SKYT-R)，dom(t1)≥dom(t2)。

根據(jù)支配分?jǐn)?shù)定義，如果t1?t2，dom(t1)≥dom(t2)。

定義2（位置索引）給定表T，如果t是T的第ath個(gè)元組，元組t∈T的位置索引是a。

用T(a)表示表T中位置索引為a的元組，用T(a,…,b)表示位置索引大于等于a且小于等于b的元組集合，用T(a,…,b).Ai表示T(a,…,b)中元組的屬性Ai的集合。

4 Baseline算法

給定表T和Skyline準(zhǔn)則ASsky，先提出直觀的BA算法（baseline algorithm）來(lái)計(jì)算top-kSkyline查詢的結(jié)果。BA算法的執(zhí)行過(guò)程可以分為兩步：Skyline計(jì)算和支配分?jǐn)?shù)計(jì)算。其中，Skyline計(jì)算步驟可以采用現(xiàn)有的一般Skyline算法來(lái)計(jì)算表T的Skyline結(jié)果SKYT，由于其較好的實(shí)際性能，本文采用LESS算法來(lái)計(jì)算SKYT。接著，利用對(duì)表T的又一輪掃描操作，計(jì)算SKYT中每個(gè)Skyline元組的支配分?jǐn)?shù)，返回其中支配分?jǐn)?shù)最高的k個(gè)Skyline元組。

BA算法的執(zhí)行比較簡(jiǎn)單。根據(jù)其實(shí)際的執(zhí)行過(guò)程發(fā)現(xiàn)，LESS算法的主要費(fèi)用來(lái)自于對(duì)表T的第一輪掃描，之后的排序操作和Skyline處理過(guò)程涉及到的數(shù)據(jù)量則要少得多?？梢院雎院笳叩牟僮髻M(fèi)用而不影響算法分析的結(jié)果。在支配分?jǐn)?shù)計(jì)算過(guò)程中，BA算法仍然需要對(duì)表T執(zhí)行一輪掃描，計(jì)算SKYT中每個(gè)Skyline元組的支配分?jǐn)?shù)。因此，BA算法需要執(zhí)行對(duì)表T的兩輪掃描來(lái)返回查詢結(jié)果，在海量數(shù)據(jù)上將引起較大的I/O費(fèi)用。

針對(duì)BA算法的性能問(wèn)題，本文提出RSTS算法來(lái)有效計(jì)算top-kSkyline結(jié)果。在候選元組計(jì)算過(guò)程中，通過(guò)對(duì)數(shù)據(jù)表的元組以一定順序排列，RSTS算法可以只讀取排序表的一部分元組就獲得查詢候選元組，并通過(guò)有效的候選元組剪切操作來(lái)減少候選元組的數(shù)量。此外，對(duì)于支配分?jǐn)?shù)計(jì)算過(guò)程，RSTS算法同樣利用排序表的有序性，從而只讀取排序表的一部分元組就可以獲得候選元組的支配分?jǐn)?shù)。

5 預(yù)排序操作

本章介紹如何對(duì)數(shù)據(jù)表T執(zhí)行預(yù)排序操作來(lái)獲得預(yù)排序表PT。自從Fagin等的先驅(qū)性工作[24]，利用有序列表來(lái)處理偏好查詢已經(jīng)成為研究人員自然的選擇。在基于有序列表方法中，表T存儲(chǔ)為有序列表集合LS={SL1,SL2,…,SLM}，每個(gè)有序列表SLi的模式為SLi(PI,Ai)，其中PI表示對(duì)應(yīng)元組在表T的位置索引，Ai表示該元組在對(duì)應(yīng)屬性上的值，SLi根據(jù)Ai的值升序排列。

?t∈T，令PIi(1≤i≤M)表示(t.PI,t.Ai)在有序列表SLi的位置索引，表PT的元組根據(jù)min1≤i≤MPIi的值升序排列，排序操作的實(shí)現(xiàn)方法描述如下。給定有序列表SLi(PI,Ai)(1≤i≤M)，預(yù)排序操作首先對(duì)SLi(PI,Ai)執(zhí)行排序操作，令排序后的有序列表表示為PSLi(PIi,PIT)，這里PIT表示該元組在表T中的位置索引，PSLi(PIi,PIT)的元組根據(jù)PIT的值升序排列。由于本文算法只需要考慮每個(gè)屬性的值的大小關(guān)系，因此PSLi不維護(hù)屬性值A(chǔ)i。很明顯，PSL1,PSL2,…,PSLM中具有相同位置索引的元組對(duì)應(yīng)于數(shù)據(jù)表T的具有相同位置索引的元組，?j(1≤j≤n)，令MPIL(j)表示PSL1,PSL2,…,PSLM的第j個(gè)元組的最小PIi值。接下來(lái)，預(yù)排序操作合并PSL1,PSL2,…,PSLM的元組并執(zhí)行排序操作，使得其中的元組根據(jù)MPIL的值升序排列，排序后的數(shù)據(jù)表表示為PT(MPIL,PIT,PI1,PI2,…,PIM)。令當(dāng)前讀取的元組pt∈PT，文獻(xiàn)[25]證明，當(dāng)前已讀取的PT元組肯定包括SL1(1,2,…,pt.MPIL-1),SL2(1,2,…,pt.MPIL-1),…,SLm(1,2,…,pt.MPIL-1)的所有元組。根據(jù)有序列表的有序性，?pt1,pt2∈PT，如果?1≤i≤m，pt1.PIi＜pt2.PIi,稱pt1?pt2，即T(pt1.PIT)?T(pt2.PIT)。

6 RSTS算法

RSTS算法的基本執(zhí)行過(guò)程包括兩個(gè)階段：在階段1中，算法順序掃描表PT的元組，維護(hù)top-kSkyline查詢的候選元組；在階段2中，算法計(jì)算當(dāng)前的候選元組的支配分?jǐn)?shù)，返回查詢結(jié)果。

6.1 階段1：維護(hù)候選元組

在表掃描過(guò)程中，用STCAD維護(hù)當(dāng)前的候選元組。令當(dāng)前讀取的元組pt=PT(j)。如果?cad∈STCAD，cad?pt，那么pt肯定不是Skyline元組，自然也不是top-kSkyline元組。否則，RSTS算法在STCAD中維護(hù)pt，并且丟棄那些在STCAD中被pt支配的候選元組。令 max1≤i≤mpt.PIi表示pt.PI1,pt.PI2,…,pt.PIm中的最大值，sd1表示已讀取元組的PI1,PI2,…,PIm屬性最大值的當(dāng)前最小值，即。

定理1表明，當(dāng)結(jié)束條件sd1≤pt.MPIL滿足時(shí)，階段1結(jié)束，top-kSkyline查詢結(jié)果包括在STCAD中。

定理1令當(dāng)前讀取的元組pt=PT(j)，當(dāng)sd1≤pt.MPIL時(shí)，階段1結(jié)束并且top-kSkyline查詢結(jié)果包括在STCAD中。

證明?t∈T，PIi(1≤i≤M)表示(t.PI,t.Ai)在有序列表SLi中的位置索引。?j1(1≤j1≤j)，sd1=max1≤i≤mPT(j1).PIi。已知，pt.MPIL表示pt.PI1,pt.PI2,…,pt.PIM的最小值，有序列表SL1,SL2,…,SLm是根據(jù)屬性值A(chǔ)i升序排列，如果sd1≤pt.MPIL，有PT(j1)?pt。再考慮到PT的元組根據(jù)MPIL的值升序排列，那么 ?pt′∈PT(j,…,n)，PT(j1)?pt′，表PT剩余的元組肯定不是Skyline結(jié)果。根據(jù)階段1的執(zhí)行過(guò)程，STCAD維護(hù)的就是Skyline結(jié)果，肯定包括top-kSkyline結(jié)果。 □

雖然可以維護(hù)所有的Skyline元組，但是在海量數(shù)據(jù)上，通常k?|SKYT|，沒(méi)有必要維護(hù)所有的Skyline元組。第一，大多數(shù)的Skyline元組不是top-kSkyline結(jié)果；第二，在計(jì)算候選元組的支配分?jǐn)?shù)時(shí)，較多的候選元組也會(huì)造成較大的計(jì)算費(fèi)用。下面介紹如何減少需要在STCAD維護(hù)的候選元組數(shù)量。

給定Skyline準(zhǔn)則ASSKY，?pt∈PT，該元組的支配分?jǐn)?shù)的下界值LDS和上界值UDS分別計(jì)算如下：

在對(duì)表PT的掃描過(guò)程中，令STSKY?STCAD，并且?pt∈STSKY，pt.MPIL=pt.PIi(?i,1≤i≤m)，定理2證明，STSKY中維護(hù)的元組肯定是Skyline元組。

定理2令STSKY?STCAD，并且滿足?pt∈STSKY，pt.MPIL=pt.PIi(?i,1≤i≤m)，STSKY中維護(hù)的元組肯定是Skyline元組。

證明給定當(dāng)前讀取的元組pt∈PT，并且滿足pt.MPIL=pt.PIi(?i,1≤i≤m)，如果STCAD中不存在支配pt的元組，那么RSTS算法將pt插入到STCAD。?pt1∈PT，如果pt1.PIi＜pt.PIi，那么根據(jù)PT元組的有序性，pt1肯定在pt的前面出現(xiàn)，而已經(jīng)假設(shè)pt沒(méi)有被之前出現(xiàn)的元組支配。對(duì)于在pt之后出現(xiàn)的元組pt2，有pt.PIi＜pt2.PIi，即在pt之后出現(xiàn)的元組不能支配pt。因此，STSKY中維護(hù)的元組肯定是Skyline元組。 □

RSTS算法計(jì)算當(dāng)前STCAD中候選元組的支配分?jǐn)?shù)的上界值和下界值，并利用最小堆MH來(lái)維護(hù)STSKY中支配分?jǐn)?shù)的下界值最大的k個(gè)候選元組，令MH.min表示MH中的最小的支配分?jǐn)?shù)下界值。提出如下剪切規(guī)則減少在STCAD中需要維護(hù)的候選元組數(shù)量。

令pt是當(dāng)前讀取的表PT元組，且pt沒(méi)有被STCAD的候選元組支配，如果UDS(pt.PIT)≤MH.min，那么pt不是候選元組。

根據(jù)剪切規(guī)則，如果pt沒(méi)有被STCAD的候選元組支配，RSTS算法計(jì)算pt的支配分?jǐn)?shù)下界值LDS(pt.PIT)和上界值UDS(pt.PIT)，如果UDS(pt.PIT)≤MH.min，那么pt肯定不是top-kSkyline結(jié)果，從而RSTS算法不需要在STCAD中維護(hù)pt。否則，RSTS算法在STCAD中維護(hù)pt。同時(shí)，如果LDS(pt.PIT)≥MH.min，RSTS算法更新MH，保證其維護(hù)STSKY中支配分?jǐn)?shù)的下界值最大的k個(gè)候選元組。

先分析階段1的掃描深度，給定sd1表示已讀取元組的PI1,PI2,…,PIm屬性最大值的當(dāng)前最小值。已知pt.MPIL表示pt.PI1,pt.PI2,…,pt.PIM的最小值，RSTS算法最多掃描M×sd1個(gè)PT元組就可以使得當(dāng)前元組滿足階段1結(jié)束條件pt.MPIL≥sd1。下面分析sd1的值。由定義可知，?j1(1≤j1≤j)，sd1=max1≤i≤MPT(j1).PIi即PT(j1).PI1≤sd1,PT(j1).PI2≤sd1,…,PT(j1).PIm≤sd1。

假設(shè)1屬性A1,A2,…,AM的值均勻獨(dú)立分布。

下面分析剪切規(guī)則1的剪切效果。

先估計(jì)MH.min的值。如圖1所示，給定Skyline準(zhǔn)則ASsky和1≤sdk≤n，m維空間的坐標(biāo) (sdk,…,sdk)將空間劃分為2m個(gè)子空間SSb1b2...bm，?i(1≤i≤m)，如果SSb1b2...bm[i]=[1,sdk]，bi=0；如果SSb1b2...bm[i]=[sdk,n]，bi=1。其中，SSb1b2...bm[i]表示子空間SSb1b2...bm在第i維上的投影區(qū)間。SKY(SS0…0)肯定是Skyline結(jié)果?；诩僭O(shè)1，子空間SS0…0包括元組數(shù)量n0=n×(sdk/n)m，SKY(SS0…0)的結(jié)果數(shù)量，令。因此，。

Fig.1 Illustration of region partitioning for Skyline computation圖1 區(qū)域劃分Skyline計(jì)算圖示

如果 max1≤i≤mpt.PIi≥m×sdk-m+1，根據(jù)剪切規(guī)則，候選元組pt肯定可以被剪切。下面來(lái)分析剪切規(guī)則的理論剪切效果。如圖2所示，給定m×sdkm+1，可以將空間劃分為2m個(gè)子空間USb1b2...bm，?i(1≤i≤m)，如 果USb1b2...bm[i]=[1,m×sdk-m+1]，bi=0，如 果USb1b2...bm[i]=[m×sdk-m+1,n]，bi=1。根據(jù)剪切規(guī)則，除US0…0外，落入其他子區(qū)間的Skyline結(jié)果可以被剪切。例如，如圖2所示，落入U(xiǎn)S01和US10的Skyline元組可以被剪切規(guī)則剪切?；诩僭O(shè)1，子空間US0…0包括的元組數(shù)量的結(jié)果數(shù)量。給定Skyline結(jié)果數(shù)量，剪切規(guī)則的剪切比例。根據(jù)pp的計(jì)算公式，剪切規(guī)則1將丟棄大多數(shù)的Skyline元組。

Fig.2 Illustration of pruning region of pruning rule圖2 剪切規(guī)則剪切區(qū)域的圖示

6.2 階段2：計(jì)算支配分?jǐn)?shù)

在獲得查詢結(jié)果的候選元組后，RSTS算法在階段2計(jì)算每個(gè)候選元組的支配分?jǐn)?shù)，從而確定支配分?jǐn)?shù)最大的k個(gè)候選元組。

在6.1節(jié)，分析的RSTS算法的階段1的掃描深度的上界是。類似的，根據(jù)6.1節(jié)的分析可以確定，?cad∈STCAD，cad.PIi＜m×sdk-m+1，即cad.PIi的可能最大值是m×sdk-m。那么，在階段2，要計(jì)算cad的支配分?jǐn)?shù)，需要讀取的表PT的掃描深度可能最大值是M×(m×sdk-m)，來(lái)確定不能被cad支配的元組數(shù)量。很明顯。在階段1結(jié)束條件滿足時(shí)，RSTS仍然需要繼續(xù)讀取表PT的元組來(lái)計(jì)算STCAD中的候選元組的支配分?jǐn)?shù)。

對(duì)于階段1讀取的元組，一個(gè)直觀的選擇是維護(hù)這些元組，那么在階段2時(shí)就可以從階段1結(jié)束的位置開(kāi)始繼續(xù)讀取元組，從而減少I/O費(fèi)用。但是在實(shí)際實(shí)現(xiàn)時(shí)，階段1維護(hù)元組所帶來(lái)的更大的內(nèi)存費(fèi)用超過(guò)了內(nèi)存維護(hù)讀取元組而減少的階段2的I/O費(fèi)用，而且在階段1讀取的數(shù)據(jù)有很大部分已經(jīng)在內(nèi)存中緩存，再次讀取這些數(shù)據(jù)的效率會(huì)較高。因此，本文采用的方法是，不維護(hù)階段1讀取的元組，階段2從頭開(kāi)始重新讀取表PT來(lái)計(jì)算候選元組的支配分?jǐn)?shù)。

階段2執(zhí)行前，令STCAD中的所有候選元組的支配分?jǐn)?shù)都是n，即?cad∈STCAD，dom(cad)=n。令pt是階段2中當(dāng)前讀取的PT元組，那么?cad∈STCAD，如果cad不支配pt，dom(cad)的值自減1。很明顯，階段2的實(shí)際掃描深度計(jì)算如下：

如果pt.MPIL＞sd2，?cad∈STCAD，無(wú)法被cad支配的元組都已經(jīng)獲得，因此當(dāng)前的dom(cad)值就是cad的支配分?jǐn)?shù)。階段2結(jié)束，RSTS算法返回STCAD中支配分?jǐn)?shù)最大的k個(gè)候選元組。

7 實(shí)驗(yàn)評(píng)價(jià)

7.1 實(shí)驗(yàn)設(shè)置

本節(jié)評(píng)價(jià)RSTS算法性能。實(shí)驗(yàn)環(huán)境為L(zhǎng)enovo ThinkCentre M8400(Intel?CoreTMi7-3770 CPU@3.40 GHz(8 CPUs)+32 GB內(nèi)存+64位Win 7操作系統(tǒng)+1 TB硬盤)。實(shí)驗(yàn)比較RSTS算法、RB算法和BA算法的性能。

在實(shí)驗(yàn)中，從以下幾方面來(lái)評(píng)價(jià)RSTS算法的性能：元組數(shù)量（n）、結(jié)果數(shù)量（k）、使用屬性數(shù)量（m）、所有屬性數(shù)量（M）。實(shí)驗(yàn)將在合成的數(shù)據(jù)集上執(zhí)行，實(shí)驗(yàn)參數(shù)設(shè)置如表1所示，并在真實(shí)數(shù)據(jù)集HIGGS上執(zhí)行。

Table 1 Table of parameters setting表1 實(shí)驗(yàn)參數(shù)設(shè)置表

7.2 實(shí)驗(yàn)1：元組數(shù)量的效果

給定m=3，M=12，k=10，實(shí)驗(yàn)1評(píng)價(jià)RSTS算法在不同元組數(shù)量的性能。如圖3（a）所示，RSTS算法比BA算法快57.128倍，這可以證明RSTS算法的高效性。這一個(gè)數(shù)量級(jí)的加速比來(lái)自于更小的內(nèi)存計(jì)算費(fèi)用和磁盤讀寫費(fèi)用。RB算法的執(zhí)行效率比RSTS算法差得多，其執(zhí)行時(shí)間甚至超過(guò)BA算法。這是由于在讀取由R-tree索引的海量數(shù)據(jù)時(shí)，每次讀取葉節(jié)點(diǎn)的數(shù)據(jù)都會(huì)引起一次磁盤隨機(jī)尋道操作，從而嚴(yán)重影響算法的執(zhí)行效率。三種算法在其執(zhí)行階段讀取的元組數(shù)量如圖3（b）所示。其中，RSTS算法讀取的元組數(shù)量是階段1和階段2中讀取的元組數(shù)量之和。如圖3（b）所示，RSTS算法讀取的元組數(shù)量是BA算法讀取元組數(shù)量的4.349%，是RB算法讀取元組數(shù)量的10.50%。圖3（c）給出了RSTS算法在階段1和階段2的實(shí)際掃描深度（P1和P2）及其理論掃描深度（P1(T)和P2(T)）。可以看到，階段1和階段2的掃描深度基本符合理論結(jié)果。RSTS算法在階段1中提出的剪切規(guī)則的剪切效果如圖3（d）所示，剪切效果不小于0.924，絕大多數(shù)的Skyline元組都可以被直接丟棄，從而減少了階段2的計(jì)算費(fèi)用。也給出了理論的剪切效果，可以看出，實(shí)際剪切比超過(guò)了理論剪切比，但是其變化趨勢(shì)基本符合理論結(jié)果。

7.3 實(shí)驗(yàn)2：結(jié)果數(shù)量的效果

給定m=3，M=12，n=108，實(shí)驗(yàn)2評(píng)價(jià)RSTS算法在不同結(jié)果數(shù)量的性能。如圖4（a）所示，RSTS算法比BA算法快12.308倍。隨著k值的增長(zhǎng)，RSTS算法的執(zhí)行時(shí)間增長(zhǎng)較快，BA算法的執(zhí)行時(shí)間則基本不變，而RB算法的執(zhí)行時(shí)間仍然比較長(zhǎng)。類似的變化趨勢(shì)也反映在圖4（b）中，但是RSTS算法讀取的元組數(shù)量是BA算法讀取元組數(shù)量的15.43%，是RB算法讀取元組數(shù)量的33.94%。RSTS算法的掃描深度在圖4（c）中給出，可以看到，在階段1，RSTS算法的掃描深度不發(fā)生變化，這是因?yàn)殡A段1其實(shí)就是計(jì)算Skyline結(jié)果的過(guò)程。但是，更大的k值使得RSTS算法在階段1結(jié)束時(shí)需要維護(hù)更多的候選元組，這也增加了階段2的掃描深度。如圖4（d）所示，隨著k值的增大，RSTS算法剪切操作性能也逐漸下降，這也符合理論分析的結(jié)果。

7.4 實(shí)驗(yàn)3：使用屬性數(shù)量的效果

給定k=10，M=12，n=108，實(shí)驗(yàn)3評(píng)價(jià)RSTS算法在不同使用屬性數(shù)量的性能。如圖5（a）所示，RSTS算法比BA算法快90.661倍。隨著m值的增大，Skyline結(jié)果數(shù)量也呈指數(shù)級(jí)增加，這使得三種算法的執(zhí)行時(shí)間都快速增長(zhǎng)。實(shí)驗(yàn)3并沒(méi)有報(bào)告RB在m=6時(shí)的執(zhí)行時(shí)間，因?yàn)樵趍=5時(shí)RB的執(zhí)行時(shí)間已經(jīng)超過(guò)257 500 s，根據(jù)其變化趨勢(shì)，在m=6時(shí)執(zhí)行時(shí)間會(huì)非常長(zhǎng)。如圖5（b）所示，RSTS算法讀取的元組數(shù)量是BA算法讀取元組數(shù)量的10.11%，是RB算法讀取元組數(shù)量的45.27%。圖5（c）給出了RSTS算法的掃描深度，可以看到，階段1和階段2的掃描深度都隨著m值的增大而快速增長(zhǎng)，基本都符合理論分析的結(jié)果。RSTS算法在階段1的剪切效果如圖5（d）所示，大多數(shù)的Skyline結(jié)果元組都可以被剪切，減少了RSTS算法需要維護(hù)的候選元組數(shù)量。

7.5 實(shí)驗(yàn)4：所有屬性數(shù)量的效果

Fig.3 Effect of tuple number圖3 元組數(shù)量的效果

Fig.4 Effect of result size圖4 結(jié)果數(shù)量的效果

Fig.5 Effect of used attribute number圖5 使用屬性數(shù)量的效果

給定k=10，m=3，n=108，實(shí)驗(yàn)4評(píng)價(jià)RSTS算法在不同所有屬性數(shù)量的性能。如圖6（a）所示，RSTS算法比BA算法快120.186倍，而RB算法的執(zhí)行時(shí)間比BA算法的還長(zhǎng)。隨著M值的增加，BA算法的執(zhí)行時(shí)間增長(zhǎng)幅度并不大，而RSTS算法的執(zhí)行時(shí)間則快速增長(zhǎng)。M值的變化使得每個(gè)元組的長(zhǎng)度發(fā)生變化，但是這并不影響B(tài)A算法在計(jì)算top-kSkyline結(jié)果時(shí)讀取的元組數(shù)量，由于預(yù)排序表的構(gòu)建方法，較大的M值影響了RSTS算法需要讀取的元組數(shù)量。讀取的元組數(shù)量的結(jié)果如圖6（b）所示，RSTS算法讀取的元組數(shù)量是BA算法讀取元組數(shù)量的2.978%，是RB算法讀取元組數(shù)量的6.638%。RSTS算法的掃描深度如圖6（c）所示，可以看到，隨著M值的增加，RSTS算法在階段1和階段2的掃描深度都增加。RSTS算法的剪切比例如圖6（d）所示，絕大多數(shù)的Skyline元組都可以被剪切。

7.6 實(shí)驗(yàn)5：真實(shí)數(shù)據(jù)集的效果

真實(shí)數(shù)據(jù)集HIGGS來(lái)自于UCI Machine Learning Repository。該數(shù)據(jù)集包含11 000 000個(gè)元組以及28個(gè)屬性。選擇前3個(gè)屬性來(lái)計(jì)算top-kSkyline結(jié)果。在實(shí)驗(yàn)5中，通過(guò)不同的結(jié)果大小來(lái)評(píng)估RSTS的性能。如圖7（a）所示，RSTS比BA快7.08倍，比RB快77.78倍。隨著k值的增加，RSTS的執(zhí)行時(shí)間顯著增加，而B(niǎo)A和RB的執(zhí)行時(shí)間基本保持不變。在實(shí)驗(yàn)5中，無(wú)論k取何值，BA和RB算法中仍然需要先計(jì)算出Skyline結(jié)果，然后計(jì)算其支配分?jǐn)?shù)。如圖7（b）所示，RSTS讀取的元組數(shù)量是BA算法讀取元組數(shù)量的23.53%，是RB算法讀取元組數(shù)量的46.95%。RSTS檢索到的元組數(shù)量隨著k值的增大而增加，因?yàn)镽STS需要檢索更多的元組來(lái)確定top-kSkyline結(jié)果，圖7（c）也說(shuō)明了這一點(diǎn)。如圖7（d）所示，隨著k值增加，剪枝規(guī)則的剪枝效果變差，從0.872減少到0.674，這與理論結(jié)果相符。

8 結(jié)論

Fig.6 Effect of total attribute number圖6 所有屬性數(shù)量的效果

Fig.7 Effect of real data set圖7 真實(shí)數(shù)據(jù)集的效果

本文考慮海量數(shù)據(jù)的top-kSkyline查詢問(wèn)題，提出一個(gè)新的基于表掃描的RSTS算法，該算法利用對(duì)預(yù)排序表的順序掃描來(lái)計(jì)算top-kSkyline結(jié)果。RSTS算法的執(zhí)行包括兩個(gè)階段，階段1掃描預(yù)排序表并維護(hù)候選元組，階段2計(jì)算候選元組的支配分?jǐn)?shù)并返回查詢結(jié)果。本文的分析發(fā)現(xiàn)，RSTS算法具有早結(jié)束特點(diǎn)，并給出早結(jié)束操作的掃描深度的理論分析。RSTS算法在階段1利用有效的剪切操作來(lái)減少需要維護(hù)的候選元組，本文給出的理論剪切分析表明，絕大多數(shù)的Skyline元組都可以被丟棄。實(shí)驗(yàn)結(jié)果表明，RSTS算法可以有效計(jì)算海量數(shù)據(jù)top-kSkyline結(jié)果。