海量不完整數(shù)據(jù)上基于維度組合的Skyline查詢*

王　妍，銀　彪，劉賡浩，宋寶燕+，王俊陸

1.遼寧大學(xué)信息學(xué)院，沈陽1100362.東北大學(xué)信息與工程學(xué)院，沈陽110819

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0495-09

?

海量不完整數(shù)據(jù)上基于維度組合的Skyline查詢*

王妍1,2，銀彪1，劉賡浩1，宋寶燕1+，王俊陸1

1.遼寧大學(xué)信息學(xué)院，沈陽110036
2.東北大學(xué)信息與工程學(xué)院，沈陽110819

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0495-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61472072, 61472169, 61300233 (國家自然科學(xué)基金); the National Basic Research Program of China under Grant No. 2014CB360509 (國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)); the National Science and Technology Support Program of China under Grant No. 2012BAF13B08 (國家科技支撐計(jì)劃); the Foundation of Science Public Welfare of Liaoning Province under Grant No. 2015003003 (遼寧省科學(xué)事業(yè)公益研究基金項(xiàng)目); the Youth Foundation of Liaoning University under Grant No. LDQN201508 (遼寧大學(xué)青年科研基金).

Received 2015-06,Accepted 2015-09.

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

摘要：隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等信息技術(shù)的快速發(fā)展，多維數(shù)據(jù)日益增多，這些海量數(shù)據(jù)中往往伴隨著大量的不完整數(shù)據(jù)，如何從海量不完整數(shù)據(jù)中高效地獲取用戶所需的近似的結(jié)果集是一個(gè)亟需解決的問題。針對海量高維的不完整數(shù)據(jù)集，提出了一種基于維度組合的Skyline查詢算法，通過構(gòu)建RankList數(shù)據(jù)結(jié)構(gòu)提高查詢效率，并減少不完整數(shù)據(jù)對查詢結(jié)果的影響；利用維度的不同組合，劃分出查詢子空間，并漸進(jìn)地查詢出每個(gè)子空間的最優(yōu)先點(diǎn)，從而獲得海量不完整數(shù)據(jù)集上均勻分布的Skyline點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該算法與Iskyline算法相比，平均查詢效率提高了85%，并且在數(shù)據(jù)量大、維度高時(shí)，較普通方法查詢效率更高。

關(guān)鍵詞：海量不完整數(shù)據(jù)；維度組合；Skyline

1　引言

隨著社會的飛速進(jìn)步和科學(xué)技術(shù)水平的不斷提高，數(shù)據(jù)規(guī)模不斷擴(kuò)大。數(shù)據(jù)通常具有多維的屬性值，且數(shù)據(jù)獲取的方式呈現(xiàn)多樣化，由于設(shè)備或其他原因?qū)е略M數(shù)據(jù)缺失或其屬性值缺失的問題越來越普遍[1]。從海量不完整數(shù)據(jù)中，高效地獲取用戶所需的結(jié)果是一個(gè)亟需解決的問題。

目前，對多維不完整數(shù)據(jù)的處理方法通常是對數(shù)據(jù)集進(jìn)行清洗、修復(fù)等預(yù)處理[2-4]，然后再通過Skyline[5-6]等方法進(jìn)行查詢處理。而在海量數(shù)據(jù)的背景下，預(yù)處理階段需要花費(fèi)大量的時(shí)間代價(jià)。為節(jié)省預(yù)處理的時(shí)間，一些學(xué)者提出，根據(jù)不完整數(shù)據(jù)缺失屬性將它們分到不同的屬性缺失列中，并動態(tài)查找Skyline點(diǎn)。但是Skyline查詢隨著數(shù)量的增大和維度的增加，查詢代價(jià)呈指數(shù)增長，此方法不適用于海量不完整數(shù)據(jù)集。有些學(xué)者為了提高Skyline算法的查詢效率，提出了低維抽樣組合的算法。該算法查詢效率得到提升，但只能查詢出數(shù)據(jù)集中的局部輪廓點(diǎn)，會缺失較多全局Skyline點(diǎn)。

對于海量的維數(shù)較高的不完整數(shù)據(jù)，本文摒棄了傳統(tǒng)方法中的預(yù)處理階段，給出一種對這類數(shù)據(jù)直接查詢處理的方法：海量不完整數(shù)據(jù)上基于維度組合的Skyline查詢（combination of dimension Skyline query, CDskyline）。該方法首先構(gòu)建RankList數(shù)據(jù)結(jié)構(gòu)，然后基于維度組合進(jìn)行子空間的劃分，并對子空間進(jìn)行編碼。這種策略充分考慮了各個(gè)維度組合的查詢結(jié)果，并減少了不完整數(shù)據(jù)對查詢結(jié)果的影響。通過掃描RankList結(jié)構(gòu)，查詢出各個(gè)子空間的最優(yōu)先點(diǎn)，從而得到最終的查詢結(jié)果。所得結(jié)果均勻分布并接近真實(shí)輪廓。最后進(jìn)行了實(shí)驗(yàn)，結(jié)果表明CDskyline算法高效適用于海量不完整數(shù)據(jù)，并顯著提高了查詢效率，快速獲取了用戶所需的近似結(jié)果。

