海量不完整數據上基于維度組合的Skyline查詢*

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

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

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

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

?

海量不完整數據上基于維度組合的Skyline查詢*

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

1.遼寧大學信息學院，沈陽110036
2.東北大學信息與工程學院，沈陽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 (國家自然科學基金); the National Basic Research Program of China under Grant No. 2014CB360509 (國家重點基礎研究發展計劃(973計劃)); the National Science and Technology Support Program of China under Grant No. 2012BAF13B08 (國家科技支撐計劃); the Foundation of Science Public Welfare of Liaoning Province under Grant No. 2015003003 (遼寧省科學事業公益研究基金項目); the Youth Foundation of Liaoning University under Grant No. LDQN201508 (遼寧大學青年科研基金).

Received 2015-06,Accepted 2015-09.

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

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

關鍵詞：海量不完整數據；維度組合；Skyline

1　引言

隨著社會的飛速進步和科學技術水平的不斷提高，數據規模不斷擴大。數據通常具有多維的屬性值，且數據獲取的方式呈現多樣化，由于設備或其他原因導致元組數據缺失或其屬性值缺失的問題越來越普遍[1]。從海量不完整數據中，高效地獲取用戶所需的結果是一個亟需解決的問題。

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

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

2　相關工作

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

文獻[11]提出了在分布式環境下通過對Skyline點進行抽樣，模擬高維Skyline數據集的算法SSRD （sampling Skylines by reduced dimensions）。首先隨機選擇出一個部分維度組合的數據集，然后在這個數據集上計算出Skyline點，作為近似的全局輪廓數據。這種方法只能查詢出數據集中的局部Skyline點，缺失大量的全局輪廓數據，因此不能反映全局的輪廓。基于各維數據綜合考慮的Skyline算法研究較少。

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

3　基于維度組合的數據集劃分

3.1構建RankList數據結構

當數據量大且含有較多不完整數據，特別是維度也較高時，直接進行Skyline查詢效率較低。為了提高查詢效率，并減少不完整數據對查詢結果的影響，本文引入了RankList數據結構，將元組id有序存入結構列表，在RankList結構之上進行查詢。

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

為了表明用戶對各個維度的偏好程度，本文對各個維度引入非負權值。為方便計算，設定權值越小的維度在查詢時越重要。RankList結構中的列表按照各維度權值升序排列，重要的維度排在前面，便于提高Skyline點查詢效率。

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

設不完整數據集C的3個維度的權值分別為0.4、0.2和0.5，表2給出了數據集C對應的RankList結構。

Table 1 Example of incomplete data sets表1　不完整數據集實例

Table 2 RankList structure表2　構建的RankList結構

由于海量數據的數據量較大，在構建RankList結構時，將數據進行分片排序，并行執行排序算法[13]，提高構建RankList結構的效率。

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

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

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

不被其他元組支配的元組為Skyline點，Skyline點構成的集合即為Skyline查詢結果。

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

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

例如，某個數據集由{d1，d2，d3}三維構成，有23-1個空間，如{d1}，{d2}，{d3}，{d1，d2}，{d1，d3}，{d2，d3}，{d1，d2，d3}。

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

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

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

3.3子空間最優先點的獲取

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

以表2為例，查找{d2，d3}空間（空間編碼為“011”）的優先點集。根據定義計算出“011”空間中各個元組的最大排序號：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”空間的優先點集為{x2，x3}。

由定義4的實例可知，“011”空間的優先點集為{x2，x3}。計算：

由于6.9>4.6，故“011”空間的最優先點為x3元組。

定理1最優先點一定為Skyline點。

證明由元組支配關系的定義可知，Skyline點是不被其他點（元組）支配的點（元組）。從優先點定義可知，優先點集中可能存在一個點或多個點。下面針對這兩種情況，對“最優先點一定為Skyline點”進行證明。

當某空間的優先點集D中只有一個點時，根據最優先點的定義可知，該點為最優先點x。再根據優先點的定義可知，優先點集外的任意一點至少有一維屬性值大于x點對應維的屬性值，即不存在支配x點的元組。因此，這個最優先點x就是Skyline點。

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

Fig.1 The highest priority points圖1　最優先點的實例

4　基于空間劃分的Skyline查詢

針對海量不完整數據，CDskyline算法處理過程是首先構建RankList結構，并按序掃描RankList結構中各個桶，基于空間劃分策略查詢出各個空間的最優先點，得到最終的Skyline點集。

CDskyline算法的偽代碼如算法1所示。首先構建RankList結構，然后按序依次橫向掃描列表中各桶，調用算法2查詢桶內是否有最優先點，掃描各桶直到某桶的空間編號等于2n-1（n為元組的維數）為止。該桶之后不會再掃描到Skyline點，因為該桶之后的點都能被該桶中的點支配。令MaxNo代表當前空間最大編號。

算法1 CDskyline

輸入：海量不完整數據集

輸出：最優先點集

1.根據數據集構建RankList結構

2. i=1，j=1;

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

4.讀取RankList結構中第i行、第j列的桶Pij；

5. Query(P);

6.更新i，j的值

7. end while

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

算法2 Query(Pij)

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

輸出：某空間的最優先點

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對應的空間編號；置位函數Bitset(pi.No，j)用于修改元組pi對應的子空間編號，其中j代表被掃描維；space[]代表空間；space[].sp代表空間的最優先點；pi.value代表pi點各屬性值與權值乘積之和；space[].state代表空間狀態是否被掃描過；NoList代表桶中最優先點映射的空間列表。

CDskyline算法通過橫向掃描RankList結構中各個桶，漸進式地從各個空間中查詢出最優先點，從而得到查詢結果。以表2為例，簡要說明CDskyline算法查詢最優先點的過程。

