基于Flink的k-支配skyline體并行求解算法*

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

(1.大連民族大學計算機科學與工程學院，遼寧 大連 116600;2.大數據應用技術國家民委重點實驗室(大連民族大學)，遼寧 大連116600;3.大連市民族文化數字技術重點實驗室(大連民族大學)，遼寧 大連116600)

1 引言

Skyline查詢在多目標決策、數據可視化等領域有著廣泛的應用。自2001年Borzsonyi等人[1]將其引入到數據庫中以來，skyline查詢受到了眾多研究人員的關注,并取得了一系列研究成果。現有skyline查詢及其變體可以解決大部分實際問題，并且能夠在大規模數據集中得到有效信息。

Skyline查詢可以篩選掉部分無用數據，但是隨著數據規模和維度的增長，數據點之間的支配可能性會變得非常小，導致結果集中存在大量的數據點，數據點規模甚至接近于原數據集的規模，這使得用戶無法快速從結果集中獲取到有價值的數據。為了解決上述問題，Chan等人[2]提出了k-支配skyline的概念，它將支配的概念放寬到k-支配，以提高數據點之間的支配可能性，使得結果集的規模變得足夠小，足以讓用戶能從中篩選到有價值的數據。

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

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

(1)提出了面向多用戶的k-支配skyline體求解優化算法MKSSOA(Multi-user K-dominated Skyline Solving Optimization Algorithm)，利用每名用戶的結果集和中間集進行存儲和共享，在支配檢查過程中，根據當前用戶2個集合中數據點出現的先后次序對候選集進行二次篩選，以減少數據點之間的比較次數。

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

(3)在合成數據集和真實數據集上進行了系統的實驗研究，驗證了本文算法的有效性、高效性和可擴展性。

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

2 相關工作

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

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

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

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

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

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

3 相關概念及定理

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

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

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

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

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

當k=d時，定義2中所提到的k-支配關系等同于定義1中的傳統支配關系。

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

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

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

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

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

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

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

當3名用戶在同一時間內進行k-支配skyline查詢時，這3名用戶會因為參數k的取值分為多種情況，其中最好的情況是每名用戶取相同的k值進行查詢，最差的情況則是每名用戶的k值均不相同。

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

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

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

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

4.1 k-支配skyline體求解優化算法

對于k-支配skyline算法的查詢思想，有如下2個性質需要用到：

假設數據點p∈D且不是一個k-支配skyline點，則有以下性質[2]：

性質1數據集D中必定存在一個傳統skyline k-支配數據點p。

性質2數據點p有可能不被任意k-支配skyline點所k-支配。

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

證明根據定理1和推論1可知，隨著k值減小，結果集R中數據點的數量也有可能會變少，因為結果集R中的數據點可能會被其他點所支配，因此需要對結果集R中的數據點重新進行支配判斷，根據性質2可知，結果集R中的數據點還需要被中間集T中的數據點進行支配判斷，進而可以保證結果的準確性。

定理4通過之前用戶i的中間集Ti分別對當前用戶候選集R進行支配檢查時，需要將從候選集R中移除的數據點加入到當前用戶自己的中間集T中，進而提升算法的查詢效率。

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

Table 3 Symbols definition in algorithm

根據上述性質和定理，本文將優化算法分為3個主要過程：查詢過程，k-支配檢查過程和數據傳遞過程。以表1中的數據集D為例，3名用戶以最差情況進行k-支配skyline查詢。當k=7時，用戶A的結果集為{p1,p2,p4,p5}，中間集則為{p3,p6}，接下來用戶B利用用戶A的結果集進行6-支配skyline查詢，得到自己的候選集{p2,p5}和中間集{p4,p1}。而在文獻[4]中，用戶B的結果集需要對用戶A的結果集與數據集D中的數據點進行依次比較才可得到，這樣會導致數據點間重復計算。在保證結果準確的前提下，本文在k-支配檢查過程中進行了優化，本文只需要根據數據點的前后次序進行比較。以用戶B結果集中的點P2為例，該點需要與{p3,p6}進行比較，因為它們之間并沒有進行過5-支配計算。接著再與{p1,p4}中的{p1}進行比較，因為在查詢過程中，p2和p4已經完成了5-支配比較?；诖?，本文算法的比較次數會比文獻[4]的少，進而算法執行效率會更高。最后，用戶C將用戶B的結果集作為其初始數據集進行5-支配skyline查詢，得到候選集{p2}，緊接著進行k-支配檢查，得到結果集{p2}。這樣將上一名用戶的結果集作為當前用戶的數據集進行k-支配查詢的做法加快了多名用戶整體的查詢時間。

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

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

輸入：數據集D，多用戶k-支配查詢集K。

輸出：Ru,…,R1。

①forevery userk∈Kdo

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

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

④Ri+1=Ri；

⑤endfor

⑥returnRu,…,R1

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

算法2getKdSetAndNotKdSet(D,Ri,k)

輸入：數據集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中的點與之前所有用戶的中間集和自身中間集當中的點進行比較，如果數據點p被數據點q所k-支配，那么將點p從Ri中移除并添加到中間集中；但是當與自身中間集中的點進行比較時，只需將點p與自身中間集中比點p早出現卻被加入到自身中間集中的數據點進行比較，因為比點p晚出現的點都已經在查詢過程中完成了比較。因此，該過程減少了不必要的重復比較且可以得到更加準確的結果.

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

輸入：對應用戶的候選集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 是新一代的分布式并行處理框架，已被廣泛運用于大數據計算中，數據處理過程見圖1。Apache Flink能在所有常見集群環境中運行，可以對任意規模的數據進行快速計算，它需要計算資源來執行應用程序并且能以內存速度和任意規模進行計算。