2　相關(guān)工作

文獻(xiàn)[7]提出了RBSSQ（replacement based Skyline sets queries）算法，通過替換策略解決了Skyline查詢中數(shù)據(jù)元組屬性丟失的問題。文獻(xiàn)[8-10]提出了使用值填充的方法解決數(shù)據(jù)不完整問題的Skyline查詢方法。文獻(xiàn)[7-10]對數(shù)據(jù)集進(jìn)行預(yù)處理，然后執(zhí)行Skyline算法。但預(yù)處理階段消耗系統(tǒng)資源過多，修復(fù)后的數(shù)據(jù)存在一定的誤差，導(dǎo)致查詢結(jié)果不準(zhǔn)確。針對海量不完整數(shù)據(jù)集，目前的查詢預(yù)處理代價(jià)較大，會顯著增加系統(tǒng)的響應(yīng)時(shí)間。

文獻(xiàn)[11]提出了在分布式環(huán)境下通過對Skyline點(diǎn)進(jìn)行抽樣，模擬高維Skyline數(shù)據(jù)集的算法SSRD （sampling Skylines by reduced dimensions）。首先隨機(jī)選擇出一個(gè)部分維度組合的數(shù)據(jù)集，然后在這個(gè)數(shù)據(jù)集上計(jì)算出Skyline點(diǎn)，作為近似的全局輪廓數(shù)據(jù)。這種方法只能查詢出數(shù)據(jù)集中的局部Skyline點(diǎn)，缺失大量的全局輪廓數(shù)據(jù)，因此不能反映全局的輪廓?；诟骶S數(shù)據(jù)綜合考慮的Skyline算法研究較少。

文獻(xiàn)[12]提出了一種基于不完整數(shù)據(jù)的Iskyline （incomplete data Skyline query）算法。該算法根據(jù)不完整數(shù)據(jù)缺失屬性將它們分到不同的缺失屬性列中，并動態(tài)查找局部和全局的Skyline點(diǎn)。該算法只適合少量不完整數(shù)據(jù)集，當(dāng)數(shù)據(jù)規(guī)模過大時(shí)查詢代價(jià)呈指數(shù)增長。該算法將不完整數(shù)據(jù)與完整數(shù)據(jù)分開查詢，沒有考慮兩者之間的支配關(guān)系，得到的結(jié)果存在較大誤差。

3　基于維度組合的數(shù)據(jù)集劃分

3.1構(gòu)建RankList數(shù)據(jù)結(jié)構(gòu)

當(dāng)數(shù)據(jù)量大且含有較多不完整數(shù)據(jù)，特別是維度也較高時(shí)，直接進(jìn)行Skyline查詢效率較低。為了提高查詢效率，并減少不完整數(shù)據(jù)對查詢結(jié)果的影響，本文引入了RankList數(shù)據(jù)結(jié)構(gòu)，將元組id有序存入結(jié)構(gòu)列表，在RankList結(jié)構(gòu)之上進(jìn)行查詢。

RankList數(shù)據(jù)結(jié)構(gòu)由多個(gè)列表組成，每個(gè)列表對應(yīng)不完整數(shù)據(jù)集的一維數(shù)據(jù)。每個(gè)列表di由數(shù)個(gè)桶Pmn組成，di維屬性值相同的元組放置同一個(gè)桶中，因此每一列中所含桶的數(shù)目與di維含有相異屬性值的多少有關(guān)。桶中元素值與元組在該維屬性值是否缺失有關(guān)，若某元組在該維屬性值缺失，則把“—”存入桶中，多個(gè)“—”出現(xiàn)時(shí)，只存儲一次，且放置于列表的末端。若某元組該維的屬性值不缺失，則存入該元組的id，把在該維屬性值相同的元組id號存放于一個(gè)桶中。某一列表的多個(gè)桶按照桶中元組在該維的屬性值升序排列，排序號用Ranki表示。

為了表明用戶對各個(gè)維度的偏好程度，本文對各個(gè)維度引入非負(fù)權(quán)值。為方便計(jì)算，設(shè)定權(quán)值越小的維度在查詢時(shí)越重要。RankList結(jié)構(gòu)中的列表按照各維度權(quán)值升序排列，重要的維度排在前面，便于提高Skyline點(diǎn)查詢效率。

用一個(gè)簡單的例子來說明RankList數(shù)據(jù)結(jié)構(gòu)。表1中不完整數(shù)據(jù)集C由9個(gè)三維元組構(gòu)成，其中“—”表示某元組在該維屬性值缺失。

