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

?

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

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

南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京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 (國(guó)家自然科學(xué)基金); the Priority Academic Development Program of Jiangsu Higher Education Institutions (江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目); the Foundation of Graduate Innovation Center in Nanjing University of Aeronautics and Astronautics under Grant No. kfjj20151607 (南京航空航天大學(xué)研究生創(chuàng)新實(shí)驗(yàn)室開(kāi)放基金).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-09-16, http://www.cnki.net/kcms/detail/11.5602.TP.20150916.0958.002.htm l

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

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

1 引言

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

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

（1）某用戶同時(shí)關(guān)注一個(gè)數(shù)據(jù)集的多個(gè)不同維度組合。例如，足球隊(duì)員數(shù)據(jù)集包括速度、體能、射門(mén)精度、搶斷、力量5個(gè)維度。教練為掌握球員的狀況，對(duì)于前鋒和后衛(wèi)，同時(shí)發(fā)出兩條查詢：

查詢1查詢速度快并且射門(mén)精度高的球員。

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

（2）多個(gè)用戶分別關(guān)心一個(gè)數(shù)據(jù)集的不同組合。例如，飯店數(shù)據(jù)集包括距離、價(jià)位、服務(wù)態(tài)度、餐廳環(huán)境、菜量、口味6個(gè)維度。甲乙丙3人相約聚餐，分別根據(jù)自己不同的喜好發(fā)出3條查詢：

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

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

查詢5查詢服務(wù)態(tài)度好并且環(huán)境好的餐廳。

上述問(wèn)題概括為：對(duì)于某數(shù)據(jù)集，系統(tǒng)中同時(shí)存在多個(gè)不同維度組合上的子空間Skyline查詢，稱(chēng)為多子空間Skyline查詢問(wèn)題。目前有關(guān)子空間Skyline查詢的算法大多集中在某一特定子空間以及全部子空間，在解決任意數(shù)量的子空間Skyline查詢時(shí)效率低下。對(duì)此，本文提出一種可以高效處理多個(gè)子空間Skyline查詢的算法，主要貢獻(xiàn)如下：

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

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

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

（4）同時(shí)采用人造數(shù)據(jù)和真實(shí)數(shù)據(jù)對(duì)算法性能進(jìn)行評(píng)估，實(shí)驗(yàn)結(jié)果證明，MSSC算法能高效解決多子空間Skyline查詢問(wèn)題。

本文結(jié)構(gòu)如下：第2章介紹Skyline查詢的基礎(chǔ)知識(shí)及相關(guān)工作，并分析現(xiàn)有方法在解決多子空間Skyline查詢時(shí)的不足；第3章提出MSSC算法，并對(duì)算法進(jìn)行詳盡的解析；第4章對(duì)MSSC算法進(jìn)行實(shí)驗(yàn)評(píng)估，并與現(xiàn)有算法進(jìn)行性能對(duì)比；最后對(duì)本文工作進(jìn)行總結(jié)。

2 背景知識(shí)

2.1 Skyline查詢概述

首先介紹支配的概念，為便于描述，假定數(shù)據(jù)集在每個(gè)維度上均越小越優(yōu)。

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

在Skyline查詢中，把數(shù)據(jù)集所有維度組成的集合稱(chēng)為全空間，在全空間上的Skyline查詢稱(chēng)為全空間Skyline查詢，即用戶關(guān)心數(shù)據(jù)的所有屬性。

定義2（全空間Skyline查詢）給定一個(gè)d維數(shù)據(jù)集S，以及維度組合U，如果U=D，則稱(chēng)查詢U上所有不被任何其他點(diǎn)支配的數(shù)據(jù)點(diǎn)的集合，為全空間Skyline查詢。

子空間Skyline查詢，即用戶關(guān)心查詢對(duì)象的部分屬性。

定義3（子空間Skyline查詢）給定一個(gè)d維數(shù)據(jù)集S，以及維度組合U，如果U?D，則稱(chēng)查詢U上所有不被任何其他點(diǎn)支配的數(shù)據(jù)點(diǎn)的集合，為子空間Skyline查詢。