Figure 1 Data processing of Flink圖1 Flink的數據處理過程

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

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

Figure 2 Calculate processing of final results圖2 最終結果計算過程

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

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

輸入：數據集D，多用戶k-支配查詢集K。

輸出：Ru,…,R1。

①env←getExecutionEnvironment();

②inputs←env.readFile(D);

③Data←input.map(newMapFunction);

④forevery userk∈Kdo

⑤Ri=Data;/*只為第1個用戶執行1次*/

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

⑦ →flatMap()；/*將當前用戶的結果集R和多名用戶中間集T進行分組*/

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

⑨Ri+1=Ri;/*將上一個用戶的結果集傳遞給下一名用戶，并作為其初始數據集*/

⑩endfor

5 實驗評估

5.1 實驗環境與數據集

本文的單機實驗環境為Intel Core i7-8700 3.2 GHz CPU，32 GB內存，CentOS 7操作系統，1.12.4版本的Flink。集群實驗環境由9臺高速千兆網絡連接的PC機組成，每臺PC機的配置為Intel Core i7-8700 3.2 GHz CPU，32 GB內存，操作系統為CentOS 7，其中1臺PC機為Master節點，其它PC機為Slave節點，Master節點僅作為JobManager，Slave節點作為TaskManager獨享使用，同時每個TaskManager設置6個Slot，Flink版本為1.12.4.

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

相關分布是指如果數據點在某一維度上的值比較好，那么該點在其它維度上的值同樣會比較好，因此相關分布的數據之間容易產生支配關系，得到的skyline點集會很少。

反相關分布是指如果數據點在某一維度上的值比較好，那么該點在其它維度上的值反而比較差，因此，反相關分布的數據之間不容易產生支配關系，得到的skyline點集會很多。

獨立分布是指每個數據點是隨機生成的，它們各維度上的值都是相互獨立的且不會相互影響。

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

5.2 實驗結果與分析

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

Figure 3 Effect of data volumes on algorithm query performance圖3 數據量對算法查詢性能的影響

從圖3中的實驗結果可以看出，隨著數據量的增加，算法的查詢時間也隨之增加，這是由于數據點之間的比較次數增加，導致算法執行效率降低。由圖3a和圖3b可知，MKSSOA算法與TBA算法和BT算法的執行時間相差不大。因為在反相關數據集中，數據點之間較難產生支配關系，比較次數大致相同，所以3種算法的時間消耗相差不明顯。而在相關數據集中，數據點之間容易產生互相支配的關系，算法執行時間相比反相關數據集會下降很多，不過3種算法在運算過程中數據集中的數據點的比較次數相差不大，故三者執行時間呈大致相同的變化趨勢且區別不大。從圖3c可以看出，MKSSOA算法在時間消耗上有較為明顯的下降。這是因為在k-支配檢查過程中，用戶候選集和中間集中存在大量不需要比較的數據點，數據點之間的比較次數減少，進而加快了算法查詢速率。

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

Figure 4 Effect of dataset dimensionality on algorithm query performance圖4 數據集維度對算法查詢性能的影響

從圖4可以看出，隨著數據集維度的增大，3種算法的測試結果變化曲線相差不大，但是可以明顯看出，MKSSOA算法在獨立分布上的效率優于另外2種算法的。在反相關分布和相關分布的數據集中，3種算法的執行時間較為相近，而在獨立分布的數據集中，MKSSOA算法對候選集和中間集分別進行了存儲，在k-支配檢查過程中，根據候選集和中間集中數據點出現的先后次序，避免了大量數據點之間的重復計算。因此，在數據集維度增加的情況下，MKSSOA算法優于TBA算法和BT算法，具有更好的查詢效率。

為了驗證MKSSOA算法是否適用于真實數據集，選取NBA球員在每個賽季的技術統計數據集進行驗證。因為在NBA聯盟中球隊經理需要權衡多項技術統計來交易或選擇球員，所以選擇NBA球員技術統計數據集是有意義的。

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

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

從圖5可以看出，MKSSOA算法在執行時間方面優于TBA算法和BT算法。這主要是因為隨著數據集維度的增加，數據點之間支配關系變得復雜，而MKSSOA算法對候選集、中間集分別存儲后，可以有效利用中間集中的數據點進行支配檢查，相較于另外2種算法，減少了數據點間因復雜的支配關系引發的重復計算問題。由于上述比較算法無法在集群環境進行測試，因此本文選擇MKSSOA算法與MKSPSA算法以準確度為評價指標對算法執行效率進行測試。首先，測試了MKSPSA算法在不同并行度下的效率；然后，在最佳并行度的基礎上分別對獨立分布數據集和真實數據集進行了測試。

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

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

圖7給出了不同數據量下單機環境和集群環境對算法性能的影響。數據維度為50，5名用戶在最差情況下進行查詢。從圖7可以看出，隨著數據集規模的增大，集群環境下的優勢逐漸顯現出來，集群環境下的系統并行性和處理能力均得到了增強，進而執行時間也越來越短。

Figure 7 Effect of different data volumes on algorithm performance圖7 不同數據量對算法性能的影響

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

Figure 8 Effect of dataset dimensionality on algorithm performance圖8 數據集維度對算法性能的影響

在NBA球員真實數據集上分別進行單機環境和集群環境的算法性能測試的結果如圖9所示。數據量默認為24 624條，5名用戶在最差情況下分別以初始維度為28，34和40進行向下查詢。

Figure 9 Performance test of the algorithm on NBA player dataset圖9 NBA球員數據集上的算法性能測試

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

6 結束語

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