設(shè)不完整數(shù)據(jù)集C的3個(gè)維度的權(quán)值分別為0.4、0.2和0.5，表2給出了數(shù)據(jù)集C對應(yīng)的RankList結(jié)構(gòu)。

Table 1 Example of incomplete data sets表1　不完整數(shù)據(jù)集實(shí)例

Table 2 RankList structure表2　構(gòu)建的RankList結(jié)構(gòu)

由于海量數(shù)據(jù)的數(shù)據(jù)量較大，在構(gòu)建RankList結(jié)構(gòu)時(shí)，將數(shù)據(jù)進(jìn)行分片排序，并行執(zhí)行排序算法[13]，提高構(gòu)建RankList結(jié)構(gòu)的效率。

3.2基于維度組合的空間劃分

Skyline查詢[14]是針對多維元組查詢的操作，元組之間的關(guān)系由是否“支配”來判定。

定義1（元組的支配關(guān)系[15]）元組tx支配元組ty(記為tx?ty)當(dāng)且僅當(dāng)在所有維度tx都不比ty差，且在至少一個(gè)維度tx比ty好，即?k，tx[k]≤ty[k]且?l, tx[l]< ty[l]。在元組屬性值越小越優(yōu)的情況下，顯然元組tx要優(yōu)于元組ty。

不被其他元組支配的元組為Skyline點(diǎn)，Skyline點(diǎn)構(gòu)成的集合即為Skyline查詢結(jié)果。

設(shè)數(shù)據(jù)維度集合為Q，集合W中任意元素都是集合Q的元素，則稱W為Q的維度子集。若某些元組在某個(gè)維度子集上不被支配，則這些元組中必含有Skyline點(diǎn)，故全局Skyline點(diǎn)可以通過維度子集漸進(jìn)式地查出。

定義2（空間劃分）數(shù)據(jù)集C由n維元組數(shù)據(jù)組成，用di代表元組的第i維，元組的維度{d1，d2，…，dn}構(gòu)成集合Q。若某個(gè)維度集合W中的任一元素屬于Q，則稱集合W為維度集合Q上的空間。

例如，某個(gè)數(shù)據(jù)集由{d1，d2，d3}三維構(gòu)成，有23-1個(gè)空間，如{d1}，{d2}，{d3}，{d1，d2}，{d1，d3}，{d2，d3}，{d1，d2，d3}。

定義3（空間關(guān)系）一般對于兩個(gè)空間A、B，如果空間A中的任意一個(gè)元素（維）都是空間B的元素，就說A、B有包含關(guān)系，稱空間A為空間B的子空間，記作A?B，同時(shí)也稱空間B為空間A的父空間?？臻gB的全部子空間構(gòu)成的集合記為Sub_ss(B)。

例如，空間A由維{d1}構(gòu)成，空間B由{d1，d2}構(gòu)成，則稱空間B為空間A的父空間，空間A為空間B的子空間。

空間編碼：數(shù)據(jù)集C中元組有n維，用di代表第i維。令空間W為維度集合Q的任一空間，編碼規(guī)則為，存在于空間W中的維dp（p∈[1,n]）用“1”代表，存在于維度集合Q但不存在于W中維dq（q∈[1,n]）用“0”代表。例如，某個(gè)數(shù)據(jù)集由{d1，d2，d3}三維構(gòu)成，子空間{d1，d3}用編號“101”表示。

3.3子空間最優(yōu)先點(diǎn)的獲取

定義4（優(yōu)先點(diǎn)）在數(shù)據(jù)集C中，任一元組xi各維的值在RankList結(jié)構(gòu)中的排序號Ranki（i∈[1,n]）的集合表示為{Ranki1,Ranki2，…，Rankin}。在任意m維空間中，對該m維上任意完整元組xi計(jì)算其Ranki集合，并求出該集合中最大排序號Pi，即Pi=max{Ranki1, Ranki2，…，Rankim}。然后，求出該m維空間所有元組的Pi最小值Pmin，即Pmin=min{P1,P2,…，Pn}，Pmin對應(yīng)的元組xj稱為優(yōu)先點(diǎn)，該空間的優(yōu)先點(diǎn)集合記為D。

以表2為例，查找{d2，d3}空間（空間編碼為“011”）的優(yōu)先點(diǎn)集。根據(jù)定義計(jì)算出“011”空間中各個(gè)元組的最大排序號：P1=max{Rank12，Rank13}= max{2,9}=9；同理，P2=4，P3=4，P4=5，P5=5，P6=6，P7= 5，P8=7。然后，求出該空間的Pi最小值：Pmin=min{P1，P2，P3，P4，P5，P6，P7，P8}={P2，P3}，即“011”空間的優(yōu)先點(diǎn)集為{x2，x3}。

由定義4的實(shí)例可知，“011”空間的優(yōu)先點(diǎn)集為{x2，x3}。計(jì)算：

由于6.9>4.6，故“011”空間的最優(yōu)先點(diǎn)為x3元組。

