孫國(guó)璋，黃 山，艾力卡木·再比布拉，徐浩桐，段曉東

(1.大連民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧 大連 116600;2.大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家民委重點(diǎn)實(shí)驗(yàn)室(大連民族大學(xué))，遼寧 大連116600;3.大連市民族文化數(shù)字技術(shù)重點(diǎn)實(shí)驗(yàn)室(大連民族大學(xué))，遼寧 大連116600)

1 引言

Skyline查詢?cè)诙嗄繕?biāo)決策、數(shù)據(jù)可視化等領(lǐng)域有著廣泛的應(yīng)用。自2001年Borzsonyi等人[1]將其引入到數(shù)據(jù)庫(kù)中以來，skyline查詢受到了眾多研究人員的關(guān)注,并取得了一系列研究成果。現(xiàn)有skyline查詢及其變體可以解決大部分實(shí)際問題，并且能夠在大規(guī)模數(shù)據(jù)集中得到有效信息。

Skyline查詢可以篩選掉部分無用數(shù)據(jù)，但是隨著數(shù)據(jù)規(guī)模和維度的增長(zhǎng)，數(shù)據(jù)點(diǎn)之間的支配可能性會(huì)變得非常小，導(dǎo)致結(jié)果集中存在大量的數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)規(guī)模甚至接近于原數(shù)據(jù)集的規(guī)模，這使得用戶無法快速?gòu)慕Y(jié)果集中獲取到有價(jià)值的數(shù)據(jù)。為了解決上述問題，Chan等人[2]提出了k-支配skyline的概念，它將支配的概念放寬到k-支配，以提高數(shù)據(jù)點(diǎn)之間的支配可能性，使得結(jié)果集的規(guī)模變得足夠小，足以讓用戶能從中篩選到有價(jià)值的數(shù)據(jù)。

為了進(jìn)一步提高算法效率，Yuan等人[3]提出了共享策略，以解決每個(gè)skyline查詢獨(dú)立計(jì)算導(dǎo)致的效率低下問題。但是，該策略只適用于傳統(tǒng)skyline查詢算法，不能直接用于k-支配skyline算法。隨著k-支配概念的提出，董雷剛等人[4]便在k-支配skyline查詢中引入共享策略，提出了基于共享策略的k-支配skyline體的算法。該算法通過k-支配skyline體的計(jì)算可以得到任意k值對(duì)應(yīng)的k-支配skyline。但是，該算法需要重復(fù)利用初始數(shù)據(jù)集對(duì)數(shù)據(jù)點(diǎn)進(jìn)行支配性檢查，影響了算法的查詢效率。而現(xiàn)有的k-支配skyline算法主要是面向于單用戶設(shè)計(jì)的，無法有效地解決多用戶查詢問題。

針對(duì)上述問題，本文首先提出了一種面向多用戶的k-支配skyline體求解優(yōu)化算法，然后基于該算法提出了一種運(yùn)行在并行處理框架Apache Flink上的k-支配skyline并行求解算法，有效解決了多用戶查詢問題，實(shí)現(xiàn)了高效、高吞吐量的查詢處理。本文主要工作如下所示：

(1)提出了面向多用戶的k-支配skyline體求解優(yōu)化算法MKSSOA(Multi-user K-dominated Skyline Solving Optimization Algorithm)，利用每名用戶的結(jié)果集和中間集進(jìn)行存儲(chǔ)和共享，在支配檢查過程中，根據(jù)當(dāng)前用戶2個(gè)集合中數(shù)據(jù)點(diǎn)出現(xiàn)的先后次序?qū)蜻x集進(jìn)行二次篩選，以減少數(shù)據(jù)點(diǎn)之間的比較次數(shù)。

(2)在MKSSOA算法的基礎(chǔ)上，提出了面向多用戶的k-支配skyline并行求解算法MKSPSA(Multi-user K-dominated Skyline Parallel Solving Algorithm)，通過利用并行處理框架Apahce Flink的自身優(yōu)勢(shì)和算子特性來調(diào)度不同算子間的數(shù)據(jù)進(jìn)行并行計(jì)算，進(jìn)一步提高了算法執(zhí)行效率。

(3)在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了系統(tǒng)的實(shí)驗(yàn)研究，驗(yàn)證了本文算法的有效性、高效性和可擴(kuò)展性。

本文第1節(jié)介紹了skyline查詢和k-支配skyline查詢的相關(guān)方法和研究現(xiàn)狀；第2節(jié)介紹了本文所需的相關(guān)概念及定理；第3節(jié)介紹了k-支配skyline體并行求解算法；第4節(jié)通過對(duì)比實(shí)驗(yàn)驗(yàn)證了所提算法的有效性；第5節(jié)總結(jié)了本文的工作。

2 相關(guān)工作

自從k-支配概念[2]和相關(guān)查詢算法提出后，國(guó)內(nèi)外研究人員在k-支配skyline查詢問題上取得了一系列研究成果，主要分為如下幾個(gè)方面：

(1)考慮到數(shù)據(jù)排序和索引結(jié)構(gòu)對(duì)查詢效率的影響，Siddique等人[5]提出了一種使用排序過濾方法的k-支配skyline算法;印鑒等人[6]通過為數(shù)據(jù)集建立2個(gè)索引，減少了數(shù)據(jù)點(diǎn)之間的比較次數(shù)，提高了算法執(zhí)行效率。Siddique等人[7]提出了一種根據(jù)數(shù)據(jù)點(diǎn)的支配能力指數(shù)進(jìn)行排序的k-支配skyline算法。黃榮躍等人[8]為了減少預(yù)排序的時(shí)間開銷，提出了一種預(yù)排序k-支配skyline查詢算法。Siddique等人[9]提出了一種統(tǒng)計(jì)數(shù)據(jù)點(diǎn)支配能力的方式處理高維數(shù)據(jù)集的k-支配skyline算法。吳俊杰等人[10]通過skyline層次計(jì)算元組支配能力并提出了k支配能力排序skyline查詢算法。黃金晶等人[11]提出了一種 k*-支配 skyline 算法，在支配關(guān)系中引入用戶偏好的優(yōu)先級(jí)，控制結(jié)果集規(guī)模的同時(shí)又消除了循環(huán)支配的可能。

