高效多子空間Skyline查詢處理算法*

王瀟逸，秦小麟，王　寧，史文浩

?

高效多子空間Skyline查詢處理算法*

王瀟逸+，秦小麟，王寧，史文浩

南京航空航天大學計算機科學與技術學院，南京210016

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(05)-0646-11

E-mail: fcst@vip.163.com http:

//www.ceaj.org Tel:

+86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61373015, 61300052, 41301047 (國家自然科學基金); the Priority Academic Development Program of Jiangsu Higher Education Institutions (江蘇高校優勢學科建設工程資助項目); the Foundation of Graduate Innovation Center in Nanjing University of Aeronautics and Astronautics under Grant No. kfjj20151607 (南京航空航天大學研究生創新實驗室開放基金).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版: 2015-09-16, http://www.cnki.net/kcms/detail/11.5602.TP.20150916.0958.002.htm l

摘要：隨著Skyline查詢應用的增多，子空間Skyline查詢成為熱點。針對實際應用中用戶從多角度審視某一數據集的需求，充分研究了多子空間Skyline查詢問題。在分析現有子空間Skyline查詢算法解決該問題不足的基礎上，提出了子空間立方體群（subspace skycube group，SSG）結構，并給出了基于該結構的同時計算任意多個子空間Skyline查詢的MSSC（multiple subspace skycube）算法。該算法采用子空間候選集（subspace candidate sets，SCS），并充分利用了子空間立方體群結構中各子空間Skyline結果間的共享關系；在此基礎上，算法采用求和過濾以及最大值過濾等方法，對數據集進行剪枝和過濾，從而進一步提高算法效率。最后，分別用人造數據和真實數據對算法進行實驗，并與現有算法進行比較，結果表明MSSC算法可以高效地解決多子空間Skyline查詢問題。

關鍵詞：多子空間Skyline查詢；子空間序列；子空間立方體群；子空間候選集

1 引言

近年來，Skyline計算[1]及其計算方法得到眾多研究者的關注，這主要因為Skyline查詢結果在很多應用中都有非常重要的作用，例如多目標決策[2]、數據挖掘及可視化以及用戶偏好查詢等。數據庫領域最初的Skyline查詢研究主要集中在全空間Skyline查詢，隨著數據庫中數據呈高維海量的趨勢發展，全空間上得到的極大Skyline結果集失去意義。在許多場景中，用戶很可能只對數據集的某幾個維度感興趣，而非全部維度。為此，研究者們提出子空間Skyline[3]查詢概念。例如，某航班信息數據包含價格、起飛時間、歷時、經停站等屬性，用戶發出一個查詢“查找一個從北京到南京的價格便宜且歷時短的航班”，該查詢就是子空間（價格和歷時）Skyline查詢。值得注意的是，全空間上的Skyline結果對象未必是子空間Skyline的查詢結果。

傳統子空間Skyline查詢算法主要集中于對某一特定子空間的查詢[3]和對全部子空間[4-5]的查詢。而實際應用中，用戶往往有從多角度審視數據集的需求。因此多數情況下用戶并非關注某一特定子空間，同時全部子空間上的Skyline結果對大多用戶意義不大。用戶通常根據自身的興趣點關注不同子空間的組合，主要可以概括為以下兩種情況：

（1）某用戶同時關注一個數據集的多個不同維度組合。例如，足球隊員數據集包括速度、體能、射門精度、搶斷、力量5個維度。教練為掌握球員的狀況，對于前鋒和后衛，同時發出兩條查詢：

查詢1查詢速度快并且射門精度高的球員。

查詢2查詢搶斷次數多并且力量大的球員。

（2）多個用戶分別關心一個數據集的不同組合。例如，飯店數據集包括距離、價位、服務態度、餐廳環境、菜量、口味6個維度。甲乙丙3人相約聚餐，分別根據自己不同的喜好發出3條查詢：

查詢3查詢位置近并且價格便宜的餐廳。

查詢4查詢口味好并且菜量大的餐廳。

查詢5查詢服務態度好并且環境好的餐廳。

上述問題概括為：對于某數據集，系統中同時存在多個不同維度組合上的子空間Skyline查詢，稱為多子空間Skyline查詢問題。目前有關子空間Skyline查詢的算法大多集中在某一特定子空間以及全部子空間，在解決任意數量的子空間Skyline查詢時效率低下。對此，本文提出一種可以高效處理多個子空間Skyline查詢的算法，主要貢獻如下：

（1）深入研究多子空間Skyline查詢問題，分析現有算法無法適用于該問題的原因。

（2）基于Skycube的定義[4]，提出子空間立方體群（subspace skycube group，SSG），給出生成該群結構的方法，并利用結構中各子空間Skyline結果的共享關系提高查詢效率。

（3）基于子空間立方體群結構，提出一種求解多子空間Skyline查詢的MSSC（multiple subspace skycube）算法。算法采用子空間候選集、求和過濾及最大值過濾3種優化方法，有效降低支配關系判定次數，提高了效率。