定理1最優(yōu)先點(diǎn)一定為Skyline點(diǎn)。

證明由元組支配關(guān)系的定義可知，Skyline點(diǎn)是不被其他點(diǎn)（元組）支配的點(diǎn)（元組）。從優(yōu)先點(diǎn)定義可知，優(yōu)先點(diǎn)集中可能存在一個(gè)點(diǎn)或多個(gè)點(diǎn)。下面針對這兩種情況，對“最優(yōu)先點(diǎn)一定為Skyline點(diǎn)”進(jìn)行證明。

當(dāng)某空間的優(yōu)先點(diǎn)集D中只有一個(gè)點(diǎn)時(shí)，根據(jù)最優(yōu)先點(diǎn)的定義可知，該點(diǎn)為最優(yōu)先點(diǎn)x。再根據(jù)優(yōu)先點(diǎn)的定義可知，優(yōu)先點(diǎn)集外的任意一點(diǎn)至少有一維屬性值大于x點(diǎn)對應(yīng)維的屬性值，即不存在支配x點(diǎn)的元組。因此，這個(gè)最優(yōu)先點(diǎn)x就是Skyline點(diǎn)。

以表2為例，查詢“011”空間及其子空間的最優(yōu)先點(diǎn)。根據(jù)定義4、定義5可得，“010”空間最優(yōu)先點(diǎn)為x7，“001”空間最優(yōu)先點(diǎn)為x6，“011”空間最優(yōu)先點(diǎn)為x3，其中x7為不完整元組。圖1中，白色點(diǎn)為非Skyline點(diǎn)，曲線上的點(diǎn)均為Skyline點(diǎn)，其中黑色點(diǎn)代表最優(yōu)先點(diǎn)，藍(lán)色點(diǎn)代表非最優(yōu)先點(diǎn)。從圖1可以看出這些最優(yōu)先點(diǎn)均勻地分布在Skyline點(diǎn)集中，在實(shí)際應(yīng)用中這些最優(yōu)先點(diǎn)漸進(jìn)地被查詢出來，既可以反映整體數(shù)據(jù)的輪廓，又可以提高查詢效率。

Fig.1 The highest priority points圖1　最優(yōu)先點(diǎn)的實(shí)例

4　基于空間劃分的Skyline查詢

針對海量不完整數(shù)據(jù)，CDskyline算法處理過程是首先構(gòu)建RankList結(jié)構(gòu)，并按序掃描RankList結(jié)構(gòu)中各個(gè)桶，基于空間劃分策略查詢出各個(gè)空間的最優(yōu)先點(diǎn)，得到最終的Skyline點(diǎn)集。

CDskyline算法的偽代碼如算法1所示。首先構(gòu)建RankList結(jié)構(gòu)，然后按序依次橫向掃描列表中各桶，調(diào)用算法2查詢桶內(nèi)是否有最優(yōu)先點(diǎn)，掃描各桶直到某桶的空間編號等于2n-1（n為元組的維數(shù)）為止。該桶之后不會再掃描到Skyline點(diǎn)，因?yàn)樵撏爸蟮狞c(diǎn)都能被該桶中的點(diǎn)支配。令MaxNo代表當(dāng)前空間最大編號。

算法1 CDskyline

輸入：海量不完整數(shù)據(jù)集

輸出：最優(yōu)先點(diǎn)集

1.根據(jù)數(shù)據(jù)集構(gòu)建RankList結(jié)構(gòu)

2. i=1，j=1;

3. While（MaxNo<2n-1）do

4.讀取RankList結(jié)構(gòu)中第i行、第j列的桶Pij；

5. Query(P);

6.更新i，j的值

7. end while

從最優(yōu)先點(diǎn)定義可知，最優(yōu)先點(diǎn)是空間中屬性綜合排序較靠前的元組，并且為Skyline點(diǎn)，在該空間具有較好的代表性。因此在對各個(gè)空間進(jìn)行查詢時(shí)，只需抽取出各個(gè)空間的最優(yōu)先點(diǎn)，即可獲得海量不完整數(shù)據(jù)的Skyline點(diǎn)。橫向掃描RankList結(jié)構(gòu)中桶Pij，并對桶Pij中元組映射的空間進(jìn)行編碼，根據(jù)定義4計(jì)算P桶中的點(diǎn)是否為該空間優(yōu)先點(diǎn)。若桶Pij中點(diǎn)的id為“—”，則跳過該桶不做處理。如果桶Pij中的點(diǎn)是空間優(yōu)先點(diǎn)，則根據(jù)定義5從這些優(yōu)先點(diǎn)中找到最優(yōu)先點(diǎn)，具體步驟詳見算法2。

算法2 Query(Pij)

輸入：桶Pij，Pij中包含元組（p1，p2，…，pn）

輸出：某空間的最優(yōu)先點(diǎn)

1. For (any point piin Pij) do