(2)在分布式環(huán)境下，Tian等人[12]提出了一種基于點(diǎn)的綁定樹PB-Tree(Point-based Bound tree)的k-支配skyline查詢算法，該算法利用PB-Tree分割數(shù)據(jù)空間并在每個(gè)子空間獨(dú)立計(jì)算k-支配 skyline，最后再使用MapReduce進(jìn)行并行計(jì)算。Peng等人[13]提出了一種引入特征位圖來驗(yàn)證支配和k-支配關(guān)系的并行k-支配skyline算法。Siddique等人[14]提出了一種在MapReduce環(huán)境下使用OB-Tree(Object-based Bound Tree)來劃分?jǐn)?shù)據(jù)空間進(jìn)行k-支配skyline的算法。Ding等人[15]提出了一種在MapReduce環(huán)境中基于支配的分層樹的索引結(jié)構(gòu)并實(shí)現(xiàn)了其構(gòu)造算法。Ding等人[16]提出了一種針對(duì)不完整數(shù)據(jù)的支配層次樹的索引結(jié)構(gòu)并結(jié)合MapReduce計(jì)算框架實(shí)現(xiàn)了有效的查詢算法。

(3)針對(duì)特殊數(shù)據(jù)集和不同應(yīng)用環(huán)境，Kontaki等人[17]提出了一種在多維數(shù)據(jù)流上連續(xù)進(jìn)行k-支配skyline算法。Siddique等人[18,19]提出了一種基于分而治之的k-支配skyline算法，以解決數(shù)據(jù)庫(kù)頻繁更新的問題。Dong等人[20]提出了一種解決多個(gè)數(shù)據(jù)集的 k-支配skyline算法。Miao等人[21]提出在不完整數(shù)據(jù)下進(jìn)行k-支配skyline算法并擴(kuò)展了加權(quán)支配skyline查詢和top-k支配查詢算法，以適應(yīng)不完整數(shù)據(jù)。廖再飛等人[22]提出了一種面向不完整數(shù)據(jù)流的k-支配skyline算法。Lai等人[23]提出了一種在不確定數(shù)據(jù)流下通過中間索引提高更新率的k-支配skyline算法。Li等人[24]提出了一種基于支配能力的并行不確定k-支配skyline查詢方法。Awasthi等人[25]提出了一種通過擴(kuò)展k-支配 skyline查詢來處理連接關(guān)系的算法。李松等人[26]提出了一種道路網(wǎng)環(huán)境下的k-支配空間skyline算法。Tripathy等人[27]提出了在動(dòng)態(tài)環(huán)境下計(jì)算k-支配skyline的查詢算法。Zheng等人[28]提出了一種根據(jù)支配能力處理動(dòng)態(tài)數(shù)據(jù)集的k-支配skyline查詢算法，且解決了頻繁更新數(shù)據(jù)庫(kù)的維護(hù)問題。

Dong等人[4]提出了基于共享策略的k-支配skyline算法，該算法通過減少部分冗余操作，節(jié)約檢查支配的時(shí)間，解決了不同k之間結(jié)果的共享問題。但是，該算法每次篩選下一個(gè)k-支配時(shí)都使用原數(shù)據(jù)進(jìn)行比較，增加了時(shí)間消耗。董雷剛等人[29]提出了一種針對(duì)k值動(dòng)態(tài)變化的k-支配skyline算法，該算法以現(xiàn)有查詢結(jié)果為基礎(chǔ)，通過變化的k值重新判斷數(shù)據(jù)點(diǎn)，進(jìn)而得到新的查詢結(jié)果。不過，在數(shù)據(jù)點(diǎn)不能被自身數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)所支配時(shí)，仍需要再次對(duì)非自身數(shù)據(jù)集中剩下的數(shù)據(jù)點(diǎn)進(jìn)行支配檢查，這使得算法的效率較低。

綜上所述，現(xiàn)有的k-支配skyline查詢算法一般都是針對(duì)單用戶查詢，但查詢用戶往往是不唯一的，在出現(xiàn)多名查詢用戶時(shí)，需要重復(fù)運(yùn)行查詢算法，這會(huì)導(dǎo)致算法產(chǎn)生額外開銷。同時(shí)，對(duì)于以往引入共享策略和更新k-支配的相關(guān)研究，也不能很好地處理多用戶查詢問題，同樣也不適用于在并行處理框架上進(jìn)行k-支配skyline查詢，具有一定的局限性。

3 相關(guān)概念及定理

給定一個(gè)d維空間S={s1,s2,s3,…,sd}，如果每一個(gè)點(diǎn)pi∈D是S上的一個(gè)d維數(shù)據(jù)點(diǎn)，則可以稱集合D={p1,p2,p3,…,pn}是S上的數(shù)據(jù)集。此外，用pi.sj表示數(shù)據(jù)點(diǎn)pi第j維的數(shù)值。

定義1(支配(dominate)[1]) 點(diǎn)pi在空間S上支配pj，當(dāng)且僅當(dāng)?sk∈S，pi.sk≥pj.sk且?st∈S，pi.st>pj.st。