（4）同時采用人造數據和真實數據對算法性能進行評估，實驗結果證明，MSSC算法能高效解決多子空間Skyline查詢問題。

本文結構如下：第2章介紹Skyline查詢的基礎知識及相關工作，并分析現有方法在解決多子空間Skyline查詢時的不足；第3章提出MSSC算法，并對算法進行詳盡的解析；第4章對MSSC算法進行實驗評估，并與現有算法進行性能對比；最后對本文工作進行總結。

2 背景知識

2.1 Skyline查詢概述

首先介紹支配的概念，為便于描述，假定數據集在每個維度上均越小越優。

定義1（支配[1]）給定一個d維數據集S，ai(1≤i≤d)表示每個維度，D為d個維度的集合，D= {a1,a2,…,ad}。p、q分別為S中的兩個數據點，其在維度ai上的值分別用p(ai)和q(ai)表示。對于任意維度組合U?D,如果?ai∈U, p(ai)≤q(ai),并且?aj∈U, p(aj)

在Skyline查詢中，把數據集所有維度組成的集合稱為全空間，在全空間上的Skyline查詢稱為全空間Skyline查詢，即用戶關心數據的所有屬性。

定義2（全空間Skyline查詢）給定一個d維數據集S，以及維度組合U，如果U=D，則稱查詢U上所有不被任何其他點支配的數據點的集合，為全空間Skyline查詢。

子空間Skyline查詢，即用戶關心查詢對象的部分屬性。

定義3（子空間Skyline查詢）給定一個d維數據集S，以及維度組合U，如果U?D，則稱查詢U上所有不被任何其他點支配的數據點的集合，為子空間Skyline查詢。

表1為簡化的旅館信息數據集，該數據集有4個維度，10個數據點。根據上述定義，若用戶甲發出查詢“查找價格低、等級高、房間大并且距離小的賓館”，則為全空間Skyline查詢，其查詢結果為{P1,P2, P3,P4,P5,P6,P7}。可見全空間Skyline結果集包含的數據點數過多（占總數的70%），并沒有為用戶帶來較高的參考價值。因此，更多的用戶可能只關注少數幾個維度的組合，比如用戶乙發出查詢“查找價格低并且距離小的賓館”，該查詢為子空間Skyline查詢，其結果為{P3,P4}。表2為該數據集上所有子空間的Skyline結果集。

Table 1 Simplified hotel information data set表1 簡化的旅館信息數據集

Table 2 A ll subspace Skyline queries results表2 所有子空間Skyline查詢結果

2.2相關工作

數據庫領域對Skyline查詢的研究主要分為全空間Skyline查詢[1,6]和子空間Skyline查詢[3-5,7]。全空間Skyline查詢算法主要包括BNL（block-nested-loops）算法[1]、DC（divide and conquer）算法[1]和SFS（sort first Skyline）算法[6]。此外，Tan等人提出bitmap和index兩種算法[8]，避免了遍歷整個數據集；Kossmann等人[9]在R樹索引基礎上提出最近鄰（nearest neighbor，NN）算法，該算法遞歸搜索區域的最近鄰點，并通過區域剪枝技術刪除被最近鄰點支配的所有對象。

隨數據庫中數據維數的增大以及數據量的擴增，全空間Skyline查詢結果包含極多的數據點，意義不大，用戶更多關注子空間上的Skyline查詢。關于子空間Skyline查詢的研究主要包括以下工作：

首先，BNL和SFS算法沒有創建任何附加索引，因此也可以解決子空間Skyline查詢問題；Tao等人[3,10]研究了任意單個子空間上的Skyline查詢，并給出Subsky算法；Dellis等人[11]研究了約束子空間的Skyline查詢，并提出了一種利用多索引求解的STA（thresholdbased Skyline algorithm）算法；文獻[12]研究了如何在高維數據集上求解某一子空間的Skyline結果。這些算法雖然在處理某一特定子空間Skyline查詢時性能優于MSSC算法，但處理多子空間Skyline查詢問題時性能低下。

此外，研究者還圍繞全部子空間的Skyline查詢進行研究。Yuan等人[4]研究了如何高效計算某一數據集所有子空間Skyline查詢的結果，并提出Skycube概念，給出計算Skycube的算法；Pei等人[5]在Skycube的基礎上，提出Skyline分組概念，并對其在語義層面進行解釋，之后又在文獻[13]中提出一種Stellar算法來計算壓縮的Skycube，這種方法避免了枚舉所有子空間；與之相似，Xia等人[14]提出一種壓縮Skycube層次數據結構（compressed skycube，CSC），并在此基礎上給出一個有效處理Skyline查詢的方法QueryCSC。上述方法均是一次性求解所有子空間的Skyline結果。