2. pi.No= Bitset(pi.No, j);

3. if (pi.No>MaxNo) then

4. MaxNo= pi.No;

5. end if

6. if (space[pi.No].state==False) then

7. space[pi.No].MaxValue== pi.Value;

8. space[pi.No].sp= pi;

9. Insert pi.No into NoList;

10. space[pi.No].state==true;

11. else

12. if (pi.No in NoList) then

13.if (pi.Value

14.space[pi.No].MaxValue==pi.Value;

15.space[pi.No].sp= pi;

16.end if

17. end if

18. end if

19. end for

20. for (any pi.No in NoList) do

21. if space[pi.No].sp has not been outputted then

22. Output space[pi.No].sp;

23. for (any q in Sub_ss(space[pi.No])) do

24.if (space[q].state==false) then

25.space[q].state=true;

26.end if

27.end for

28. end for

29. NoList = null;

令pi.No代表元組pi對應(yīng)的空間編號；置位函數(shù)Bitset(pi.No，j)用于修改元組pi對應(yīng)的子空間編號，其中j代表被掃描維；space[]代表空間；space[].sp代表空間的最優(yōu)先點(diǎn)；pi.value代表pi點(diǎn)各屬性值與權(quán)值乘積之和；space[].state代表空間狀態(tài)是否被掃描過；NoList代表桶中最優(yōu)先點(diǎn)映射的空間列表。

CDskyline算法通過橫向掃描RankList結(jié)構(gòu)中各個(gè)桶，漸進(jìn)式地從各個(gè)空間中查詢出最優(yōu)先點(diǎn)，從而得到查詢結(jié)果。以表2為例，簡要說明CDskyline算法查詢最優(yōu)先點(diǎn)的過程。

（1）掃描RankList結(jié)構(gòu)第一行第一列的桶，桶中的元組為x7，映射空間為“010”。根據(jù)算法2 Query()計(jì)算可知，x7元組為映射空間“010”的最優(yōu)先點(diǎn)，故輸出x7元組。

（2）掃描第一行第二列的桶，桶中元組為x3、x6，映射空間為“100”，x3元組的value值為4×0.4+5×0.2+ 4×0.5=4.6，同理得x6元組的value值為4.2，由于4.2 < 4.6，故x6元組為映射空間“100”的最優(yōu)先點(diǎn)，輸出x6元組點(diǎn)。

（3）掃描第一行第三列的桶，桶中的x6元組已經(jīng)是“100”空間的點(diǎn)，同時(shí)又映射“001”空間，故x6元組為空間“101”的最優(yōu)先點(diǎn)，同時(shí)修改其映射空間為“101”。由于x6元組已輸出，故不再輸出。此時(shí)遍歷“101”空間的子空間，對未掃描的001空間狀態(tài)置為true。

（4）按上述方法，依次掃描剩下的RankList結(jié)構(gòu)，直到找到空間“111”的最優(yōu)先點(diǎn)為止。

5　實(shí)驗(yàn)及結(jié)果分析

基于以上算法，本文設(shè)計(jì)了4個(gè)實(shí)驗(yàn)，從多個(gè)方面驗(yàn)證CDskyline算法的性能。實(shí)驗(yàn)主要關(guān)注以下幾個(gè)方面的性能表現(xiàn)：（1）當(dāng)維度從4維增加到16維時(shí)，各個(gè)算法響應(yīng)時(shí)間的對比；（2）當(dāng)維度從4維增加到16維時(shí)，各個(gè)算法結(jié)果集大小的對比；（3）數(shù)據(jù)集的大小對各個(gè)算法響應(yīng)時(shí)間的影響對比；（4）數(shù)據(jù)集缺失率對算法響應(yīng)時(shí)間的影響對比。

本實(shí)驗(yàn)的主機(jī)是一臺8 GB內(nèi)存，Intel Core i5-2400 3.10 GHz 4核CPU，臺式PC機(jī)。實(shí)驗(yàn)中每個(gè)維的數(shù)據(jù)由正態(tài)分布函數(shù)產(chǎn)生，元組隨機(jī)缺失其一維的數(shù)據(jù)生成實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)集中數(shù)據(jù)不完整率為10%。

5.1數(shù)據(jù)集的維度對響應(yīng)時(shí)間的影響分析

本實(shí)驗(yàn)在不同的數(shù)據(jù)維度下，對算法性能進(jìn)行分析。實(shí)驗(yàn)采用包含2×105條數(shù)據(jù)的數(shù)據(jù)集，維度的變化區(qū)間為[4,16]，每一維的值域?yàn)閇1,100]，各維的權(quán)值均取1。實(shí)驗(yàn)將CDskyline算法和Iskyline算法進(jìn)行對比，隨著維度增加各自響應(yīng)時(shí)間的情況如圖2所示。

Fig.2 Influence of dimensions on response time圖2　維度對響應(yīng)時(shí)間的影響