表1為簡(jiǎn)化的旅館信息數(shù)據(jù)集，該數(shù)據(jù)集有4個(gè)維度，10個(gè)數(shù)據(jù)點(diǎn)。根據(jù)上述定義，若用戶甲發(fā)出查詢“查找價(jià)格低、等級(jí)高、房間大并且距離小的賓館”，則為全空間Skyline查詢，其查詢結(jié)果為{P1,P2, P3,P4,P5,P6,P7}?？梢?jiàn)全空間Skyline結(jié)果集包含的數(shù)據(jù)點(diǎn)數(shù)過(guò)多（占總數(shù)的70%），并沒(méi)有為用戶帶來(lái)較高的參考價(jià)值。因此，更多的用戶可能只關(guān)注少數(shù)幾個(gè)維度的組合，比如用戶乙發(fā)出查詢“查找價(jià)格低并且距離小的賓館”，該查詢?yōu)樽涌臻gSkyline查詢，其結(jié)果為{P3,P4}。表2為該數(shù)據(jù)集上所有子空間的Skyline結(jié)果集。

Table 1 Simplified hotel information data set表1 簡(jiǎn)化的旅館信息數(shù)據(jù)集

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

2.2相關(guān)工作

數(shù)據(jù)庫(kù)領(lǐng)域?qū)kyline查詢的研究主要分為全空間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]，避免了遍歷整個(gè)數(shù)據(jù)集；Kossmann等人[9]在R樹(shù)索引基礎(chǔ)上提出最近鄰（nearest neighbor，NN）算法，該算法遞歸搜索區(qū)域的最近鄰點(diǎn)，并通過(guò)區(qū)域剪枝技術(shù)刪除被最近鄰點(diǎn)支配的所有對(duì)象。

隨數(shù)據(jù)庫(kù)中數(shù)據(jù)維數(shù)的增大以及數(shù)據(jù)量的擴(kuò)增，全空間Skyline查詢結(jié)果包含極多的數(shù)據(jù)點(diǎn)，意義不大，用戶更多關(guān)注子空間上的Skyline查詢。關(guān)于子空間Skyline查詢的研究主要包括以下工作：

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

此外，研究者還圍繞全部子空間的Skyline查詢進(jìn)行研究。Yuan等人[4]研究了如何高效計(jì)算某一數(shù)據(jù)集所有子空間Skyline查詢的結(jié)果，并提出Skycube概念，給出計(jì)算Skycube的算法；Pei等人[5]在Skycube的基礎(chǔ)上，提出Skyline分組概念，并對(duì)其在語(yǔ)義層面進(jìn)行解釋?zhuān)笥衷谖墨I(xiàn)[13]中提出一種Stellar算法來(lái)計(jì)算壓縮的Skycube，這種方法避免了枚舉所有子空間；與之相似，Xia等人[14]提出一種壓縮Skycube層次數(shù)據(jù)結(jié)構(gòu)（compressed skycube，CSC），并在此基礎(chǔ)上給出一個(gè)有效處理Skyline查詢的方法QueryCSC。上述方法均是一次性求解所有子空間的Skyline結(jié)果。

除上述外，研究者們?cè)赟kyline查詢的其他方向也取得諸多成果。Kailasam等人[15]利用位圖結(jié)構(gòu)計(jì)算Skycube中所有子空間結(jié)果；文獻(xiàn)[16]研究了對(duì)等網(wǎng)絡(luò)中的子空間Skyline查詢；文獻(xiàn)[17]研究了Skyline分組問(wèn)題，并給出QSkycube算法；此外，在分布式環(huán)境中，文獻(xiàn)[7]提出了分布式不確定數(shù)據(jù)上概率Skyline查詢的低通信開(kāi)銷(xiāo)算法，文獻(xiàn)[18]研究了分布式環(huán)境中特定子空間Skyline求解方法。

經(jīng)調(diào)研，現(xiàn)有算法沒(méi)有針對(duì)求解任意多個(gè)子空間Skyline查詢的研究。雖然少數(shù)已有算法可以用來(lái)解決多子空間Skyline查詢問(wèn)題，卻有以下不足：

（1）一些算法[1,6]求解每個(gè)子空間Skyline結(jié)果時(shí)均需要遍歷整個(gè)數(shù)據(jù)集至少一遍，效率較低。