除上述外，研究者們在Skyline查詢的其他方向也取得諸多成果。Kailasam等人[15]利用位圖結構計算Skycube中所有子空間結果；文獻[16]研究了對等網絡中的子空間Skyline查詢；文獻[17]研究了Skyline分組問題，并給出QSkycube算法；此外，在分布式環境中，文獻[7]提出了分布式不確定數據上概率Skyline查詢的低通信開銷算法，文獻[18]研究了分布式環境中特定子空間Skyline求解方法。

經調研，現有算法沒有針對求解任意多個子空間Skyline查詢的研究。雖然少數已有算法可以用來解決多子空間Skyline查詢問題，卻有以下不足：

（1）一些算法[1,6]求解每個子空間Skyline結果時均需要遍歷整個數據集至少一遍，效率較低。

（2）無需遍歷整個數據集的算法[8,11]需要建立索引結構，而在解決多子空間Skyline查詢時，則需要建立多個索引（最多建立2n-1個索引）。而建立索引的開銷非常大，因此類方法對于解決多子空間Skyline查詢問題顯然效率低下。

（3）現有算法用來解決該問題時，一類是要運行多次逐個求解每個子空間Skyline結果[3,5]，效率很低；另一類是一次性計算出所有2n-1個子空間Skyline結果[4-5,13]，計算結果冗余，耗時高。

綜上，多子空間Skyline查詢問題是一個具有挑戰性的問題，提出的MSSC算法可以高效地同時求解任意多個子空間Skyline查詢。

3 多子空間Skyline查詢算法

此部分將給出求解多子空間Skyline查詢問題的MSSC算法。首先基于Skycube概念提出子空間立方體群結構，基于此，有效實施了MSSC算法。算法執行過程中，采用多種剪枝方式進行優化，最終，算法有效返回系統中所有的子空間Skyline查詢結果。后文中，用skyV表示子空間V上的Skyline結果集，并假設數據集所有維度上的值越小越好。

3.1子空間立方體群

為充分利用子空間結果集之間的共享關系，減少算法的時間開銷，在Skycube結構基礎上，提出子空間立方體群概念。

文獻[4]第一次提出Skycube概念。對于一個d維的數據集S，一共有2d-1個不同的維度組合，Skycube結構是由這2d-1個維度組合組成的分層結構。圖1所示為旅館信息數據集的Skycube結構。從底向上，Skycube被分為4層，對于Skycube中的兩個子空間U和V，共存在3種關系：（1）如果U?V，且二者相差大于一層，則稱V是U的祖先，例如子空間abc與b；（2）如果U?V，且二者只相差一層，則稱V 是U的父親，例如子空間abc與ab；（3）如果U與V在同一層，則稱U與V是兄弟，例如子空間ab與bc。

Fig.1 Skycube of hotel information data set圖1 旅館數據集的Skycube結構

基于Skycube結構，定義4給出子空間立方體概念。

定義4（子空間立方體）對于子空間序列中的任意一個子空間Vi，將其構造成滿足如下性質的結構，稱之為子空間立方體(SSC)：（1）該結構為分層結構，層數為Vi的維數|Vi|，所有節點均為一個子空間；（2）最頂層為當前子空間Vi；（3）第j層為從Vi包含的維度中取出j個維度的所有組合，共有個子空間；（4）有向邊集{}連接相鄰兩層的各節點，由上層節點指向下層節點，其中|Ut|=|Uk|-1，且Ut?Uk。

定義5（子空間立方體群）由n(n≥1)個子空間立方體構成的群結構。

系統中同時存在多個不同子空間Skyline查詢時，不妨假設共有v個子空間Skyline查詢，形成一個子空間序列SKS={V1,V2,…,Vv}，下面給出子空間有序列的定義。

定義6（子空間有序列）對于子空間序列SKS={V1, V2,…,Vv}，如果滿足如下條件，則稱該序列為子空間有序列：?Vi,Vj∈SKS，如果locate(Vi)< locate(Vj)，則必有|Vi|≥|Vj|。其中，locate(Vi)為Vi在序列SKS中的位置，|Vi|為子空間Vi的維數。

算法1子空間立方體群生成算法createSSG(O)

輸入：子空間集合O={V1,V2,…,Vv}

輸出：子空間立方體群SSG

1. SSG←?//將SSG集合初始化為空