從圖2可以直觀地看出，CDskyline算法比Iskyline算法具有更高的執(zhí)行效率，并且隨著維數(shù)的增加，CDskyline算法比Iskyline算法的優(yōu)勢更加明顯。雖然CDskyline算法在高維時(shí)消耗的時(shí)間快速增長，但由于排序時(shí)間大致不變和子空間抽樣的原因，使其時(shí)間消耗增長的速度比其他算法的增長速度慢。

5.2數(shù)據(jù)集的維度對結(jié)果集大小的影響分析

本實(shí)驗(yàn)在不同的數(shù)據(jù)維度下，對算法結(jié)果集大小進(jìn)行分析。實(shí)驗(yàn)采用包含2×105條數(shù)據(jù)的數(shù)據(jù)集，維度的變化區(qū)間為[4,16]，各維的權(quán)值均取1，每維的值域?yàn)閇1,100]。實(shí)驗(yàn)將CDskyline算法和Iskyline算法進(jìn)行對比，隨著維度增加結(jié)果集數(shù)量的變化如圖3所示。

Fig.3 Influence of dimensions on result set圖3　維度對結(jié)果集的影響

從圖3可以直觀地看出，CDskyline算法比Iskyline算法的結(jié)果集小很多。由于CDskyline算法抽取的是屬性空間的最優(yōu)先點(diǎn)，故其抽取的Skyline點(diǎn)數(shù)不會超過2n（n為數(shù)據(jù)集的維數(shù)）個(gè)，從實(shí)驗(yàn)結(jié)果中已得到了驗(yàn)證。當(dāng)數(shù)據(jù)集的維度較高時(shí)，CDskyline算法能從各個(gè)維度組合中漸進(jìn)式地獲取用戶所需的Skyline點(diǎn)。由于兩種算法得到的結(jié)果集大小差異較大，圖3并不能詳盡地反映CDskyline算法的變化趨勢，該算法維度對結(jié)果集影響的詳盡情況如圖4所示。

Fig.4 Influence of dimensions on result set in CDskyline algorithm圖4　CDskyline算法維度對結(jié)果集的影響

5.3數(shù)據(jù)集的大小對響應(yīng)時(shí)間的影響分析

本實(shí)驗(yàn)分析數(shù)據(jù)集大小對算法響應(yīng)時(shí)間的影響。實(shí)驗(yàn)數(shù)據(jù)集的維度為10，各維的權(quán)值均取1，每維的值域?yàn)閇1,100]，數(shù)據(jù)集大小變化區(qū)間為2×105～ 10×105條數(shù)據(jù)。實(shí)驗(yàn)將CDskyline算法和Iskyline算法進(jìn)行對比，隨數(shù)據(jù)集增加兩種算法響應(yīng)時(shí)間的變化如圖5所示。

Fig.5 Influence of the size of dataset on response time圖5　數(shù)據(jù)集大小對響應(yīng)時(shí)間的影響

從圖5中可以看出，CDskyline算法所花費(fèi)的時(shí)間明顯低于Iskyline算法所需時(shí)間，最初CDskyline算法所用時(shí)間約為Iskyline算法的30%，但隨著數(shù)據(jù)集的增加，最終CDskyline算法所消耗時(shí)間約為Iskyline算法的20%。因?yàn)镽ankList結(jié)構(gòu)列表中桶的有序性，抽樣過程并沒有隨數(shù)據(jù)集的增加而消耗太多時(shí)間。但是由于需要對RankList結(jié)構(gòu)進(jìn)行排序和數(shù)據(jù)集的增加，CDskyline算法花費(fèi)時(shí)間還是增加的。

5.4數(shù)據(jù)集的缺失率對響應(yīng)時(shí)間的影響分析

本實(shí)驗(yàn)重點(diǎn)分析數(shù)據(jù)集缺失率對算法響應(yīng)時(shí)間的影響。實(shí)驗(yàn)數(shù)據(jù)集的維度為10，各維的權(quán)值均取1，每維的值域?yàn)閇1,100]，數(shù)據(jù)集大小變化區(qū)間為2× 105～10×105條數(shù)據(jù)。設(shè)數(shù)據(jù)集缺失率為10%和20%，圖6中用CDskyline_0.1與CDskyline_0.2表示。

Fig.6 Influence of missing data rate on response time圖6　數(shù)據(jù)數(shù)據(jù)確實(shí)率對響應(yīng)時(shí)間的影響

從圖6中可以看出，缺失率對響應(yīng)時(shí)間的影響不大。這是因?yàn)橥ㄟ^屬性值排序構(gòu)建RankList結(jié)構(gòu)時(shí)，若某元組缺少di維的屬性值，該元組在RankList結(jié)構(gòu)中di維的排序靠后。當(dāng)查詢各個(gè)子空間的最優(yōu)先點(diǎn)時(shí)，這些不完整數(shù)據(jù)對查詢的影響較小。