定義2(k-支配(k-dominate)[2]) 點(diǎn)pi在空間S上k-支配pj，當(dāng)且僅當(dāng)?S′?S，|S′|=k，?sr∈S′，pi.sr≥pj.sr且?st∈S′，pi.st≥pj.st。

定義3(k-支配skyline(k-dominant skyline)[2]) 點(diǎn)pi是 k-支配 skyline 點(diǎn)，當(dāng)且僅當(dāng)不存在任何一點(diǎn)滿足pj∈D且pj≠pi的條件使得點(diǎn)pjk-支配點(diǎn)pi。

本文用DSP(k,D,S)表示在空間S上數(shù)據(jù)集D的所有k-支配skyline點(diǎn)集。

當(dāng)k=d時(shí)，定義2中所提到的k-支配關(guān)系等同于定義1中的傳統(tǒng)支配關(guān)系。

引理1對(duì)于任意2點(diǎn)pi，pj∈D，如果點(diǎn)pi(k+1)-支配pj，那么pi一定k-支配pj[2]。

推論1|DSP(k,D,S)| ≤ |DSP(k+1,D,S)|[2]。

定理2如果k<(d+2)/2，則任何一對(duì)k-支配skyline點(diǎn)至少在d-2k+2維度上具有相同的數(shù)值[2]。

從推論1中可知，k-支配skyline數(shù)據(jù)點(diǎn)的數(shù)量會(huì)隨著參數(shù)k的變小而單調(diào)遞減。因此，選擇一個(gè)合適的k值可以將k-支配skyline的數(shù)據(jù)點(diǎn)控制在一定范圍內(nèi)，但是參數(shù)k的取值必須考慮實(shí)際意義，不能一味地降低。根據(jù)定理2可知，除非數(shù)據(jù)集中存在大量至少在d-2k+2維度上數(shù)值相同的數(shù)據(jù)點(diǎn)，才有必要將k的取值控制在(d+2)/2之下；否則會(huì)導(dǎo)致結(jié)果集中數(shù)據(jù)點(diǎn)的數(shù)量急劇減少，甚至出現(xiàn)空集的情況，進(jìn)而失去管理和分析的意義。

定義4(k-支配skyline體(k-dominant skyline cube)[4]) 在d維空間中進(jìn)行k-支配skyline查詢，最多有d種不同的k-支配skyline結(jié)果，所有k-支配skyline的集合為k-支配skyline體，記作k-SKYCUB(D,S)。

定義5(多用戶k-支配skyline體(Multi-user k-dominant skyline cube)) 在d維空間中進(jìn)行k-支配skyline查詢，最多有d種不同的k-支配skyline結(jié)果，由于多用戶的不確定性和合理性，參數(shù)k的取值應(yīng)在大于或等于(d+2)/2和小于d的范圍內(nèi)。如果參數(shù)k取到小于(d+2)/2的數(shù)值，至少需要在d-2k+2維度上有相同的數(shù)值，由于這種情況發(fā)生的概率很小，故不做考慮。因此，在k值的取值范圍內(nèi)，最多有(d-2)/2種k-支配skyline結(jié)果，將其稱為多用戶k-支配查詢，記作MKDSC(u,D,S),其中u表示用戶數(shù)量。

下面通過實(shí)例來說明k-支配skyline和多用戶k-支配skyline體。

當(dāng)3名用戶在同一時(shí)間內(nèi)進(jìn)行k-支配skyline查詢時(shí)，這3名用戶會(huì)因?yàn)閰?shù)k的取值分為多種情況，其中最好的情況是每名用戶取相同的k值進(jìn)行查詢，最差的情況則是每名用戶的k值均不相同。

以表1(左)為例，當(dāng)3名用戶全部將k值設(shè)為6時(shí)，只需從表2所示的數(shù)據(jù)集中進(jìn)行一次6-支配skyline查詢即可，從而避免了3名用戶的重復(fù)查詢，最終得到的結(jié)果為{p2,p5}；以表2(右)為例，當(dāng)3名用戶的k值均不相同時(shí)，用戶A在計(jì)算7-支配skyline查詢后得到的結(jié)果集為{p1,p2,p4,p5}，然后用戶B根據(jù)用戶A的結(jié)果集進(jìn)行6-支配skyline查詢，得到的結(jié)果集為{p2,p5}，同樣，用戶C將用戶B的結(jié)果集作為其初始數(shù)據(jù)集進(jìn)行5-支配skyline查詢，得到的結(jié)果集為{p2}。

Table 1 Best case (left) and worst case (right) for the three user queries

4 k-支配skyline體并行求解算法

本節(jié)首先介紹k-支配skyline體求解優(yōu)化算法MKSSOA，隨后在MKSSOA算法的基礎(chǔ)上，提出一種引入并行處理框架Apache Flink的k-支配skyline體并行求解算法MKSPSA，該算法利用Flink并行化和算子特性，進(jìn)一步提高了算法效率。

4.1 k-支配skyline體求解優(yōu)化算法

對(duì)于k-支配skyline算法的查詢思想，有如下2個(gè)性質(zhì)需要用到：

假設(shè)數(shù)據(jù)點(diǎn)p∈D且不是一個(gè)k-支配skyline點(diǎn)，則有以下性質(zhì)[2]：

性質(zhì)1數(shù)據(jù)集D中必定存在一個(gè)傳統(tǒng)skyline k-支配數(shù)據(jù)點(diǎn)p。

性質(zhì)2數(shù)據(jù)點(diǎn)p有可能不被任意k-支配skyline點(diǎn)所k-支配。