（2）無(wú)需遍歷整個(gè)數(shù)據(jù)集的算法[8,11]需要建立索引結(jié)構(gòu)，而在解決多子空間Skyline查詢時(shí)，則需要建立多個(gè)索引（最多建立2n-1個(gè)索引）。而建立索引的開(kāi)銷(xiāo)非常大，因此類(lèi)方法對(duì)于解決多子空間Skyline查詢問(wèn)題顯然效率低下。

（3）現(xiàn)有算法用來(lái)解決該問(wèn)題時(shí)，一類(lèi)是要運(yùn)行多次逐個(gè)求解每個(gè)子空間Skyline結(jié)果[3,5]，效率很低；另一類(lèi)是一次性計(jì)算出所有2n-1個(gè)子空間Skyline結(jié)果[4-5,13]，計(jì)算結(jié)果冗余，耗時(shí)高。

綜上，多子空間Skyline查詢問(wèn)題是一個(gè)具有挑戰(zhàn)性的問(wèn)題，提出的MSSC算法可以高效地同時(shí)求解任意多個(gè)子空間Skyline查詢。

3 多子空間Skyline查詢算法

此部分將給出求解多子空間Skyline查詢問(wèn)題的MSSC算法。首先基于Skycube概念提出子空間立方體群結(jié)構(gòu)，基于此，有效實(shí)施了MSSC算法。算法執(zhí)行過(guò)程中，采用多種剪枝方式進(jìn)行優(yōu)化，最終，算法有效返回系統(tǒng)中所有的子空間Skyline查詢結(jié)果。后文中，用skyV表示子空間V上的Skyline結(jié)果集，并假設(shè)數(shù)據(jù)集所有維度上的值越小越好。

3.1子空間立方體群

為充分利用子空間結(jié)果集之間的共享關(guān)系，減少算法的時(shí)間開(kāi)銷(xiāo)，在Skycube結(jié)構(gòu)基礎(chǔ)上，提出子空間立方體群概念。

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

Fig.1 Skycube of hotel information data set圖1 旅館數(shù)據(jù)集的Skycube結(jié)構(gòu)

基于Skycube結(jié)構(gòu)，定義4給出子空間立方體概念。

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

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

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

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

算法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生成一個(gè)子

空間立方體

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

7.end if

8.end for

9.return SSG //將子空間立方體群結(jié)構(gòu)返回

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

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

3.2子空間候選集

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

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

證明對(duì)于skyU中的數(shù)據(jù)點(diǎn)q，如果在skyU中存在數(shù)據(jù)點(diǎn)p，p與q在U的所有維度上的值都相等，那么若p在子空間V-U上支配q，則p在V上支配q；如果不存在這樣的數(shù)據(jù)點(diǎn)p，則q一定屬于skyV，因?yàn)樵赩上沒(méi)有任何數(shù)據(jù)點(diǎn)能支配q?！?/p>

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

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

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

2. for i←0 to |V| do//對(duì)于V的每一個(gè)孩子子空間Ui

3.for every point p∈skyUido //對(duì)于skyUi中的每

個(gè)數(shù)據(jù)點(diǎn)p

4.BUF←getEqualPoint(p, Ui)

//找出與p在Ui上相同的點(diǎn)，放入BUF

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

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

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

//將不是V上的Skyline結(jié)果的點(diǎn)找出

8.SCS←SCS-TEMP

//從SCS中將非V上Skyline點(diǎn)刪除

9.end if

10. end for

11. end for

12. return SCS

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

3.3求和過(guò)濾方法

計(jì)算某一子空間V的Skyline結(jié)果集skyV時(shí)，支配關(guān)系判定過(guò)程不可避免。傳統(tǒng)方法是將待判定數(shù)據(jù)點(diǎn)p與當(dāng)前skyV中數(shù)據(jù)點(diǎn)在V空間上逐個(gè)比較，從而得出p點(diǎn)是否可以放入skyV，這一過(guò)程的時(shí)間復(fù)雜度為O(d)。當(dāng)數(shù)據(jù)維度較高時(shí)，時(shí)間開(kāi)銷(xiāo)會(huì)很大，而該過(guò)程在算法執(zhí)行過(guò)程中會(huì)被重復(fù)調(diào)用很多次。因此若能降低該過(guò)程的時(shí)間復(fù)雜度，則算法效率會(huì)大幅度提升。對(duì)此，采用求和過(guò)濾方法對(duì)該過(guò)程進(jìn)行優(yōu)化（對(duì)應(yīng)于算法3中的第16行），該過(guò)濾條件執(zhí)行的時(shí)間復(fù)雜度為O(1)，若滿足該條件，則不必對(duì)數(shù)據(jù)點(diǎn)p進(jìn)行支配關(guān)系判定。顯然，通過(guò)該方法，在算法執(zhí)行過(guò)程中，時(shí)間復(fù)雜度為O(d)的支配關(guān)系判定過(guò)程次數(shù)將大大減少。