6　結(jié)束語

本文針對海量數(shù)據(jù)查詢中面臨的數(shù)據(jù)不完整、數(shù)據(jù)量大、維度較高等問題，提出了一種海量不完整數(shù)據(jù)上基于維度組合的Skyline查詢方法（CDskyline）。該方法深入分析了數(shù)據(jù)集的不同維度對查詢的影響，通過構(gòu)建RankList結(jié)構(gòu)和按維度組合劃分的子空間掃描查找策略，直接對海量不完整數(shù)據(jù)進(jìn)行查詢，減少了傳統(tǒng)數(shù)據(jù)處理中預(yù)處理帶來的查詢代價(jià)。該方法從各個(gè)子空間獲取最優(yōu)先點(diǎn)，從而漸進(jìn)地得到用戶所需的Skyline點(diǎn)。CDskyline適用于海量不完整數(shù)據(jù)的Skyline查詢，具有較高的查詢效率。

References:

[1] Li Jianzhong, Liu Xianmin. An important aspect of big data: data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147-1162.

[2] Cao Jianjun, Diao Xingchun, Chen Shuang, et al. Data cleaning and its general system framework[J]. Computer Science, 2012, 39(Z11): 207-211.

[3] Lin Yinhua, Zhang Chunhai, Liu Jie. Realization of data cleaning based on editing rules and master data[J]. Computer Science, 2012, 39(Z11): 174-176.

[4] Chen Wei, Ding Qiulin. Based on the data cleansing rules and master data restoration algorithm implementation[J]. Microcomputer & Its Applications, 2005, 24(2): 44-45.

[5] Wei Xiaojuan, Yang Jing, Li Cuiping, et al. Skyline query processing[J]. Journal of Software, 2008, 19(6): 1386-1400.

[6] Zhu Lin, Guan Jihong, Zhou Shuigeng. Skyline computation: survey[J]. Computer Engineering and Applications, 2008, 44(6): 160-165.

[7] Arefin M S, Morimoto Y. Skyline sets queries from databases with missing values[C]//Proceedings of the 22nd International Conference on Computer Theory and Applications, Alexandria, USA, Oct 13- 15, 2012. Piscataway, USA: IEEE, 2012: 24-29.

[8] Alwan A A, Ibrahim H, Udzir N I, et al. Skyline queries over incomplete multidimensional database[C]//Proceedings of the 3rd International Conference on Computing and Informatics, Bandung, Indonesia, Jun 8-9, 2011.

[9] Bu Fanyu, Chen Zhikui, Zhang Qingchen. Incomplete big data imputation algorithm based on deep learning[J]. Microelectronics & Computer, 2014, 31(12): 173-176.

[10] Chen Zhikui, Lv Ailing, Zhang Qingchen. A new algorithm for imputing missing data based on distinguishing the importance of attributes[J]. Microelectronics & Computer, 2013, 30(7): 167-172.

[11] Balke W T, Ountzer U, Zheng J X. Efficient distributed skylining for Web information systems[C]//Proceedings of the 9th International Conference on Extending Database Technology, Heraklion, Greece, Mar 14-18, 2004．Berlin, Heidelberg: Springer, 2004: 256-273.

[12] Khalefa M E, Mokbel M F, Levandoski J J. Skyline query processing for incomplete data[C]//Proceedings of the 24th International Conference on Data Engineering, Cancun, Mexico,Apr 7-12, 2008. Piscataway, USA: IEEE, 2008: 556-565.

[13] Wang Wenyi, Qiu Yong. A new algorthm for parallel merge sorting[J]. Computer Engineering and Applications, 2005, 41(5): 71-72.

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

[15] Xin Junchang, Bai Mei, Dong Han, et al. An efficient processing algorithm for ρ-dominant Skyline query[J]. Chinese Journal of Computers, 2011, 34(10): 1876-1884.

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

[1]李建中,劉顯敏.大數(shù)據(jù)的一個(gè)重要方面：數(shù)據(jù)可用性[J].計(jì)算機(jī)研究與發(fā)展, 2013, 50(6): 1147-1162.

[2]曹建軍,刁興春,陳爽,等.數(shù)據(jù)清洗及其一般性系統(tǒng)框架[J].計(jì)算機(jī)科學(xué), 2012, 39(Z11): 207-211.

[3]林印華,張春海,劉潔.基于清洗規(guī)則和主數(shù)據(jù)的數(shù)據(jù)修復(fù)算法實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué), 2012, 39(Z11): 174-176.

[4]陳偉,丁秋林.數(shù)據(jù)清理中不完整數(shù)據(jù)的清理方法[J].微型機(jī)與應(yīng)用, 2005, 24(2): 44-45.

[5]魏小娟,楊婧,李翠平,等. Skyline查詢處理[J].軟件學(xué)報(bào), 2008, 19(6): 1386-1400.