定理3對(duì)于數(shù)據(jù)集D和某用戶的結(jié)果集R，若其他用戶的k′小于該用戶的k，則選擇最接近k的k′用戶，利用結(jié)果集R代替數(shù)據(jù)集D進(jìn)行k′-支配skyline查詢，即對(duì)結(jié)果集R中的數(shù)據(jù)點(diǎn)重新進(jìn)行支配比較，從而得出新的結(jié)果R′。

證明根據(jù)定理1和推論1可知，隨著k值減小，結(jié)果集R中數(shù)據(jù)點(diǎn)的數(shù)量也有可能會(huì)變少，因?yàn)榻Y(jié)果集R中的數(shù)據(jù)點(diǎn)可能會(huì)被其他點(diǎn)所支配，因此需要對(duì)結(jié)果集R中的數(shù)據(jù)點(diǎn)重新進(jìn)行支配判斷，根據(jù)性質(zhì)2可知，結(jié)果集R中的數(shù)據(jù)點(diǎn)還需要被中間集T中的數(shù)據(jù)點(diǎn)進(jìn)行支配判斷，進(jìn)而可以保證結(jié)果的準(zhǔn)確性。

定理4通過之前用戶i的中間集Ti分別對(duì)當(dāng)前用戶候選集R進(jìn)行支配檢查時(shí)，需要將從候選集R中移除的數(shù)據(jù)點(diǎn)加入到當(dāng)前用戶自己的中間集T中，進(jìn)而提升算法的查詢效率。

證明用反證法。如果將候選集R中移除的數(shù)據(jù)點(diǎn)加入到其他用戶i的中間集Ti中，在k-支配檢查過程中，其他用戶的中間集Ti會(huì)再次與當(dāng)前用戶的候選集R進(jìn)行比較，這意味著數(shù)據(jù)間的比較次數(shù)將會(huì)增加，進(jìn)而降低查詢效率。

Table 3 Symbols definition in algorithm

根據(jù)上述性質(zhì)和定理，本文將優(yōu)化算法分為3個(gè)主要過程：查詢過程，k-支配檢查過程和數(shù)據(jù)傳遞過程。以表1中的數(shù)據(jù)集D為例，3名用戶以最差情況進(jìn)行k-支配skyline查詢。當(dāng)k=7時(shí)，用戶A的結(jié)果集為{p1,p2,p4,p5}，中間集則為{p3,p6}，接下來用戶B利用用戶A的結(jié)果集進(jìn)行6-支配skyline查詢，得到自己的候選集{p2,p5}和中間集{p4,p1}。而在文獻(xiàn)[4]中，用戶B的結(jié)果集需要對(duì)用戶A的結(jié)果集與數(shù)據(jù)集D中的數(shù)據(jù)點(diǎn)進(jìn)行依次比較才可得到，這樣會(huì)導(dǎo)致數(shù)據(jù)點(diǎn)間重復(fù)計(jì)算。在保證結(jié)果準(zhǔn)確的前提下，本文在k-支配檢查過程中進(jìn)行了優(yōu)化，本文只需要根據(jù)數(shù)據(jù)點(diǎn)的前后次序進(jìn)行比較。以用戶B結(jié)果集中的點(diǎn)P2為例，該點(diǎn)需要與{p3,p6}進(jìn)行比較，因?yàn)樗鼈冎g并沒有進(jìn)行過5-支配計(jì)算。接著再與{p1,p4}中的{p1}進(jìn)行比較，因?yàn)樵诓樵冞^程中，p2和p4已經(jīng)完成了5-支配比較?；诖?，本文算法的比較次數(shù)會(huì)比文獻(xiàn)[4]的少，進(jìn)而算法執(zhí)行效率會(huì)更高。最后，用戶C將用戶B的結(jié)果集作為其初始數(shù)據(jù)集進(jìn)行5-支配skyline查詢，得到候選集{p2}，緊接著進(jìn)行k-支配檢查，得到結(jié)果集{p2}。這樣將上一名用戶的結(jié)果集作為當(dāng)前用戶的數(shù)據(jù)集進(jìn)行k-支配查詢的做法加快了多名用戶整體的查詢時(shí)間。

算法1描述了上述過程的具體細(xì)節(jié)，算法中的符號(hào)定義如表3所示。第①行代碼表示需要從多用戶k-支配查詢集中取出最大k值。第②行代碼用一個(gè)子算法來處理數(shù)據(jù)集D，該過程在算法2中進(jìn)行了詳細(xì)描述。第③行代碼表示在另一個(gè)子算法中，利用多個(gè)中間集T檢查候選集R中非k-支配skyline點(diǎn)，該子算法在算法3中進(jìn)行了詳細(xì)描述。第④行代碼表示將候選集R傳遞給下一位用戶作為其初始數(shù)據(jù)集，便可再次執(zhí)行總流程直到查詢完所有用戶，進(jìn)而得到多個(gè)用戶的k-支配skyline查詢的結(jié)果集。

算法1k-支配skyline體求解優(yōu)化算法(MKSSOA)

輸入：數(shù)據(jù)集D，多用戶k-支配查詢集K。

輸出：Ru,…,R1。

①forevery userk∈Kdo

②Ri,Ti←getKdSetAndNotKdSet(D,Ri,k)；

③Ri←getResult(Ri,Tu,…,Ti)；

④Ri+1=Ri；

⑤endfor

⑥r(nóng)eturnRu,…,R1

算法2為查詢過程，將數(shù)據(jù)集D中的每個(gè)數(shù)據(jù)點(diǎn)與候選集Ri中的數(shù)據(jù)點(diǎn)逐一比較，如果點(diǎn)p被點(diǎn)p′所k-支配，那么數(shù)據(jù)點(diǎn)p將會(huì)加入中間集Ti中，否則加入候選集Ri中；如果點(diǎn)p′被點(diǎn)p所k-支配，那么點(diǎn)p′將會(huì)存到中間集Ti并從Ri中移除。根據(jù)性質(zhì)2，在第1次掃描結(jié)束后，候選集Ri中會(huì)存在非k-支配skyline的數(shù)據(jù)點(diǎn)，因此需要進(jìn)行k-支配檢查，以消除候選集中的非k-支配skyline點(diǎn)。