該過(guò)濾條件是利用數(shù)據(jù)點(diǎn)在子空間V上的維度值的和進(jìn)行過(guò)濾，對(duì)于某一數(shù)據(jù)點(diǎn)p，p在子空間V上的過(guò)濾器設(shè)計(jì)為：

該公式表明，p點(diǎn)在V上的過(guò)濾值為FV(p)，該值等于p點(diǎn)在V上所有維度值的和。通過(guò)該過(guò)濾器，很容易初步判定兩個(gè)數(shù)據(jù)點(diǎn)p和q的支配關(guān)系，如果FV(p)≤FV(q)，顯然表明q在V空間上不可能支配p，因?yàn)樵赩上，q至少有一個(gè)維度上的值大于p。

MSSC算法執(zhí)行過(guò)程中，兩處利用該過(guò)濾值提高效率。首先，所有子空間Skyline結(jié)果集中的數(shù)據(jù)點(diǎn)均按照該過(guò)濾值從小到大排序；此外，在計(jì)算skyV時(shí)，判定數(shù)據(jù)點(diǎn)p與當(dāng)前skyV中數(shù)據(jù)點(diǎn)q的支配關(guān)系之前進(jìn)行過(guò)濾條件測(cè)試，若FV(p)≤FV(q)，則顯然skyV中數(shù)據(jù)點(diǎn)q無(wú)法支配p，并且因?yàn)閟kyV中數(shù)據(jù)點(diǎn)按過(guò)濾值非遞減排序，所以q之后的點(diǎn)也無(wú)法支配p點(diǎn)，則p點(diǎn)直接放入skyV中即可；若FV(p)>FV(q)，才需對(duì)數(shù)據(jù)點(diǎn)p和q進(jìn)行逐個(gè)維度上的數(shù)值比較以確定支配關(guān)系。

3.4 MSSC算法

本節(jié)提出基于子空間立方體群結(jié)構(gòu)的多子空間Skyline查詢算法——MSSC算法。

算法3 MSSC算法

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

輸出：每個(gè)子空間上的Skyline結(jié)果skyV1,skyV2,…, skyVv

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

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

3.skyai←points with min value on aiin lai

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

4.for every SSC in the SSG do

//對(duì)于SSG中的每個(gè)子空間立方體

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

//對(duì)于第二層開(kāi)始到頂端的每個(gè)子空間V

6.if V is done then continue

//V已經(jīng)被計(jì)算過(guò)，則跳過(guò)該子空間

7.skyV←?

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

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

10.for every point p in lai

do //對(duì)于序列中的每個(gè)數(shù)據(jù)點(diǎn)

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

12.else if p∈SCS then //當(dāng)前點(diǎn)屬于候選集，直接將p放入skyV

13.insert p into skyVaccording to FV(p) //根據(jù)過(guò)濾值大小插入到skyV相應(yīng)位置

14.else

15.for every point q in skyVdo

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

過(guò)濾條件，則直接將p放入skyV

17.insert p into skyVaccording to

FV(p)

18.break

19.else if q dom inate p then break

// p被q支配，則刪除當(dāng)前p點(diǎn)

20.end for

21.if skyVis end then //說(shuō)明沒(méi)有能支

配p的數(shù)據(jù)點(diǎn)，則將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轉(zhuǎn)化為子空間立方體群，時(shí)間復(fù)雜度為O(v lb v+2max(| |Vi))；之后將數(shù)據(jù)集分別在第一層各維度上排序，這樣既可保證生成子空間候選集過(guò)程的高效性，又可直接得出第一層子空間的Skyline結(jié)果，該過(guò)程最多只要進(jìn)行d次排序，相比傳統(tǒng)算法的2d-1次排序有很大提升；接下來(lái)從第二層開(kāi)始每個(gè)子空間的Skyline求解過(guò)程，均建立在已計(jì)算的所有子空間Skyline結(jié)果的基礎(chǔ)上，先利用算法2生成當(dāng)前子空間的候選集，時(shí)間復(fù)雜度為O(m lb m+mt2)，然后選取一個(gè)數(shù)據(jù)序列l(wèi)ai對(duì)數(shù)據(jù)集進(jìn)行遍歷，逐個(gè)生成每個(gè)子空間的Skyline結(jié)果（10行至23行）。