[6]朱琳,關(guān)佶紅,周水庚. Skyline計(jì)算研究綜述[J].計(jì)算機(jī)工程與應(yīng)用, 2008, 44(6): 160-165.

[9]卜范玉,陳志奎,張清辰.基于深度學(xué)習(xí)的不完整大數(shù)據(jù)填充算法[J].微電子學(xué)與計(jì)算機(jī), 2014, 31(12): 173-176.

[10]陳志奎,呂愛玲,張清辰.基于屬性重要性的不完備數(shù)據(jù)填充算法[J].微電子學(xué)與計(jì)算機(jī), 2013, 30(7): 167-172.

[13]王文義,邱涌.一種新的并行歸并排序算法[J].計(jì)算機(jī)工程與應(yīng)用, 2005, 41(5): 71-72.

[15]信俊昌,白梅,東韓,等.一種ρ-支配輪廓查詢的高效處理算法[J].計(jì)算機(jī)學(xué)報(bào), 2011, 34(10): 1876-1884.

WANG Yan was born in 1978. She is an associate professor at Liaoning University, Ph.D. candidate at Northeastern University, and the student member of CCF. Her research interests include massive data query technology, sensing data processing and big data management, etc.

王妍（1978—），女，遼寧撫順人，遼寧大學(xué)副教授，東北大學(xué)博士研究生，CCF學(xué)生會員，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)查詢技術(shù)，感知數(shù)據(jù)處理，大數(shù)據(jù)管理等。

YIN Biao was born in 1987. He is an M.S. candidate at Liaoning University, and the student member of CCF. His research interest is massive data query technology.

銀彪（1987—），男，河南漯河人，遼寧大學(xué)碩士研究生，CCF學(xué)生會員，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)查詢技術(shù)。

LIU Genghao was born in 1990. He is an M.S. candidate at Liaoning University, and the student member of CCF. His research interest is massive data query technology.

劉賡浩（1990—），男，遼寧大連人，遼寧大學(xué)碩士研究生，CCF學(xué)生會員，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)查詢技術(shù)。

SONG Baoyan was born in 1965. She received the Ph.D. degree in computer software and theory from Northeastern University in 2002. Now she is a professor at Liaoning University, and the senior member of CCF. Her research interests include database theory and techniques, RFID event stream processing techniques, big data management and graph data management, etc.

宋寶燕（1965—），女，遼寧開原人，2002年于東北大學(xué)計(jì)算機(jī)軟件與理論專業(yè)獲得博士學(xué)位，現(xiàn)為遼寧大學(xué)教授，CCF高級會員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論與技術(shù)，RFID事件流處理技術(shù)，大數(shù)據(jù)管理，圖數(shù)據(jù)管理技術(shù)等。

WANG Junlu was born in 1988. He received the M.S. degree from Liaoning University in 2014. Now he is an assistant engineer at Liaoning University, and the member of CCF. His research interests include database theory and techniques, big data processing techniques and massive data processing techniques, etc.

王俊陸（1988—），男，遼寧丹東人，2014年于遼寧大學(xué)獲得碩士學(xué)位，現(xiàn)為遼寧大學(xué)助理實(shí)驗(yàn)師，CCF會員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫理論與技術(shù)，大數(shù)據(jù)處理技術(shù)，海量數(shù)據(jù)處理技術(shù)等。

Skyline Query of Massive Incomplete Data Based on Combinational Dimensions?

WANG Yan1,2, YIN Biao1, LIU Genghao1, SONG Baoyan1+, WANG Junlu1
1. School of Information, Liaoning University, Shenyang 110036, China
2. School of Information Science and Engineering, Northeastern University, Shenyang 110819, China

+ Corresponding author: E-mail: bysong@lnu.edu.cn

WANG Yan, YIN Biao, LIU Genghao, et al. Skyline query of massive incomplete data based on combinational dimensions. Journal of Frontiers of Computer Science and Technology, 2016, 10(4): 495-503.

Abstract:With the rapid development of Internet, Internet of things and other information technology, and multidimensional data increasing, these massive data are often accompanied by a large number of incomplete data. So how to efficiently get the approximate result sets required by users from the massive incomplete data is an urgent problem to solve. This paper proposes a Skyline query algorithm for the massive high-dimensional incomplete data sets based on combination of dimensions. The algorithm constitutes RankList data structure to improve query efficiency and reduce the impact of incomplete data for query results, divides query subspaces by combining different dimensions, and incrementally checks out the highest priority point in the subspace, that is Skyline points uniformly distributed in the incomplete data set. The experimental results show that, compared with the Iskyline algorithm, the query efficiency of the proposed algorithm increases by 85% on average.And when the data are huge amount and high dimension, the algorithmbook=496,ebook=50shows higher query efficiency than the ordinary methods.

Key words:massive incomplete data; combinational dimensions; Skyline

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

中圖分類號：TP311.1

doi:10.3778/j.issn.1673-9418.1506045