算法2getKdSetAndNotKdSet(D,Ri,k)

輸入：數(shù)據(jù)集D，候選集Ri，用戶的支配維度k。

輸出：Ri,Ti。

①forevery pointp∈Ddo

②flag=1；

③forevery pointp′∈Rido

④ifp′ k-dominantpthen

⑤flag=0；

⑥endif

⑦ifpk-dominantp′then

⑧ insertp′intoTi;

⑨ removep′fromRi;

⑩endif

算法3為k-支配檢查過程，需要將用戶候選集Ri中的點(diǎn)與之前所有用戶的中間集和自身中間集當(dāng)中的點(diǎn)進(jìn)行比較，如果數(shù)據(jù)點(diǎn)p被數(shù)據(jù)點(diǎn)q所k-支配，那么將點(diǎn)p從Ri中移除并添加到中間集中；但是當(dāng)與自身中間集中的點(diǎn)進(jìn)行比較時(shí)，只需將點(diǎn)p與自身中間集中比點(diǎn)p早出現(xiàn)卻被加入到自身中間集中的數(shù)據(jù)點(diǎn)進(jìn)行比較，因?yàn)楸赛c(diǎn)p晚出現(xiàn)的點(diǎn)都已經(jīng)在查詢過程中完成了比較。因此，該過程減少了不必要的重復(fù)比較且可以得到更加準(zhǔn)確的結(jié)果.

算法3getResultSet(Ri,Tu,…,Ti)

輸入：對(duì)應(yīng)用戶的候選集Ri,中間集Tu,…,Ti。

輸出：Ri。

①forevery pointq∈{Tu,…,Ti}do

②forevery pointp∈Rido

③ifu=ithen

④ifqearlier thanpthen

⑤ifqk-dominatepthen

⑥ insertpintoTi;

⑦ removepfromRi;

⑧endif

⑨endif

⑩else

4.2 k-支配skyline體并行求解算法

Apache Flink 是新一代的分布式并行處理框架，已被廣泛運(yùn)用于大數(shù)據(jù)計(jì)算中，數(shù)據(jù)處理過程見圖1。Apache Flink能在所有常見集群環(huán)境中運(yùn)行，可以對(duì)任意規(guī)模的數(shù)據(jù)進(jìn)行快速計(jì)算，它需要計(jì)算資源來執(zhí)行應(yīng)用程序并且能以內(nèi)存速度和任意規(guī)模進(jìn)行計(jì)算。

Figure 1 Data processing of Flink圖1 Flink的數(shù)據(jù)處理過程

由于目前Apache Flink 的版本默認(rèn)采用Pipelined Region Strategy 調(diào)度策略，Pipelined 就會(huì)在上下游節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換，即上游邊寫，下游邊讀邊消費(fèi)。這樣能夠節(jié)省調(diào)度花費(fèi)的時(shí)間，對(duì)上下游任務(wù)進(jìn)行并行處理，減少了線程之間的緩沖和切換開銷，同時(shí)也避免了不必要的資源浪費(fèi)，提高了整體吞吐量。因此，本文利用該特性對(duì)查詢算法進(jìn)行并行化處理。

圖2展示了多用戶k-支配skyline最終結(jié)果的計(jì)算過程。首先，通過map算子對(duì)數(shù)據(jù)集進(jìn)行處理并將數(shù)據(jù)流發(fā)送給下游的算子節(jié)點(diǎn)；然后，flatmap算子在接收到數(shù)據(jù)后，開始進(jìn)行k-支配skyline查詢。以表1為例，當(dāng)k=7時(shí)數(shù)據(jù)集會(huì)分為2部分：候選集R和中間集T，接著數(shù)據(jù)流傳輸?shù)较乱粋€(gè)flatmap算子當(dāng)中，該算子可以對(duì)每個(gè)k值相同的候選集和中間集分組，同時(shí)包含大于當(dāng)前k值的中間集。此時(shí)，k=7的用戶便可得到正確的結(jié)果集。然后將數(shù)據(jù)流重新發(fā)送到flatmap算子進(jìn)行下一名用戶的k-支配skyline查詢，緊接著進(jìn)行flatmap操作分組，重復(fù)多次上述操作，直到最后一名用戶完成查詢，最后所有用戶的查詢結(jié)果組成多用戶k-支配結(jié)果集。

Figure 2 Calculate processing of final results圖2 最終結(jié)果計(jì)算過程