對(duì)數(shù)據(jù)序列遍歷并生成結(jié)果集時(shí)，最耗時(shí)、調(diào)用最頻繁的操作是數(shù)據(jù)點(diǎn)間支配關(guān)系判定運(yùn)算（第19行），因此對(duì)該過(guò)程的優(yōu)化是提高算法效率的關(guān)鍵所在。MSSC算法主要采用以下方法進(jìn)行優(yōu)化。

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

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

（3）求和過(guò)濾方法（第16至18行）：根據(jù)3.3節(jié)對(duì)求和過(guò)濾器的描述，當(dāng)數(shù)據(jù)點(diǎn)p的過(guò)濾值小于等于skyV中某一點(diǎn)的過(guò)濾值時(shí)，說(shuō)明p點(diǎn)不可能被skyV中任何一點(diǎn)所支配，因此這樣的數(shù)據(jù)點(diǎn)p一定為當(dāng)前子空間V的Skyline結(jié)果。

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

4 實(shí)驗(yàn)及分析

下面驗(yàn)證MSSC算法的有效性及性能。目前沒(méi)有專(zhuān)門(mén)針對(duì)同時(shí)計(jì)算多個(gè)子空間Skyline查詢的算法，因此通過(guò)實(shí)驗(yàn)與可以解決該問(wèn)題的Subsky算法和BUS算法進(jìn)行對(duì)比。其中Subsky算法需要多次執(zhí)行來(lái)完成多子空間Skyline計(jì)算，每次選取前n個(gè)點(diǎn)為anchor，設(shè)定n為10，而B(niǎo)US算法將全空間作為輸入執(zhí)行一次即可。

MSSC算法的有效性從兩方面得到證明：首先，實(shí)驗(yàn)利用表1中數(shù)據(jù)對(duì)算法進(jìn)行測(cè)試，計(jì)算結(jié)果與表2中的理論結(jié)果相同；其次，實(shí)驗(yàn)過(guò)程中，MSSC算法與Subsky算法、BUS算法的執(zhí)行結(jié)果相同。因此MSSC算法具備有效性。

分別采用人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集對(duì)MSSC算法進(jìn)行測(cè)試，其中人造數(shù)據(jù)的生成方法在文獻(xiàn)[1]中有介紹，分為3種：（1）相關(guān)數(shù)據(jù)集，一個(gè)數(shù)據(jù)點(diǎn)在某個(gè)維度上相對(duì)較優(yōu)，那么在其他維度上也較優(yōu)；（2）獨(dú)立數(shù)據(jù)集，數(shù)據(jù)集中所有維度上的數(shù)值都是獨(dú)立分布的，即各維度直接沒(méi)有相關(guān)關(guān)系；（3）反相關(guān)數(shù)據(jù)集，數(shù)據(jù)點(diǎn)在某個(gè)維度上較優(yōu)，則在其他維度上相對(duì)較差，3種數(shù)據(jù)集的全空間維數(shù)均為8維。真實(shí)數(shù)據(jù)為NBA球員技術(shù)統(tǒng)計(jì)數(shù)據(jù)集（http://www.basketballreference.com）。

實(shí)驗(yàn)分別采用查詢時(shí)間和支配關(guān)系判定次數(shù)兩個(gè)指標(biāo)來(lái)對(duì)算法性能進(jìn)行衡量。其中查詢時(shí)間為從算法開(kāi)始直到得出所有子空間Skyline結(jié)果的運(yùn)行時(shí)間；支配關(guān)系判定次數(shù)為算法運(yùn)行過(guò)程中執(zhí)行的所有支配關(guān)系判定的總數(shù)，對(duì)應(yīng)于算法3中的第19行。為避免隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生的影響，所有結(jié)果均取10次測(cè)試的平均值。