（1）掃描RankList結構第一行第一列的桶，桶中的元組為x7，映射空間為“010”。根據算法2 Query()計算可知，x7元組為映射空間“010”的最優先點，故輸出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”的最優先點，輸出x6元組點。

（3）掃描第一行第三列的桶，桶中的x6元組已經是“100”空間的點，同時又映射“001”空間，故x6元組為空間“101”的最優先點，同時修改其映射空間為“101”。由于x6元組已輸出，故不再輸出。此時遍歷“101”空間的子空間，對未掃描的001空間狀態置為true。

（4）按上述方法，依次掃描剩下的RankList結構，直到找到空間“111”的最優先點為止。

5　實驗及結果分析

基于以上算法，本文設計了4個實驗，從多個方面驗證CDskyline算法的性能。實驗主要關注以下幾個方面的性能表現：（1）當維度從4維增加到16維時，各個算法響應時間的對比；（2）當維度從4維增加到16維時，各個算法結果集大小的對比；（3）數據集的大小對各個算法響應時間的影響對比；（4）數據集缺失率對算法響應時間的影響對比。

本實驗的主機是一臺8 GB內存，Intel Core i5-2400 3.10 GHz 4核CPU，臺式PC機。實驗中每個維的數據由正態分布函數產生，元組隨機缺失其一維的數據生成實驗數據，數據集中數據不完整率為10%。

5.1數據集的維度對響應時間的影響分析

本實驗在不同的數據維度下，對算法性能進行分析。實驗采用包含2×105條數據的數據集，維度的變化區間為[4,16]，每一維的值域為[1,100]，各維的權值均取1。實驗將CDskyline算法和Iskyline算法進行對比，隨著維度增加各自響應時間的情況如圖2所示。

Fig.2 Influence of dimensions on response time圖2　維度對響應時間的影響

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

5.2數據集的維度對結果集大小的影響分析

本實驗在不同的數據維度下，對算法結果集大小進行分析。實驗采用包含2×105條數據的數據集，維度的變化區間為[4,16]，各維的權值均取1，每維的值域為[1,100]。實驗將CDskyline算法和Iskyline算法進行對比，隨著維度增加結果集數量的變化如圖3所示。

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

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

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

5.3數據集的大小對響應時間的影響分析

本實驗分析數據集大小對算法響應時間的影響。實驗數據集的維度為10，各維的權值均取1，每維的值域為[1,100]，數據集大小變化區間為2×105～ 10×105條數據。實驗將CDskyline算法和Iskyline算法進行對比，隨數據集增加兩種算法響應時間的變化如圖5所示。

Fig.5 Influence of the size of dataset on response time圖5　數據集大小對響應時間的影響

從圖5中可以看出，CDskyline算法所花費的時間明顯低于Iskyline算法所需時間，最初CDskyline算法所用時間約為Iskyline算法的30%，但隨著數據集的增加，最終CDskyline算法所消耗時間約為Iskyline算法的20%。因為RankList結構列表中桶的有序性，抽樣過程并沒有隨數據集的增加而消耗太多時間。但是由于需要對RankList結構進行排序和數據集的增加，CDskyline算法花費時間還是增加的。

5.4數據集的缺失率對響應時間的影響分析

本實驗重點分析數據集缺失率對算法響應時間的影響。實驗數據集的維度為10，各維的權值均取1，每維的值域為[1,100]，數據集大小變化區間為2× 105～10×105條數據。設數據集缺失率為10%和20%，圖6中用CDskyline_0.1與CDskyline_0.2表示。

Fig.6 Influence of missing data rate on response time圖6　數據數據確實率對響應時間的影響

從圖6中可以看出，缺失率對響應時間的影響不大。這是因為通過屬性值排序構建RankList結構時，若某元組缺少di維的屬性值，該元組在RankList結構中di維的排序靠后。當查詢各個子空間的最優先點時，這些不完整數據對查詢的影響較小。

6　結束語

本文針對海量數據查詢中面臨的數據不完整、數據量大、維度較高等問題，提出了一種海量不完整數據上基于維度組合的Skyline查詢方法（CDskyline）。該方法深入分析了數據集的不同維度對查詢的影響，通過構建RankList結構和按維度組合劃分的子空間掃描查找策略，直接對海量不完整數據進行查詢，減少了傳統數據處理中預處理帶來的查詢代價。該方法從各個子空間獲取最優先點，從而漸進地得到用戶所需的Skyline點。CDskyline適用于海量不完整數據的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.

附中文參考文獻：

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

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

[3]林印華,張春海,劉潔.基于清洗規則和主數據的數據修復算法實現[J].計算機科學, 2012, 39(Z11): 174-176.

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

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

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

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

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

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

[15]信俊昌,白梅,東韓,等.一種ρ-支配輪廓查詢的高效處理算法[J].計算機學報, 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—），女，遼寧撫順人，遼寧大學副教授，東北大學博士研究生，CCF學生會員，主要研究領域為海量數據查詢技術，感知數據處理，大數據管理等。

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—），男，河南漯河人，遼寧大學碩士研究生，CCF學生會員，主要研究領域為海量數據查詢技術。

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—），男，遼寧大連人，遼寧大學碩士研究生，CCF學生會員，主要研究領域為海量數據查詢技術。

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年于東北大學計算機軟件與理論專業獲得博士學位，現為遼寧大學教授，CCF高級會員，主要研究領域為數據庫理論與技術，RFID事件流處理技術，大數據管理，圖數據管理技術等。

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年于遼寧大學獲得碩士學位，現為遼寧大學助理實驗師，CCF會員，主要研究領域為數據庫理論與技術，大數據處理技術，海量數據處理技術等。

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

文獻標志碼：A

中圖分類號：TP311.1

doi:10.3778/j.issn.1673-9418.1506045