算法4表示在集群上的運(yùn)行過程。第①行代碼為獲取Flink執(zhí)行環(huán)境。該環(huán)境記錄了用戶作業(yè)和集群配置等信息，默認(rèn)情況下系統(tǒng)會(huì)自動(dòng)檢測(cè)節(jié)點(diǎn)硬件環(huán)境并進(jìn)行配置。由于算子層次的并行度優(yōu)先級(jí)高于系統(tǒng)層次、客戶端層次和執(zhí)行環(huán)境層次，因此該算法在算子層次上設(shè)置并行度。這種設(shè)置不僅方便調(diào)試，還可以為多個(gè)算子設(shè)置不同的并行度。第②～③行代碼表示從文件中讀取數(shù)據(jù)集并在讀取到的數(shù)據(jù)上做map操作，以轉(zhuǎn)換input并存儲(chǔ)數(shù)據(jù)。第④～⑩代碼行是對(duì)多用戶中的每名用戶逐一進(jìn)行flatmap、flatmap操作、設(shè)置并行度和傳遞數(shù)據(jù)集。首先，第1個(gè)flatmap算子調(diào)用算法2和算法3完成查詢過程和k-支配檢查過程，得到用戶的結(jié)果集R和中間集T。接著第2個(gè)flatmap算子對(duì)當(dāng)前用戶的結(jié)果集R和多名用戶的中間集T進(jìn)行分組;然后，為算子設(shè)置相應(yīng)的并行度;最后，將用戶的結(jié)果集傳遞給下一名用戶,并作為其初始數(shù)據(jù)集。第～行代碼表示在輸出所有用戶的k-支配skyline數(shù)據(jù)后，將作業(yè)提交給集群執(zhí)行，直到作業(yè)執(zhí)行完畢，返回作業(yè)執(zhí)行結(jié)果。

算法4k-支配skyline體并行求解算法(MKSPSA)

輸入：數(shù)據(jù)集D，多用戶k-支配查詢集K。

輸出：Ru,…,R1。

①env←getExecutionEnvironment();

②inputs←env.readFile(D);

③Data←input.map(newMapFunction);

④forevery userk∈Kdo

⑤Ri=Data;/*只為第1個(gè)用戶執(zhí)行1次*/

⑥Ri→flatMap()；/*調(diào)用算法2和算法3，得到結(jié)果集R和中間集T*/

⑦ →flatMap()；/*將當(dāng)前用戶的結(jié)果集R和多名用戶中間集T進(jìn)行分組*/

⑧ →setParallelism();/*設(shè)置算子并行度*/

⑨Ri+1=Ri;/*將上一個(gè)用戶的結(jié)果集傳遞給下一名用戶，并作為其初始數(shù)據(jù)集*/

⑩endfor

5 實(shí)驗(yàn)評(píng)估

5.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文的單機(jī)實(shí)驗(yàn)環(huán)境為Intel Core i7-8700 3.2 GHz CPU，32 GB內(nèi)存，CentOS 7操作系統(tǒng)，1.12.4版本的Flink。集群實(shí)驗(yàn)環(huán)境由9臺(tái)高速千兆網(wǎng)絡(luò)連接的PC機(jī)組成，每臺(tái)PC機(jī)的配置為Intel Core i7-8700 3.2 GHz CPU，32 GB內(nèi)存，操作系統(tǒng)為CentOS 7，其中1臺(tái)PC機(jī)為Master節(jié)點(diǎn)，其它PC機(jī)為Slave節(jié)點(diǎn)，Master節(jié)點(diǎn)僅作為JobManager，Slave節(jié)點(diǎn)作為TaskManager獨(dú)享使用，同時(shí)每個(gè)TaskManager設(shè)置6個(gè)Slot，F(xiàn)link版本為1.12.4.

實(shí)驗(yàn)數(shù)據(jù)由合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集2部分組成。真實(shí)數(shù)據(jù)集來自NBA球員從1950賽季到2017賽季所有的表現(xiàn)統(tǒng)計(jì)，不限于得分、籃板、助攻、搶斷等低階數(shù)據(jù)，還包括有效命中率、真實(shí)命中率、籃板率等高階數(shù)據(jù)，共45項(xiàng)技術(shù)統(tǒng)計(jì)，數(shù)據(jù)集共有 24 624條數(shù)據(jù)點(diǎn)。合成數(shù)據(jù)集是采用文獻(xiàn)[1]中的生成工具生成的相同維度不同數(shù)據(jù)量的數(shù)據(jù)集和不同維度相同數(shù)據(jù)量的數(shù)據(jù)集。數(shù)據(jù)量在5萬條～25萬條變化，默認(rèn)維度是50。數(shù)據(jù)集維度的變化區(qū)間在50～100，默認(rèn)數(shù)據(jù)量為5萬條數(shù)據(jù)。一般情況下，測(cè)試k-支配skyline查詢性能需要分別從相關(guān)分布、反相關(guān)分布和獨(dú)立分布的數(shù)據(jù)集進(jìn)行測(cè)試。

相關(guān)分布是指如果數(shù)據(jù)點(diǎn)在某一維度上的值比較好，那么該點(diǎn)在其它維度上的值同樣會(huì)比較好，因此相關(guān)分布的數(shù)據(jù)之間容易產(chǎn)生支配關(guān)系，得到的skyline點(diǎn)集會(huì)很少。

反相關(guān)分布是指如果數(shù)據(jù)點(diǎn)在某一維度上的值比較好，那么該點(diǎn)在其它維度上的值反而比較差，因此，反相關(guān)分布的數(shù)據(jù)之間不容易產(chǎn)生支配關(guān)系，得到的skyline點(diǎn)集會(huì)很多。

獨(dú)立分布是指每個(gè)數(shù)據(jù)點(diǎn)是隨機(jī)生成的，它們各維度上的值都是相互獨(dú)立的且不會(huì)相互影響。

在對(duì)比算法方面，選擇了基于共享策略的k-支配skyline算法TBA(Top-Bottom Algorithm)[4]。該算法通過共享策略可以實(shí)現(xiàn)類似多用戶k-支配skyline查詢的效果；其次選擇了具有更新k-支配輪廓特性的BT[29]算法。該算法中k值動(dòng)態(tài)變化的形式與本文算法相同。TBA[4]和BT[29]算法同本文算法(MKSSOA)在單機(jī)實(shí)驗(yàn)環(huán)境下進(jìn)行測(cè)試對(duì)比，同時(shí)將MKSSOA算法與在集群環(huán)境下提出的MKSPSA算法進(jìn)行對(duì)比實(shí)驗(yàn)。在結(jié)果準(zhǔn)確性一致的前提下，選擇算法執(zhí)行時(shí)間作為評(píng)價(jià)指標(biāo)。