實(shí)驗(yàn)所用計(jì)算機(jī)的操作系統(tǒng)為Windows7，CPU主頻為3.3 GHz，內(nèi)存為4 GB。所有算法均用C++語(yǔ)言實(shí)現(xiàn)，編譯器為Visual Studio2013。

4.1數(shù)據(jù)量對(duì)算法性能的影響

為分析數(shù)據(jù)量對(duì)MSSC算法的影響，本實(shí)驗(yàn)采用相關(guān)、獨(dú)立和反相關(guān)3種人造數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)點(diǎn)個(gè)數(shù)n從1×105到5×105變化。系統(tǒng)隨機(jī)生成10組子空間組合，每組包含8個(gè)子空間，其中最大維度均為6，所求時(shí)間和支配關(guān)系判定次數(shù)為10組子空間求解的平均值。

圖3（a）、（b）、（c）展示了相關(guān)、獨(dú)立和反相關(guān)數(shù)據(jù)集下3種算法查詢時(shí)間對(duì)比?？梢园l(fā)現(xiàn)算法的耗時(shí)均隨數(shù)據(jù)量增大而增加，而MSSC算法在3種情況下均明顯優(yōu)于其他算法，且數(shù)據(jù)量越大優(yōu)越性越明顯，主要是因?yàn)镸SSC算法中的幾種過(guò)濾機(jī)制。圖4 （a）、（b）、（c）分別展示了3種算法在不同數(shù)據(jù)集下支配關(guān)系判定次數(shù)的對(duì)比。MSSC算法的表現(xiàn)與查詢時(shí)間有著相同的特性，主要由于MSSC算法有效地避免了大量數(shù)據(jù)點(diǎn)的支配關(guān)系判定。此外，相關(guān)、獨(dú)立和不相關(guān)數(shù)據(jù)集中包含的Skyline數(shù)據(jù)點(diǎn)數(shù)是依次遞增的，因此3種數(shù)據(jù)集下的查詢時(shí)間和支配關(guān)系判定次數(shù)也相應(yīng)增加。

4.2待求子空間最大維數(shù)對(duì)算法性能的影響

從上節(jié)實(shí)驗(yàn)中可以發(fā)現(xiàn)，正相關(guān)數(shù)據(jù)集下的Skyline結(jié)果集包含的數(shù)據(jù)點(diǎn)數(shù)較少，算法性能均較好。因此，實(shí)驗(yàn)利用獨(dú)立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)點(diǎn)個(gè)數(shù)為1×105個(gè)。系統(tǒng)隨機(jī)生成10組子空間組合，每組包含8個(gè)子空間，其中最大維度從2維到8維變化，實(shí)驗(yàn)采取執(zhí)行時(shí)間對(duì)算法進(jìn)行評(píng)估，時(shí)間為10組子空間求解的平均值。

圖5（a）、（b）分別為獨(dú)立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集的測(cè)試結(jié)果?？梢园l(fā)現(xiàn)Subsky算法在子空間維度較小時(shí)性能較好，而當(dāng)最大維度高于6時(shí)效率會(huì)驟降。BUS算法為完成實(shí)驗(yàn)中的8個(gè)子空間計(jì)算，要計(jì)算數(shù)據(jù)集的所有子空間，因此查詢效率只與數(shù)據(jù)的全空間維數(shù)和數(shù)據(jù)量有關(guān)，在本實(shí)驗(yàn)中查詢時(shí)間基本穩(wěn)定。而MSSC算法在子空間最大維數(shù)較小時(shí)的性能與Subsky算法不相上下，主要是因?yàn)榇藭r(shí)子空間候選集并不能很好地發(fā)揮過(guò)濾作用，MSSC算法的共享機(jī)制無(wú)法較好地體現(xiàn)，而計(jì)算子空間候選集又耗費(fèi)一定時(shí)間；相反，當(dāng)維數(shù)較高時(shí)，性能會(huì)明顯優(yōu)于Subsky算法。

Fig.3 Effect of cardinality on query time under different data sets圖3 不同數(shù)據(jù)集下數(shù)據(jù)量對(duì)執(zhí)行時(shí)間的影響

Fig.4 Effect of cardinality on dom inance test time under different data sets圖4 不同數(shù)據(jù)集下數(shù)據(jù)量對(duì)支配關(guān)系判定次數(shù)的影響

4.3待求子空間個(gè)數(shù)對(duì)算法性能的影響