2.SKS←createlist (V1,V2,…,Vv）

3.for i←0 to v do

4.if ! contain(SSG,Vi) then //如果子空間Vi不

在SSG中

5.SSC←createSSC(Vi) //Vi生成一個子

空間立方體

6.add SSC to SSG //將該SSC放入SSG中

7.end if

8.end for

9.return SSG //將子空間立方體群結構返回

算法1有效地將系統中多個子空間轉化成子空間立方體群結構。首先將子空間集合O轉化為子空間有序列，該過程的時間復雜度為O(v lb v)；之后按子空間有序列中的順序依次將每個子空間構造成子空間立方體，并放入SSG中。其中，判斷Vi是否在SSG中的時間復雜度為O(v lb v)，將Vi生成子空間立方體的時間復雜度為O(2|Vi |)。綜上，算法1的時間復雜度為O(v lb v+2max(|Vi |))。其中，v為子空間個數，max(|Vi|)為待求子空間的最大維數。例如，表1旅館信息數據集中，4個維度分別為a、b、c、d。假定系統中存在待求子空間集合為O={ab, abc, acd, a}，則通過算法1可以生成圖2所示結構，該子空間立方體群包括兩個子空間立方體，其中標有下劃線的子空間在后續計算時只需計算一次。

Fig.2 Subspace skycube group圖2 子空間立方體群

3.2子空間候選集

通過對子空間立方體群結構中子空間Skyline結果集的充分實驗及觀察，發現結構中相鄰兩層的子空間U和V(U?V)的Skyline結果集skyU和skyV之間并不存在一種明顯的包含關系。例如前文例子中，skya為{P4, P5}，而skyab為{P1, P5, P6}。這種現象是由于數據集中存在多個數據點在某一維度上的值相同而產生的。經分析，定理1可以描述skyU和skyV中數據點之間的隱含關系。

定理1對于給定的d維數據集S，其全空間為D，U和V為兩個子空間，U,V?D，且V是U的父親，則?q∈skyU，在子空間V上滿足下面兩種情況中的一種：（1）屬于skyV；（2）被skyU中的另外某一數據點p所支配。

證明對于skyU中的數據點q，如果在skyU中存在數據點p，p與q在U的所有維度上的值都相等，那么若p在子空間V-U上支配q，則p在V上支配q；如果不存在這樣的數據點p，則q一定屬于skyV，因為在V上沒有任何數據點能支配q。□

根據定理1描述的父親子空間Skyline結果集與孩子子空間Skyline結果集的關系，提出了子空間候選集的概念。對于正在被計算的子空間V,其候選集的計算方法為：先對V所有孩子子空間結果集求并，之后排除在V上被其他數據點支配的數據點，得到的集合則為子空間V的候選集。子空間候選集作用為：第一，實現子空間Skyline結果共享，保證MSSC算法并非獨立地求子空間立方體群中的所有子空間Skyline結果，上層求解過程建立在下層已求結果的基礎上；第二，對于每個子空間的計算過程，減小了數據輸入量；第三，由于候選集中的數據點一定屬于當前子空間V的Skyline結果，有效避免了對這一部分數據點的支配關系判斷過程，大量減少了比較次數。因此子空間候選集的使用，有效提高了算法效率。算法2子空間候選集生成算法createSCS(V,SSC)輸入：當前正在計算的子空間V；以V為頂點的子空間立方體SSC

輸出：子空間V的候選集SCS 1. SCS←union(SSC)

//將SCS初始化為V的所有孩子空間Skyline結果集的并

2. for i←0 to |V| do//對于V的每一個孩子子空間Ui

3.for every point p∈skyUido //對于skyUi中的每

個數據點p

4.BUF←getEqualPoint(p, Ui)

//找出與p在Ui上相同的點，放入BUF

5.if BUF≠?then //如果存在與p在Ui上相同的點

6.BUF←p //將p也放入BUF

7.TEMP←BUF-getSkyline(BUF,V-Ui)

//將不是V上的Skyline結果的點找出

8.SCS←SCS-TEMP

//從SCS中將非V上Skyline點刪除

9.end if

10. end for

11. end for

12. return SCS

算法2依據定理1中描述的子空間Skyline結果集之間的關系，保證了結果集的有效性和正確性，對每個子空間生成一個候選集。算法的輸入為正在計算的子空間V以及以V為頂點的除V外全部計算完成的子空間立方體。首先，對V下一層所有子空間（V的孩子子空間）Skyline結果集求并，并賦給SCS，時間復雜度為O(1)；之后，只需將不屬于skyV的數據點從SCS中刪除即可。根據定理1，判斷skyU中的一個數據點p是否屬于skyV，只需將skyU中與p在U上相等的數據點與p進行比較，當skyU中不存在與p 在U上相等的點時，則p一定屬于skyV；如果存在這樣的點，則在V-U上判定這些點中有哪些屬于skyV。由于各子空間U上的Skyline結果集都是按照數據點在U上各維度數值和的非遞減排序方式存儲，上述操作的時間開銷非常小。當SCS中不存在非skyV數據點時，為最優情況，時間復雜度為O(m lb m)，其中m為skyU所包含數據點的個數；當求得的BUF均不為空時，為最差，時間復雜度為O(m lb m+mt2)，其中t為BUF中包含的數據個數，該值一般極小。

3.3求和過濾方法

計算某一子空間V的Skyline結果集skyV時，支配關系判定過程不可避免。傳統方法是將待判定數據點p與當前skyV中數據點在V空間上逐個比較，從而得出p點是否可以放入skyV，這一過程的時間復雜度為O(d)。當數據維度較高時，時間開銷會很大，而該過程在算法執行過程中會被重復調用很多次。因此若能降低該過程的時間復雜度，則算法效率會大幅度提升。對此，采用求和過濾方法對該過程進行優化（對應于算法3中的第16行），該過濾條件執行的時間復雜度為O(1)，若滿足該條件，則不必對數據點p進行支配關系判定。顯然，通過該方法，在算法執行過程中，時間復雜度為O(d)的支配關系判定過程次數將大大減少。

該過濾條件是利用數據點在子空間V上的維度值的和進行過濾，對于某一數據點p，p在子空間V上的過濾器設計為：

該公式表明，p點在V上的過濾值為FV(p)，該值等于p點在V上所有維度值的和。通過該過濾器，很容易初步判定兩個數據點p和q的支配關系，如果FV(p)≤FV(q)，顯然表明q在V空間上不可能支配p，因為在V上，q至少有一個維度上的值大于p。

MSSC算法執行過程中，兩處利用該過濾值提高效率。首先，所有子空間Skyline結果集中的數據點均按照該過濾值從小到大排序；此外，在計算skyV時，判定數據點p與當前skyV中數據點q的支配關系之前進行過濾條件測試，若FV(p)≤FV(q)，則顯然skyV中數據點q無法支配p，并且因為skyV中數據點按過濾值非遞減排序，所以q之后的點也無法支配p點，則p點直接放入skyV中即可；若FV(p)>FV(q)，才需對數據點p和q進行逐個維度上的數值比較以確定支配關系。

3.4 MSSC算法

本節提出基于子空間立方體群結構的多子空間Skyline查詢算法——MSSC算法。

算法3 MSSC算法

輸入：數據集S；子空間集合O={V1,V2,…,Vv}

輸出：每個子空間上的Skyline結果skyV1,skyV2,…, skyVv

1.SSG←createSSG(O) //生成子空間立方體群

2.lai←sort data on each aiin the first level of SSG //將數據集S分別在SSG中的第一層各維度ai(1

3.skyai←points with min value on aiin lai

// SSG中第一層的子空間結果直接得出

4.for every SSC in the SSG do

//對于SSG中的每個子空間立方體

5.for every subspace V from level 2 to top do

//對于第二層開始到頂端的每個子空間V

6.if V is done then continue

//V已經被計算過，則跳過該子空間

7.skyV←?

8.SCS←createSCS(V, SSC) //求出當前子空間的候選集

9.choose a list lai(ai∈V) //從當前子空間V中選一個排好序的維度序列

10.for every point p in lai

do //對于序列中的每個數據點

11.if m in (p)≥max (skyV) then continue

12.else if p∈SCS then //當前點屬于候選集，直接將p放入skyV

13.insert p into skyVaccording to FV(p) //根據過濾值大小插入到skyV相應位置

14.else

15.for every point q in skyVdo

16.if FV(p)≤FV(q) then //滿足求和

過濾條件，則直接將p放入skyV

17.insert p into skyVaccording to

FV(p)

18.break

19.else if q dom inate p then break

// p被q支配，則刪除當前p點

20.end for

21.if skyVis end then //說明沒有能支

配p的數據點，則將p放入skyV

22.insert p into skyVaccording to FV(p)

23.end for

24.end for

25.end for

26. return skyV1,skyV2,…, skyVn

如算法3所示，首先利用算法1將待求子空間集合O轉化為子空間立方體群，時間復雜度為O(v lb v+2max(| |Vi))；之后將數據集分別在第一層各維度上排序，這樣既可保證生成子空間候選集過程的高效性，又可直接得出第一層子空間的Skyline結果，該過程最多只要進行d次排序，相比傳統算法的2d-1次排序有很大提升；接下來從第二層開始每個子空間的Skyline求解過程，均建立在已計算的所有子空間Skyline結果的基礎上，先利用算法2生成當前子空間的候選集，時間復雜度為O(m lb m+mt2)，然后選取一個數據序列lai對數據集進行遍歷，逐個生成每個子空間的Skyline結果（10行至23行）。

對數據序列遍歷并生成結果集時，最耗時、調用最頻繁的操作是數據點間支配關系判定運算（第19行），因此對該過程的優化是提高算法效率的關鍵所在。MSSC算法主要采用以下方法進行優化。

（1）最大值裁剪（第11行）：采用最大值裁剪方法，即數據點p在子空間V上的最小值若大于目前skyV中的最大值，則顯然數據點p會被skyV中的某一點支配，因此可以直接刪除這些數據點。

（2）子空間候選集過濾（第12、13行）：通過3.2節可知，子空間候選集SCS中的數據點必定為當前子空間的Skyline結果，因此這些數據點可以直接被加入到skyV中，顯然子空間候選集將數據輸入量從原始數據集的n減小到n-count(SCS)。

（3）求和過濾方法（第16至18行）：根據3.3節對求和過濾器的描述，當數據點p的過濾值小于等于skyV中某一點的過濾值時，說明p點不可能被skyV中任何一點所支配，因此這樣的數據點p一定為當前子空間V的Skyline結果。

從上述描述可以發現，3種方法的過濾效果主要體現在兩個方面：第一，3種方法將大部分數據點的復雜度為O(d)的支配關系判定操作排除，時間復雜度降低為O(1)；第二，將每個子空間的數據輸入量縮減到n-count(SCS)，而越上層的子空間所對應的count(SCS)越大，效果越明顯。綜上所述，很容易得出MSSC算法的時間復雜度為O[vn(t1+(n-count(SCS)))]。其中v為子空間個數，n為數據點數，t1為生成子空間候選集的耗時，count(SCS)為子空間候選集中包含數據點的個數。值得注意的是，t1值較小，而count(SCS)值一般較大，因此n-count(SCS)趨近于常數。

4 實驗及分析

下面驗證MSSC算法的有效性及性能。目前沒有專門針對同時計算多個子空間Skyline查詢的算法，因此通過實驗與可以解決該問題的Subsky算法和BUS算法進行對比。其中Subsky算法需要多次執行來完成多子空間Skyline計算，每次選取前n個點為anchor，設定n為10，而BUS算法將全空間作為輸入執行一次即可。

MSSC算法的有效性從兩方面得到證明：首先，實驗利用表1中數據對算法進行測試，計算結果與表2中的理論結果相同；其次，實驗過程中，MSSC算法與Subsky算法、BUS算法的執行結果相同。因此MSSC算法具備有效性。

分別采用人造數據集和真實數據集對MSSC算法進行測試，其中人造數據的生成方法在文獻[1]中有介紹，分為3種：（1）相關數據集，一個數據點在某個維度上相對較優，那么在其他維度上也較優；（2）獨立數據集，數據集中所有維度上的數值都是獨立分布的，即各維度直接沒有相關關系；（3）反相關數據集，數據點在某個維度上較優，則在其他維度上相對較差，3種數據集的全空間維數均為8維。真實數據為NBA球員技術統計數據集（http://www.basketballreference.com）。

實驗分別采用查詢時間和支配關系判定次數兩個指標來對算法性能進行衡量。其中查詢時間為從算法開始直到得出所有子空間Skyline結果的運行時間；支配關系判定次數為算法運行過程中執行的所有支配關系判定的總數，對應于算法3中的第19行。為避免隨機性對實驗結果產生的影響，所有結果均取10次測試的平均值。

實驗所用計算機的操作系統為Windows7，CPU主頻為3.3 GHz，內存為4 GB。所有算法均用C++語言實現，編譯器為Visual Studio2013。

4.1數據量對算法性能的影響

為分析數據量對MSSC算法的影響，本實驗采用相關、獨立和反相關3種人造數據集進行測試，數據點個數n從1×105到5×105變化。系統隨機生成10組子空間組合，每組包含8個子空間，其中最大維度均為6，所求時間和支配關系判定次數為10組子空間求解的平均值。

圖3（a）、（b）、（c）展示了相關、獨立和反相關數據集下3種算法查詢時間對比。可以發現算法的耗時均隨數據量增大而增加，而MSSC算法在3種情況下均明顯優于其他算法，且數據量越大優越性越明顯，主要是因為MSSC算法中的幾種過濾機制。圖4 （a）、（b）、（c）分別展示了3種算法在不同數據集下支配關系判定次數的對比。MSSC算法的表現與查詢時間有著相同的特性，主要由于MSSC算法有效地避免了大量數據點的支配關系判定。此外，相關、獨立和不相關數據集中包含的Skyline數據點數是依次遞增的，因此3種數據集下的查詢時間和支配關系判定次數也相應增加。

4.2待求子空間最大維數對算法性能的影響

從上節實驗中可以發現，正相關數據集下的Skyline結果集包含的數據點數較少，算法性能均較好。因此，實驗利用獨立數據集和反相關數據集進行測試，數據點個數為1×105個。系統隨機生成10組子空間組合，每組包含8個子空間，其中最大維度從2維到8維變化，實驗采取執行時間對算法進行評估，時間為10組子空間求解的平均值。

圖5（a）、（b）分別為獨立數據集和反相關數據集的測試結果。可以發現Subsky算法在子空間維度較小時性能較好，而當最大維度高于6時效率會驟降。BUS算法為完成實驗中的8個子空間計算，要計算數據集的所有子空間，因此查詢效率只與數據的全空間維數和數據量有關，在本實驗中查詢時間基本穩定。而MSSC算法在子空間最大維數較小時的性能與Subsky算法不相上下，主要是因為此時子空間候選集并不能很好地發揮過濾作用，MSSC算法的共享機制無法較好地體現，而計算子空間候選集又耗費一定時間；相反，當維數較高時，性能會明顯優于Subsky算法。

Fig.3 Effect of cardinality on query time under different data sets圖3 不同數據集下數據量對執行時間的影響

Fig.4 Effect of cardinality on dom inance test time under different data sets圖4 不同數據集下數據量對支配關系判定次數的影響

4.3待求子空間個數對算法性能的影響

本實驗主要考察待求子空間個數對算法性能的影響，實驗同樣采用獨立和反相關數據集進行測試，數據點個數為1×105個。在保證最大維數為6的條件下，實驗中子空間個數從1到10變化。從上述兩個實驗中可以發現，在數據量和數據維度不變的情況下，BUS算法的性能不發生變化，因此本實驗主要將MSSC算法與Subsky算法進行對比。

圖6（a）、（b）分別為獨立數據集和反相關數據集的測試結果。可以看出，Subsky是對每個子空間分別計算，因此該算法的查詢時間幾乎與子空間個數成正比。而MSSC算法在子空間個數增長時，子空間立方體的數目不會過多增長，因此算法時間并不會成倍增加。此外，在獨立數據集下，當子空間個數小于3時，MSSC算法并不優于Subsky算法。這主要是由于MSSC算法執行之前要做一部分準備工作，當子空間個數較少時，算法的性能不能很好地體現，而個數增加后，準備工作的作用將很好地展現，因此性能會遠高于多次執行的Subsky算法。

4.4真實數據下的算法性能

Fig.5 Effect of max dimensionality on query timeunder different data sets圖5 不同數據集下最大查詢維數對查詢時間的影響

Fig.6 Effect of subspace number on query timeunder different data sets圖6 不同數據集下子空間個數對查詢時間的影響

圖7和圖8為真實數據下的實驗結果，可以發現測試結果與人造標準數據下的結果保持一致。其中，BUS算法由于數據量和數據全空間維度均未發生改變，性能平穩；Subsky算法性能依然隨子空間個數和最大維度的增加而大幅下降，MSSC算法在高維和多子空間條件下均呈現優良性能。

Fig.7 Effect of subspace number on query time圖7 子空間個數對查詢時間的影響

Fig.8 Effect of max dimensionality on query time圖8 最大維數對查詢時間的影響

5 結束語

本文從用戶多角度審視數據集的需求出發，提出了一種針對多子空間Skyline查詢問題的解決方案。首先，提出了子空間立方體群的概念，并給出由待求子空間集合生成子空間立方體群結構的算法；基于該結構，提出了一種同時處理多個子空間Skyline查詢的算法——MSSC算法，有效地解決了多子空間Skyline查詢問題。算法實施過程中，充分利用共享孩子子空間Skyline結果集的方法，直接將子空間候選集中的數據放入結果集，減少了支配關系判定次數；此外，算法還采用最大值剪枝、求和過濾等方法進一步降低支配關系判定次數，有效地提高了算法效率。最后，利用多個數據集對MSSC算法性能進行全方位的評估。實驗結果顯示，MSSC算法解決了現有子空間Skyline算法在解決多子空間Skyline查詢問題時的不足，具有明顯的優勢。

下一步研究工作將重點關注如何將MSSC算法用于云平臺，以實現分布式環境下的多子空間Skyline查詢。

References:

[1] Borzsony S, Kossmann D, Stocker K. The skyline operator [C]//Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany, 2001. Piscataway, USA: IEEE, 2001: 421-430.

[2] Deb K. Multi-objective optim ization[M]//Search Methodologies. New York: Springer US, 2014: 403-449.

[3] Tao Yufei, Xiao Xiaokui, Pei Jian. Subsky: efficient computation of skylines in subspaces[C]//Proceedings of the 22nd International Conference on Data Engineering, Atlanta, USA, 2006. Piscataway, USA: IEEE, 2006: 65.

[4] Yuan Yidong, Lin Xuem in, Liu Qing, et al. Efficient computation of the skyline cube[C]//Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway,Aug 30-Sep 2, 2005: 241-252.

[5] Pei J, Jin W, Ester M, et al. Catching the best views of skyline: a semantic approach based on decisive subspaces[C]// Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, Aug 30-Sep 2, 2005: 253-264.

[6] Chomicki J, Godfrey P, Gryz J, et al. Skyline with presorting: theory and optimizations[C]//Proceedings of the 2005 International Conference on Intelligent Information Processing and Web M ining, Gdansk, Poland, Jun 13-16, 2005. Berlin, Heidelberg: Springer, 2005: 595-604.

[7] Wang Xiaowei, Huang Jiuming, Jia Yan. Probabilistic Skyline computation on distributed uncertain data[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4 (10): 951-960.

[8] 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, Italy, Sep 11-14, 2001: 301-310.

[9] 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, China, 2002: 275-286.

[10] Tao Yufei, Xiao Xiaokui, Pei Jian. Efficient skyline and topk retrieval in subspaces[J]. IEEE Transactions on Know ledge and Data Engineering, 2007, 19(8): 1072-1088.

[11] Dellis E, Vlachou A, V ladimirskiy I, et al. Constrained subspace skyline computation[C]//Proceedings of the 15th International Conference on Information and Know ledge Management, Arlington, USA, Nov 6-11, 2006. New York, USA:ACM, 2006: 415-424.

[12] Jin Wen, Tung A K H, Ester M, et al. On efficient processing of subspace skyline queries on high dimensional data[C]// Proceedings of the 19th International Conference on Scientific and Statistical Database Management, Banff, Canada, 2007. Washington, USA: IEEE Computer Society, 2007: 12. [13] Pei Jian, Fu A W C, Lin Xuem in, et al. Computing compressed multidimensional skyline cubes efficiently[C]//Proceedings of the 23rd International Conference on Data Engineering, Istanbul, Turkey, Apr 15-20, 2007. Piscataway, USA: IEEE, 2007: 96-105.

[14] Xia Tian, Zhang Donghui. Refreshing the sky: the compressed skycube w ith efficient support for frequent updates [C]//Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, Chicago, USA, 2006. New York, USA:ACM, 2006: 491-502.

[15] Kailasam G T, Lee J S, Rhee J W, et al. Efficient skycube computation using point and domain-based filtering[J]. Information Sciences, 2010, 180(7): 1090-1103.

[16] Banafaa K M, Li Ruixuan. Efficient algorithms for constrained subspace skyline query in structured peer-to-peer systems[C]//LNCS 7418: Proceedings of the 13th International Conference on Web-Age Information Management, Harbin, China, Aug 18-20, 2012. Berlin, Heidelberg: Springer, 2012: 334-345.

[17] Lee J, Hwang S. Toward efficient multidimensional subspace skyline computation[J]. The VLDB Journal, 2014, 23 (1): 129-145.

[18] Vlachou A, Doulkeridis C, Kotidis Y, et al. Efficient routing of subspace skyline queries over highly distributed data[J]. IEEE Transactions on Know ledge and Data Engineering, 2010, 22(12): 1694-1708.

附中文參考文獻：

[7]王曉偉,黃九鳴,賈焰.分布式不確定數據上的概率Skyline計算[J].計算機科學與探索, 2010, 4(10): 951-960.

WANG Xiaoyi was born in 1992. He is an M.S. candidate at Nanjing University of Aeronautics and Astronautics. His research interests include data management and query, distributed database and cloud computing, etc.

王瀟逸（1992—），男，吉林公主嶺人，南京航空航天大學計算機科學與技術學院碩士研究生，主要研究領域為數據管理與查詢，分布式數據庫，云計算等。

QIN Xiaolin was born in 1953. He is a professor and Ph.D. supervisor at Nanjing University of Aeronautics and Astronautics, and the senior member of CCF. His research interests include spatial and spatio-temporal databases, data management and security in distributed environment, etc.

秦小麟（1953—），男，江蘇南京人，南京航空航天大學教授、博士生導師，CCF高級會員，主要研究領域為空間與時空數據庫，分布式數據管理與安全等。

WANG Ning was born in 1987. He is a lecturer and Ph.D. candidate at Nanjing University of Aeronautics and Astronautics. His research interests include data management and secure localization for w ireless sensor network, etc.

王寧（1987—），男，山東威海人，南京航空航天大學講師、博士研究生，主要研究領域為數據管理，無線傳感器網絡位置安全等。

SHI Wenhao was born in 1988. He is an M.S. candidate at Nanjing University of Aeronautics and Astronautics. His research interests include access control and cloud computing, etc.

史文浩（1988—），男，河北衡水人，南京航空航天大學計算機科學與技術學院碩士研究生，主要研究領域為訪問控制，云計算技術等。

Efficient Algorithm for M ultiple Subspace SkylineQueries Processing?

WANG Xiaoyi+, QIN Xiaolin, WANG Ning, SHI Wenhao
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
+ Corresponding author: E-mail: xywang515829@nuaa.edu.cn

WANG Xiaoyi, QIN Xiaolin, WANG Ning, et al. Efficient algorithm for multip le subspace Skylinequeriesprocessing. Journal of Frontiersof Computer Scienceand Technology, 2016, 10(5)：623-634.

Abstract:As Skyline queries are w idely used, subspace Skyline query processing has attracted lots of attention. Aiming at meeting the need that users want to evaluate a dataset from multiple perspectives, this paper makes a full study of multiple subspace Skyline queries. Motivated by the deficiency of existing algorithms, this paper proposes the structure of subspace skycube group, and puts forward an efficient method called MSSC (multiple subspace skycube) based on that structure. The MSSC algorithm can efficiently process any number of subspace Skyline queries simultaneously. Firstly, the MSSC algorithm uses subspace candidate sets to share the results of different subspace Skyline queries in the subspace Skycube group. Then it adopts sum filter and max-value filter to cut and filter data, which further improves the performance of the MSSC algorithm.At last, the experiments conducted on both synthetic data sets and a reallife data set demonstrate that the MSSC algorithm can solve the multiple subspace Skyline queries problem efficiently. Key words: multiple subspace Skyline queries; subspace list; subspace skycube group; subspace candidate set

doi:10.3778/j.issn.1673-9418.1507073

文獻標志碼：A

中圖分類號：TP311