5.2 實(shí)驗(yàn)結(jié)果與分析

圖3測(cè)試的是關(guān)于數(shù)據(jù)量變化對(duì)算法查詢效率的影響。設(shè)數(shù)據(jù)集維度為50，數(shù)據(jù)量在5萬條～25萬條變化，5名用戶在最差情況下測(cè)試了3種查詢算法的查詢性能。

Figure 3 Effect of data volumes on algorithm query performance圖3 數(shù)據(jù)量對(duì)算法查詢性能的影響

從圖3中的實(shí)驗(yàn)結(jié)果可以看出，隨著數(shù)據(jù)量的增加，算法的查詢時(shí)間也隨之增加，這是由于數(shù)據(jù)點(diǎn)之間的比較次數(shù)增加，導(dǎo)致算法執(zhí)行效率降低。由圖3a和圖3b可知，MKSSOA算法與TBA算法和BT算法的執(zhí)行時(shí)間相差不大。因?yàn)樵诜聪嚓P(guān)數(shù)據(jù)集中，數(shù)據(jù)點(diǎn)之間較難產(chǎn)生支配關(guān)系，比較次數(shù)大致相同，所以3種算法的時(shí)間消耗相差不明顯。而在相關(guān)數(shù)據(jù)集中，數(shù)據(jù)點(diǎn)之間容易產(chǎn)生互相支配的關(guān)系，算法執(zhí)行時(shí)間相比反相關(guān)數(shù)據(jù)集會(huì)下降很多，不過3種算法在運(yùn)算過程中數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)的比較次數(shù)相差不大，故三者執(zhí)行時(shí)間呈大致相同的變化趨勢(shì)且區(qū)別不大。從圖3c可以看出，MKSSOA算法在時(shí)間消耗上有較為明顯的下降。這是因?yàn)樵趉-支配檢查過程中，用戶候選集和中間集中存在大量不需要比較的數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)之間的比較次數(shù)減少，進(jìn)而加快了算法查詢速率。

圖4測(cè)試的是數(shù)據(jù)維度變化對(duì)算法查詢效率的影響。設(shè)數(shù)據(jù)量為5萬條，數(shù)據(jù)維度在50～100變化，5名用戶在最差情況下對(duì)3種查詢算法的性能進(jìn)行測(cè)試。

Figure 4 Effect of dataset dimensionality on algorithm query performance圖4 數(shù)據(jù)集維度對(duì)算法查詢性能的影響

從圖4可以看出，隨著數(shù)據(jù)集維度的增大，3種算法的測(cè)試結(jié)果變化曲線相差不大，但是可以明顯看出，MKSSOA算法在獨(dú)立分布上的效率優(yōu)于另外2種算法的。在反相關(guān)分布和相關(guān)分布的數(shù)據(jù)集中，3種算法的執(zhí)行時(shí)間較為相近，而在獨(dú)立分布的數(shù)據(jù)集中，MKSSOA算法對(duì)候選集和中間集分別進(jìn)行了存儲(chǔ)，在k-支配檢查過程中，根據(jù)候選集和中間集中數(shù)據(jù)點(diǎn)出現(xiàn)的先后次序，避免了大量數(shù)據(jù)點(diǎn)之間的重復(fù)計(jì)算。因此，在數(shù)據(jù)集維度增加的情況下，MKSSOA算法優(yōu)于TBA算法和BT算法，具有更好的查詢效率。

為了驗(yàn)證MKSSOA算法是否適用于真實(shí)數(shù)據(jù)集，選取NBA球員在每個(gè)賽季的技術(shù)統(tǒng)計(jì)數(shù)據(jù)集進(jìn)行驗(yàn)證。因?yàn)樵贜BA聯(lián)盟中球隊(duì)經(jīng)理需要權(quán)衡多項(xiàng)技術(shù)統(tǒng)計(jì)來交易或選擇球員，所以選擇NBA球員技術(shù)統(tǒng)計(jì)數(shù)據(jù)集是有意義的。

圖5是測(cè)試不同初始維度對(duì)算法的查詢性能的影響。由于NBA球員數(shù)據(jù)集的維度為45，當(dāng)k值選擇過大或者過小都會(huì)對(duì)結(jié)果產(chǎn)生影響，選擇過大會(huì)產(chǎn)生過多的結(jié)果且不具有查詢意義，選擇過小則失去了篩選的目的，因此模擬5名用戶在最差的情況下分別以初始維度為28，34和40進(jìn)行向下查詢。

Figure 5 Effect of different initial dimensions on algorithm query performance圖5 不同初始維度對(duì)算法查詢性能的影響

從圖5可以看出，MKSSOA算法在執(zhí)行時(shí)間方面優(yōu)于TBA算法和BT算法。這主要是因?yàn)殡S著數(shù)據(jù)集維度的增加，數(shù)據(jù)點(diǎn)之間支配關(guān)系變得復(fù)雜，而MKSSOA算法對(duì)候選集、中間集分別存儲(chǔ)后，可以有效利用中間集中的數(shù)據(jù)點(diǎn)進(jìn)行支配檢查，相較于另外2種算法，減少了數(shù)據(jù)點(diǎn)間因復(fù)雜的支配關(guān)系引發(fā)的重復(fù)計(jì)算問題。由于上述比較算法無法在集群環(huán)境進(jìn)行測(cè)試，因此本文選擇MKSSOA算法與MKSPSA算法以準(zhǔn)確度為評(píng)價(jià)指標(biāo)對(duì)算法執(zhí)行效率進(jìn)行測(cè)試。首先，測(cè)試了MKSPSA算法在不同并行度下的效率；然后，在最佳并行度的基礎(chǔ)上分別對(duì)獨(dú)立分布數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行了測(cè)試。