本實(shí)驗(yàn)主要考察待求子空間個(gè)數(shù)對(duì)算法性能的影響，實(shí)驗(yàn)同樣采用獨(dú)立和反相關(guān)數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)點(diǎn)個(gè)數(shù)為1×105個(gè)。在保證最大維數(shù)為6的條件下，實(shí)驗(yàn)中子空間個(gè)數(shù)從1到10變化。從上述兩個(gè)實(shí)驗(yàn)中可以發(fā)現(xiàn)，在數(shù)據(jù)量和數(shù)據(jù)維度不變的情況下，BUS算法的性能不發(fā)生變化，因此本實(shí)驗(yàn)主要將MSSC算法與Subsky算法進(jìn)行對(duì)比。

圖6（a）、（b）分別為獨(dú)立數(shù)據(jù)集和反相關(guān)數(shù)據(jù)集的測(cè)試結(jié)果。可以看出，Subsky是對(duì)每個(gè)子空間分別計(jì)算，因此該算法的查詢時(shí)間幾乎與子空間個(gè)數(shù)成正比。而MSSC算法在子空間個(gè)數(shù)增長(zhǎng)時(shí)，子空間立方體的數(shù)目不會(huì)過(guò)多增長(zhǎng)，因此算法時(shí)間并不會(huì)成倍增加。此外，在獨(dú)立數(shù)據(jù)集下，當(dāng)子空間個(gè)數(shù)小于3時(shí)，MSSC算法并不優(yōu)于Subsky算法。這主要是由于MSSC算法執(zhí)行之前要做一部分準(zhǔn)備工作，當(dāng)子空間個(gè)數(shù)較少時(shí)，算法的性能不能很好地體現(xiàn)，而個(gè)數(shù)增加后，準(zhǔn)備工作的作用將很好地展現(xiàn)，因此性能會(huì)遠(yuǎn)高于多次執(zhí)行的Subsky算法。

4.4真實(shí)數(shù)據(jù)下的算法性能

Fig.5 Effect of max dimensionality on query timeunder different data sets圖5 不同數(shù)據(jù)集下最大查詢維數(shù)對(duì)查詢時(shí)間的影響

Fig.6 Effect of subspace number on query timeunder different data sets圖6 不同數(shù)據(jù)集下子空間個(gè)數(shù)對(duì)查詢時(shí)間的影響

圖7和圖8為真實(shí)數(shù)據(jù)下的實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)測(cè)試結(jié)果與人造標(biāo)準(zhǔn)數(shù)據(jù)下的結(jié)果保持一致。其中，BUS算法由于數(shù)據(jù)量和數(shù)據(jù)全空間維度均未發(fā)生改變，性能平穩(wěn)；Subsky算法性能依然隨子空間個(gè)數(shù)和最大維度的增加而大幅下降，MSSC算法在高維和多子空間條件下均呈現(xiàn)優(yōu)良性能。

Fig.7 Effect of subspace number on query time圖7 子空間個(gè)數(shù)對(duì)查詢時(shí)間的影響

Fig.8 Effect of max dimensionality on query time圖8 最大維數(shù)對(duì)查詢時(shí)間的影響

5 結(jié)束語(yǔ)

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

下一步研究工作將重點(diǎn)關(guān)注如何將MSSC算法用于云平臺(tái)，以實(shí)現(xiàn)分布式環(huán)境下的多子空間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.

附中文參考文獻(xiàn)：

[7]王曉偉,黃九鳴,賈焰.分布式不確定數(shù)據(jù)上的概率Skyline計(jì)算[J].計(jì)算機(jī)科學(xué)與探索, 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—），男，吉林公主嶺人，南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)管理與查詢，分布式數(shù)據(jù)庫(kù)，云計(jì)算等。

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—），男，江蘇南京人，南京航空航天大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榭臻g與時(shí)空數(shù)據(jù)庫(kù)，分布式數(shù)據(jù)管理與安全等。

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—），男，山東威海人，南京航空航天大學(xué)講師、博士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)管理，無(wú)線傳感器網(wǎng)絡(luò)位置安全等。

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—），男，河北衡水人，南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)樵L問(wèn)控制，云計(jì)算技術(shù)等。

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

文獻(xiàn)標(biāo)志碼：A

中圖分類(lèi)號(hào)：TP311