如圖6所示，實(shí)驗(yàn)測(cè)試了不同并行度對(duì)算法執(zhí)行時(shí)間的影響。獨(dú)立分布數(shù)據(jù)集的數(shù)據(jù)量為5萬條，數(shù)據(jù)維度為50，5名用戶在最差情況下在該數(shù)據(jù)集上進(jìn)行查詢操作。為了排除其它因素的影響，確保實(shí)驗(yàn)的準(zhǔn)確性，本文通過多次測(cè)試取平均值的方法確定最終結(jié)果。從圖6可以看出，隨著并行度的逐漸增加，算法執(zhí)行時(shí)間會(huì)先下降到一定程度，隨后呈現(xiàn)出小幅上升并再次下降的變化趨勢(shì)。這是由Apache Flink內(nèi)部機(jī)制導(dǎo)致的，并行度的提高并不一定能提升處理能力，只有控制好每個(gè)任務(wù)管理器(TaskManager)上子任務(wù) (subtask)的數(shù)量，才能避免多余的subtask成為整個(gè)任務(wù)的瓶頸。為了減少subtask的限制數(shù)量和避免資源浪費(fèi)，本文將subtask設(shè)置成2的整數(shù)次冪。從實(shí)驗(yàn)結(jié)果可以看出，并行度為32的算法執(zhí)行時(shí)間最低，因此在后續(xù)的集群環(huán)境下均將并行度設(shè)置為32進(jìn)行實(shí)驗(yàn)測(cè)試。

Figure 6 Effect of different parallelism degrees on algorithm query performance圖6 不同并行度對(duì)算法查詢性能的影響

圖7給出了不同數(shù)據(jù)量下單機(jī)環(huán)境和集群環(huán)境對(duì)算法性能的影響。數(shù)據(jù)維度為50，5名用戶在最差情況下進(jìn)行查詢。從圖7可以看出，隨著數(shù)據(jù)集規(guī)模的增大，集群環(huán)境下的優(yōu)勢(shì)逐漸顯現(xiàn)出來，集群環(huán)境下的系統(tǒng)并行性和處理能力均得到了增強(qiáng)，進(jìn)而執(zhí)行時(shí)間也越來越短。

Figure 7 Effect of different data volumes on algorithm performance圖7 不同數(shù)據(jù)量對(duì)算法性能的影響

在單機(jī)和集群環(huán)境下，對(duì)相同數(shù)據(jù)量不同數(shù)據(jù)維度的數(shù)據(jù)集進(jìn)行算法性能測(cè)試，結(jié)果如圖8所示。數(shù)據(jù)量為5萬條，5名用戶在最差情況下進(jìn)行查詢。從圖8中的實(shí)驗(yàn)數(shù)據(jù)可以看出，隨著數(shù)據(jù)維度的不斷提高，集群環(huán)境下的算法性能也逐漸與單機(jī)環(huán)境下的算法拉開差距，表明算法有良好的并行性。

Figure 8 Effect of dataset dimensionality on algorithm performance圖8 數(shù)據(jù)集維度對(duì)算法性能的影響

在NBA球員真實(shí)數(shù)據(jù)集上分別進(jìn)行單機(jī)環(huán)境和集群環(huán)境的算法性能測(cè)試的結(jié)果如圖9所示。數(shù)據(jù)量默認(rèn)為24 624條，5名用戶在最差情況下分別以初始維度為28，34和40進(jìn)行向下查詢。

Figure 9 Performance test of the algorithm on NBA player dataset圖9 NBA球員數(shù)據(jù)集上的算法性能測(cè)試

從圖9可以看出，集群環(huán)境下的執(zhí)行時(shí)間相較于單機(jī)環(huán)境均有降低，由于NBA球員數(shù)據(jù)集規(guī)模較小，導(dǎo)致在初始維度28時(shí)與單機(jī)環(huán)境下的差距不夠明顯，隨著初始維度數(shù)量的增加，候選集中數(shù)據(jù)點(diǎn)的數(shù)量也逐漸增多，算法需要花費(fèi)更多的時(shí)間進(jìn)行處理，由于Apache Flink框架特性，MKSPSA算法在整個(gè)處理過程中避免了大量的時(shí)間消耗。因此，在處理大規(guī)模高維度數(shù)據(jù)集時(shí)，MKSPSA算法優(yōu)于MKSSOA算法。

6 結(jié)束語

本文對(duì)多用戶k-支配skyline查詢問題進(jìn)行了深入的研究。首先，提出了面向多用戶的k-支配skyline體求解優(yōu)化算法MKSSOA，該算法對(duì)每名用戶的候選集和中間集分別進(jìn)行存儲(chǔ)，再根據(jù)兩集合中數(shù)據(jù)點(diǎn)出現(xiàn)的先后次序?qū)蜻x集進(jìn)行k-支配檢查，可以減少數(shù)據(jù)點(diǎn)之間的比較次數(shù)，從而更快地得到準(zhǔn)確的結(jié)果集；隨后，在此基礎(chǔ)上提出了面向多用戶的k-支配skyline體并行求解算法MKSPSA，該算法利用Apache Flink的并行性和算子特性，有效減少了數(shù)據(jù)點(diǎn)的比較時(shí)間，提高了算法效率；最后，通過理論研究和對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文所提算法的有效性和高效性。未來的研究重點(diǎn)為針對(duì)k-支配skyline查詢過程進(jìn)行優(yōu)化，以提高算法查詢效率。