王之瓊，霸建民，黃 達(dá)，信俊昌+

1.東北大學(xué) 中荷生物醫(yī)學(xué)與信息工程學(xué)院，沈陽(yáng) 110819

2.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819

數(shù)據(jù)流中ρ-支配輪廓查詢(xún)算法*

王之瓊1，霸建民2，黃 達(dá)2，信俊昌2+

1.東北大學(xué) 中荷生物醫(yī)學(xué)與信息工程學(xué)院，沈陽(yáng) 110819

2.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819

+Corresponding autho author:r:E-mail:xinjunchang@mail.neu.edu.cn

WANG Zhiqiong,BA Jianm in,HUANG Da,etal.ρ-dom inant skyline com putation on data stream s.Journal of Frontiersof Computer Scienceand Technology,2017,11(7)：1080-1091.

數(shù)據(jù)流上的輪廓查詢(xún)算法不能直接處理ρ-支配輪廓查詢(xún)，而傳統(tǒng)的ρ-支配輪廓查詢(xún)無(wú)法在數(shù)據(jù)更新頻繁時(shí)滿(mǎn)足查詢(xún)處理的實(shí)時(shí)性需求。因此，提出了數(shù)據(jù)流上的ρ-支配輪廓查詢(xún)算法。首先，系統(tǒng)地介紹了完全支配、ρ-支配和ρ-支配輪廓的定義，進(jìn)而提出了數(shù)據(jù)流上ρ-支配輪廓的定義。然后，通過(guò)深入分析數(shù)據(jù)流上的ρ-支配輪廓的性質(zhì)，得出基于時(shí)序支配的數(shù)據(jù)過(guò)濾方法，并提出了基于滑動(dòng)窗口的ρ-支配輪廓查詢(xún)算法（ρ-dominant skyline query over sliding w indow，DSSW），提高了數(shù)據(jù)流上的ρ-支配輪廓計(jì)算的效率。最后，通過(guò)大量的實(shí)驗(yàn)證明，DSSW算法相比較于傳統(tǒng)的ρ-支配輪廓查詢(xún)算法，在響應(yīng)時(shí)間及存儲(chǔ)空間上均有明顯優(yōu)勢(shì)。

ρ-支配關(guān)系；ρ-支配輪廓；數(shù)據(jù)流；滑動(dòng)窗口

1 引言

近年來(lái)，輪廓查詢(xún)[1-3]被廣泛地應(yīng)用于多標(biāo)準(zhǔn)決策中，例如個(gè)性化推薦系統(tǒng)、市場(chǎng)監(jiān)測(cè)系統(tǒng)等。給定一個(gè)數(shù)據(jù)點(diǎn)集合P，則數(shù)據(jù)集P的輪廓是指P中所有不被其他點(diǎn)支配的點(diǎn)的集合。需要指出的是一個(gè)點(diǎn)x支配另一個(gè)點(diǎn)y必須滿(mǎn)足x在所有維上都不比y差，并且至少在一維上x(chóng)比y好。不失一般性，假設(shè)一個(gè)小的值比大的值好，在d維數(shù)據(jù)空間內(nèi)，點(diǎn)x支配y可以表示為：（1）?i∈[1,d],x[i]≤y[i]；（2）?j∈[1,d],x[j]＜y[j]。圖1（a）中的點(diǎn)a、f和g由于不被其他任何點(diǎn)支配，就構(gòu)成了圖1（a）的輪廓。

Fig.1 Exampleof traditionalskylineand dynamic skyline圖1 傳統(tǒng)輪廓與動(dòng)態(tài)輪廓示例圖

動(dòng)態(tài)輪廓[4]為傳統(tǒng)輪廓的一種變體，致力于在查詢(xún)點(diǎn)的變換空間中計(jì)算輪廓。給定一個(gè)d維空間內(nèi)查詢(xún)點(diǎn)q，則對(duì)于任意一個(gè)d維數(shù)據(jù)p，都可以關(guān)于查詢(xún)點(diǎn)q變換為p′，并且p′滿(mǎn)足p′[i]=|p[i]-q[i]|+q[i],i∈[1,d]。圖1（b）是圖1（a）中以c為查詢(xún)點(diǎn)的動(dòng)態(tài)輪廓結(jié)果，因?yàn)辄c(diǎn)a′和g′在變換空間中不被其他任何點(diǎn)支配，所以點(diǎn)a′和g′構(gòu)成了此集合的動(dòng)態(tài)輪廓。動(dòng)態(tài)輪廓比傳統(tǒng)的輪廓有更廣泛的應(yīng)用，例如在一個(gè)電商平臺(tái)中，如果一個(gè)消費(fèi)者感興趣的商品已售空，則電商平臺(tái)可將與之類(lèi)似的商品推薦給消費(fèi)者。相當(dāng)于以已售空的商品作為查詢(xún)點(diǎn)，將動(dòng)態(tài)輪廓計(jì)算結(jié)果推薦給消費(fèi)者。

由于電商平臺(tái)的商品數(shù)量巨大，通過(guò)動(dòng)態(tài)輪廓查詢(xún)后，推薦給消費(fèi)者的商品數(shù)量仍然很多，無(wú)法幫助消費(fèi)者進(jìn)行選擇，可通過(guò)ρ-支配輪廓查詢(xún)解決，通過(guò)調(diào)節(jié)ρ值的大小完成對(duì)輪廓集大小的控制，從而實(shí)現(xiàn)向消費(fèi)者推薦其期望的商品數(shù)量。

然而，電商數(shù)據(jù)具有典型的數(shù)據(jù)流特點(diǎn)。傳統(tǒng)的ρ-支配輪廓查詢(xún)不能滿(mǎn)足具有無(wú)限性和實(shí)時(shí)性的數(shù)據(jù)流中的查詢(xún)需求，因而本文將研究數(shù)據(jù)流中的ρ-支配輪廓查詢(xún)來(lái)滿(mǎn)足此類(lèi)現(xiàn)實(shí)應(yīng)用。平臺(tái)中商品的更新是頻繁的，則很久以前的商品成為推薦商品的概率極小，因此可以只關(guān)注最近一段時(shí)間內(nèi)平臺(tái)中的商品。本文在基于append-only數(shù)據(jù)流的基礎(chǔ)上應(yīng)用滑動(dòng)窗口來(lái)研究數(shù)據(jù)流中的ρ-支配輪廓查詢(xún)算法。

首先，給出了完全支配關(guān)系、ρ-支配關(guān)系、ρ-支配輪廓和數(shù)據(jù)流上ρ-支配輪廓的定義。然后，深入地分析了數(shù)據(jù)流上ρ-支配輪廓的性質(zhì)，建立了基于時(shí)序支配的數(shù)據(jù)過(guò)濾方法，并據(jù)此提出了基于滑動(dòng)窗口的ρ-支配輪廓查詢(xún)算法（ρ-dom inant skyline query over sliding w indow，DSSW）。最后，通過(guò)實(shí)驗(yàn)證明DSSW算法提高了數(shù)據(jù)流上的ρ-支配輪廓計(jì)算的效率。

2 相關(guān)工作

2.1 輪廓查詢(xún)

一些學(xué)者針對(duì)非數(shù)據(jù)流上的輪廓查詢(xún)進(jìn)行了大量的研究工作。Borzsonyi等人[1]提出了嵌套循環(huán)算法，將某個(gè)元組p與其他元組逐一比較，如果p不被任意其他元組支配，則p是輪廓點(diǎn)，并使用輪廓操作去擴(kuò)展數(shù)據(jù)庫(kù)系統(tǒng)；Papadias等人[2]提出了基于最近搜索的BBS（branch-and-bound skyline）算法，此算法僅僅對(duì)可能包含輪廓點(diǎn)的R樹(shù)節(jié)點(diǎn)執(zhí)行一次存取并且不進(jìn)行重復(fù)檢索，另外此算法還可以有效地應(yīng)用于各種變體輪廓查詢(xún)中；Chen等人[3]提出了定義在動(dòng)態(tài)空間中的動(dòng)態(tài)輪廓查詢(xún)，通過(guò)動(dòng)態(tài)索引給出了一種有效的剪枝技術(shù)去計(jì)算動(dòng)態(tài)輪廓，并且論證了剪枝后動(dòng)態(tài)輪廓查詢(xún)的性能；Chan等人[4]提出了考慮不同維度時(shí)多久返回輪廓結(jié)果的頻率輪廓查詢(xún)，并應(yīng)用找出top-k頻率的輪廓點(diǎn)給出了一種計(jì)算方法；Yiu等人[5]應(yīng)用多維數(shù)據(jù)索引和深入探究top-k支配的特點(diǎn)給出了一種計(jì)算top-k輪廓的算法；Chen等人[6]通過(guò)大量的無(wú)組織的分布式環(huán)境研究了約束輪廓，首先利用一種分割算法將所有的數(shù)據(jù)分割為一些群組以便可以并發(fā)處理這些數(shù)據(jù)，然后提出了一個(gè)并行處理算法。

也有學(xué)者針對(duì)數(shù)據(jù)流上的輪廓查詢(xún)開(kāi)展了一些研究工作。Kossmann等人[7]第一次提出了持續(xù)的輪廓查詢(xún)算法，首先立刻返回一組輪廓，然后持續(xù)不斷地返回多組輪廓并且允許使用者控制計(jì)算時(shí)間；Lin等人[8]第一次提出了在最近N組數(shù)據(jù)中計(jì)算輪廓的n-of-N輪廓查詢(xún)，提出了一種剪枝技術(shù)和一種高效數(shù)據(jù)存取技術(shù)，并且提出了一種持續(xù)計(jì)算n-of-N輪廓的算法；Zhang等人[9]分析了需要保存數(shù)據(jù)的特點(diǎn)和輪廓集合的大小，提出了不確定數(shù)據(jù)流上的輪廓查詢(xún)算法；Ding等人[10]研究了不確定數(shù)據(jù)流上的輪廓查詢(xún)問(wèn)題；Yang等人[11]提出了DC-Tree算法去計(jì)算數(shù)據(jù)流上的輪廓查詢(xún)；Zhu等人[12]提出了以DC-tree作為索引的反輪廓查詢(xún)算法，并且應(yīng)用剪枝技術(shù)縮減了查找空間的大小；Bai等人[13]提出了不確定數(shù)據(jù)流上概率反輪廓查詢(xún)的定義以及索引模型，并且提出了一種基于R-tree的不確定數(shù)據(jù)流上的反輪廓查詢(xún)算法（probabilistic reverse skyline on uncertain data streams based on R-tree index，RT2RS）；Dellis等人[14]采用多個(gè)低維索引來(lái)支持任意子空間的限制性輪廓查詢(xún)；Morse等人[15]提出了LookOut算法來(lái)計(jì)算連續(xù)時(shí)間間隔的輪廓查詢(xún)。

2.2 ρ-支配輪廓查詢(xún)

2011年，Xin等人[16]首先提出了基于數(shù)值間比例值大小的ρ-支配關(guān)系和ρ-支配輪廓查詢(xún)的概念，并建立了一種應(yīng)用于傳統(tǒng)數(shù)據(jù)集上的基于分支定界的ρ-支配輪廓查詢(xún)算法（branch and boundρ-dominant skyline algorithm，BBDS）。BBDS算法采用標(biāo)準(zhǔn)的R樹(shù)索引存儲(chǔ)數(shù)據(jù)，并將所有數(shù)據(jù)分為兩類(lèi)：ρ-支配輪廓集合S和非ρ-支配輪廓集合SS，初始時(shí)兩集合均為空。采用廣度優(yōu)先遍歷算法遍歷R樹(shù)中的節(jié)點(diǎn)e，如果e是中間節(jié)點(diǎn)，判斷e是否被S+SS中的兩個(gè)數(shù)據(jù)支配；若不被兩個(gè)數(shù)據(jù)支配，則遍歷所有不被兩個(gè)元素支配的子節(jié)點(diǎn)。如果e是葉子節(jié)點(diǎn)，判斷e是否被S+SS中的數(shù)據(jù)支配，如果不被支配，繼續(xù)判斷是否被S+SS中的數(shù)據(jù)ρ-支配，若不被ρ-支配則將e加入到S中，否則將e加入到SS中；接著將S中被eρ-支配的集合加入到SS中。

但是在數(shù)據(jù)流中，若每當(dāng)有數(shù)據(jù)更新時(shí)便先維護(hù)R樹(shù)，再調(diào)用BBDS算法，必將花費(fèi)大量的時(shí)間和空間代價(jià)?？傊?，傳統(tǒng)的ρ-支配輪廓查詢(xún)無(wú)法在數(shù)據(jù)更新頻繁時(shí)滿(mǎn)足查詢(xún)處理的實(shí)時(shí)性需求，而數(shù)據(jù)流上的輪廓查詢(xún)不能滿(mǎn)足數(shù)值間比例關(guān)系的輪廓查詢(xún)。因此，本文將深入研究數(shù)據(jù)流中的ρ-支配輪廓查詢(xún)問(wèn)題。

3 問(wèn)題描述

首先回顧完全支配關(guān)系和ρ-支配關(guān)系[16]的定義。

定義1（完全支配）一個(gè)點(diǎn)x關(guān)于查詢(xún)點(diǎn)q完全支配另一個(gè)點(diǎn)y(x?qy)當(dāng)且僅當(dāng)：（1）?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧|x[i]-q[i]|≤|y[i]-q[i]|；（2）?j∈[1,d],(x[j]-q[j])(y[j]-q[j])＞0 ∧ |x[j]-q[j]|＜ |y[j]-q[j]|。

定義2（ρ-支配）一個(gè)點(diǎn)x關(guān)于查詢(xún)點(diǎn)qρ-支配另一個(gè)點(diǎn)當(dāng)且僅當(dāng)：（1）?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧|x[i]-q[i]|≤ρ×|y[i]-q[i]|；（2）?j∈[1,d],(x[j]-q[j])(y[j]-q[j])＞0∧|x[j]-q[j]|＜ρ×|y[j]-q[j]|。

圖2（a）顯示了二維空間中完全支配的一個(gè)例子。因?yàn)閷?duì)任意一維b和q之間的距離比a和q之間的距離短，并且a、b在q的同一側(cè)，所以點(diǎn)b關(guān)于查詢(xún)點(diǎn)q完全支配點(diǎn)a。同理，點(diǎn)h關(guān)于查詢(xún)點(diǎn)q完全支配點(diǎn)g。而點(diǎn)b、c、d、e、f和點(diǎn)h不被其他任一點(diǎn)完全支配。

Fig.2 Example of full-dom inance andρ-dom inance圖2 完全支配和ρ-支配示例圖

圖2（b）展示了當(dāng)ρ取值為1.5時(shí)的ρ-支配關(guān)系的例子，在本例中使用x′表示x與q的1/3分位點(diǎn)。因?yàn)閷?duì)任意一維點(diǎn)b′和點(diǎn)q之間的距離比點(diǎn)a和點(diǎn)q之間的距離小，并且b′和a在點(diǎn)q的同一側(cè)，所以點(diǎn)b關(guān)于查詢(xún)點(diǎn)q1.5-支配點(diǎn)a。同理可得，點(diǎn)f關(guān)于查詢(xún)點(diǎn)q1.5-支配點(diǎn)e，并且點(diǎn)e關(guān)于查詢(xún)點(diǎn)q1.5-支配點(diǎn)f，點(diǎn)h關(guān)于查詢(xún)點(diǎn)q1.5-支配點(diǎn)g。而點(diǎn)b、c、d和h不被其他任意點(diǎn)1.5-支配。

由完全支配關(guān)系和ρ-支配關(guān)系可以容易地得出完全支配輪廓和ρ-支配輪廓[16]的定義，如定義3和定義4所示。

定義3（完全支配輪廓）給定一個(gè)數(shù)據(jù)集合P和一個(gè)查詢(xún)點(diǎn)q，數(shù)據(jù)集P中所有不被P中其他點(diǎn)關(guān)于點(diǎn)q完全支配的點(diǎn)構(gòu)成數(shù)據(jù)集P的完全支配輪廓。

定義4（ρ-支配輪廓）給定一個(gè)數(shù)據(jù)集合P和一個(gè)查詢(xún)點(diǎn)q，數(shù)據(jù)集P中所有不被P中其他點(diǎn)關(guān)于點(diǎn)qρ-支配的點(diǎn)構(gòu)成數(shù)據(jù)集P的ρ-支配輪廓。

根據(jù)定義3可得，如果一個(gè)點(diǎn)p不被數(shù)據(jù)集中其他任一點(diǎn)關(guān)于查詢(xún)點(diǎn)q完全支配，則點(diǎn)p為一個(gè)完全支配輪廓點(diǎn)。如圖2（a）所示，點(diǎn)b、c、d、e、f和h不被其他任意點(diǎn)完全支配，因此點(diǎn)b、c、d、e、f和h構(gòu)成了圖2（a）的完全支配輪廓。同理可以得出點(diǎn)b、c、d和h組成圖2（b）的1.5-支配輪廓。

根據(jù)定義3和定義4可以容易地看出完全支配輪廓是ρ-支配輪廓中ρ取值為1時(shí)的特例。

類(lèi)似ρ-支配輪廓，可以得出數(shù)據(jù)流上的ρ-支配輪廓的定義。用PN表示數(shù)據(jù)流中最近的N組數(shù)據(jù)，即滑動(dòng)窗口中的數(shù)據(jù)，并且用L(p)表示點(diǎn)p在數(shù)據(jù)流中的位置，L(p)大的點(diǎn)表示后到，數(shù)據(jù)流中的ρ-支配輪廓如定義5所示。

定義5（數(shù)據(jù)流中的ρ-支配輪廓）給定一個(gè)數(shù)據(jù)流P和一個(gè)查詢(xún)點(diǎn)q，則數(shù)據(jù)流上PN中不被其他任一點(diǎn)ρ-支配的點(diǎn)構(gòu)成數(shù)據(jù)流P的ρ-支配輪廓。

4 數(shù)據(jù)流中的ρ-支配輪廓查詢(xún)

本文將詳細(xì)介紹DSSW算法，首先深入分析數(shù)據(jù)流上的ρ-支配輪廓的性質(zhì)；接著根據(jù)數(shù)據(jù)流上ρ-支配輪廓的性質(zhì)建立數(shù)據(jù)過(guò)濾方法；最后詳細(xì)地給出DSSW算法的具體過(guò)程。

4.1 ρ-支配輪廓的性質(zhì)

當(dāng)ρ小于等于1時(shí)，ρ-支配關(guān)系滿(mǎn)足傳遞性，因此ρ小于等于1時(shí)的ρ-支配輪廓可以采用類(lèi)似于輪廓查詢(xún)的方式來(lái)計(jì)算，故本文只討論ρ大于1時(shí)的情況。

如圖2（a）和圖2（b）所示，對(duì)于同一個(gè)數(shù)據(jù)集合P，完全支配輪廓包含點(diǎn)b、c、d、e、f和h，而1.5-支配輪廓包含點(diǎn)b、c、d和h，從中可以容易地看出完全支配輪廓點(diǎn)包含1.5-支配輪廓點(diǎn)。此結(jié)論更一般的表達(dá)如定理1所示。

定理1給定兩個(gè)值ρ1和ρ2，并且ρ1＞ρ2，如果一個(gè)點(diǎn) p是 ρ1-支配輪廓點(diǎn)，那么 p一定也是 ρ2-支配輪廓點(diǎn)。

證明采用反證法。假設(shè)點(diǎn)p不是 ρ2-支配輪廓點(diǎn)，則存在另一點(diǎn)xρ2-支配點(diǎn) p，根據(jù)定義2可得?i∈[1,d],(x[i]-q[i])(p[i]-q[i])≥0∧|x[i]-q[i]|≤ρ2×|p[i]-q[i]|并且 ?j∈[1,d],(x[j]-q[j])(p[j]-q[j])＞0∧|x[j]-q[j]|＜ρ2×|p[j]-q[j]|。又因?yàn)棣?＞ρ2,則?i∈[1,d],(x[i]-q[i])(p[i]-q[i])≥ 0 ∧|x[i]-q[i]|≤ ρ1×|p[i]-q[i]|和?j∈[1,d],(x[j]-q[j])(p[j]-q[j])＞0∧|x[j]-q[j]|＜ρ1×|p[j]-q[j]|，即點(diǎn) x ρ1-支配點(diǎn) p，與已知條件不符，所以點(diǎn) p一定是 ρ2-支配輪廓點(diǎn)。 □

由定理1可以看出，通過(guò)調(diào)節(jié)ρ值的大小可以控制結(jié)果集的大小，因此 ρ-支配輪廓查詢(xún)有更廣泛的應(yīng)用。

定理2給定兩個(gè)點(diǎn)x和y，如果 ρ＞1并且x?qy，則

證明根據(jù)定義1，由 x?qy可得?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧|x[i]-q[i]|≤|y[i]-q[i]|并且 ?j∈[1,d],(x[j]-q[j])(y[j]-q[j])＞0∧|x[j]-q[j]|＜|y[j]-q[j]|。又因?yàn)?ρ＞1，則?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧|x[i]-q[i]|≤ρ×|y[i]-q[i]|并 且 ?j∈[1,d],(x[j]-q[j])(y[j]-q[j])＞0∧|x[j]-q[j]|＜ρ×|y[j]-q[j]|，由定義2可得

由定理2可以看出，如果一個(gè)點(diǎn)x被另一個(gè)點(diǎn)y完全支配，那么當(dāng) ρ＞1時(shí)點(diǎn)x也被點(diǎn)yρ-支配。由定理2的證明過(guò)程可以容易地得出反之不成立。

定理3給定數(shù)據(jù)流中的兩個(gè)點(diǎn)x和y，如果并且L(x)＞L(y)，則點(diǎn)y不可能成為 ρ-支配輪廓點(diǎn)。

證明因?yàn)?，所以?dāng)x屬于PN時(shí)點(diǎn)y不是ρ-支配輪廓點(diǎn)。又由于在數(shù)據(jù)流中L(x)＞L(y)，則在PN中y比x先消失，從而y不可能成為一個(gè) ρ-支配輪廓點(diǎn)。 □

引理1給定數(shù)據(jù)流中的兩個(gè)點(diǎn)x和y，如果x?qy并且L(x)＞L(y)，則點(diǎn)y不可能成為 ρ-支配輪廓點(diǎn)。

由定理2和定理3可以容易地證出引理1。

定理4如果x?qy和，那么

證明由于x?qy和，根據(jù)定義1可得?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧|x[i]-q[i]|≤ |y[i]-q[i]|，根據(jù)定義2可得 ?i∈[1,d],(y[i]-q[i])(z[i]-q[i])≥0∧|y[i]-q[i]|≤ρ×|z[i]-q[i]|，則通過(guò)兩式分別相乘得 ?i∈[1,d],(x[i]-q[i])(z[i]-q[i])≥0∧|x[i]-q[i]|≤ρ×|z[i]-q[i]|。同理可得 ?j∈[1,d],(x[j]-q[j])(z[j]-q[j])＞0∧|x[j]-q[j]|＜ρ×|z[j]-q[j]|，因此。 □

一個(gè)點(diǎn)p可能同時(shí)被PN中多個(gè)點(diǎn)ρ-支配，并且PN中只要存在一個(gè) ρ-支配點(diǎn) p的點(diǎn)，點(diǎn) p就不是 ρ-支配輪廓點(diǎn)，因此點(diǎn) p是否是 ρ-支配輪廓點(diǎn)將由 ρ-支配它的點(diǎn)中最后一個(gè)到達(dá)的點(diǎn)n是否存在于PN中所決定，并且將點(diǎn)n記為 pre(p)。

4.2 過(guò)濾方法

考慮圖3中的例子，其中點(diǎn)按照它們的字母表順序依次到達(dá)，并且 ρ值為2。假設(shè)點(diǎn)c剛剛到達(dá)滑動(dòng)窗口，并且滑動(dòng)窗口的大小大于3，因?yàn)辄c(diǎn)a被點(diǎn)b2-支配，所以點(diǎn)a不可能成為ρ-支配輪廓點(diǎn)，但是如果將a過(guò)濾掉，因?yàn)辄c(diǎn)b不能 ρ-支配點(diǎn)c，所以點(diǎn)c將被判斷為 ρ-支配輪廓點(diǎn)。然而，從圖3中可以看出點(diǎn)aρ-支配點(diǎn)c，因此點(diǎn)c不是 ρ-支配輪廓點(diǎn)，不能直接將不可能成為ρ-支配輪廓點(diǎn)的點(diǎn)過(guò)濾掉。

Fig.3 Counterexampleof filtering圖3 過(guò)濾的反例

如果一個(gè)點(diǎn)y被另一個(gè)后到的點(diǎn)x完全支配，根據(jù)定理4可得，則被點(diǎn)yρ-支配的點(diǎn)也被點(diǎn)xρ-支配，因此當(dāng)刪除點(diǎn)y時(shí)，如果有新的被點(diǎn)yρ-支配的點(diǎn)z到達(dá)時(shí)，點(diǎn)z必將被點(diǎn)xρ-支配，從而不會(huì)影響點(diǎn)z是否成為 ρ-支配輪廓點(diǎn)；又根據(jù)引理1可得，點(diǎn)y不可能成為一個(gè)ρ-支配輪廓點(diǎn)，因此在輪廓計(jì)算前可以過(guò)濾掉被后到的點(diǎn)完全支配的點(diǎn)。

用SN表示PN中過(guò)濾后的點(diǎn)的集合，則SN={p|p∈PN,?/p′∈PN,L(p′)＞L(p)∧p′?qp}。進(jìn)一步可以將SN劃分為3類(lèi)：

（1）ρ-支配輪廓點(diǎn)(DN)，SN中不被其他任何點(diǎn)ρ-支配的點(diǎn)的集合；

（2）候選點(diǎn)(CN)，SN中被先到的點(diǎn)ρ-支配而不被后到的點(diǎn)ρ-支配的點(diǎn)的集合；

（3）輔助點(diǎn)(AN)，SN中被后到的點(diǎn)ρ-支配而不被后到的點(diǎn)完全支配的點(diǎn)的集合。

繼續(xù)考慮圖2（b）的例子，假設(shè)滑動(dòng)窗口的大小不小于8，并且點(diǎn)按照字母表順序到達(dá)。因?yàn)辄c(diǎn)a和g分別被b和h完全支配，所以計(jì)算前過(guò)濾掉a和g，從而SN={b,c,d,e,f,h}；因?yàn)辄c(diǎn)b、c、d和h不被其他任一點(diǎn)ρ-支配，所以ρ-支配輪廓DN={b,c,d,h}；因?yàn)辄c(diǎn)f被一個(gè)先到的點(diǎn)eρ-支配而不被后到的點(diǎn)ρ-支配，所以候選點(diǎn)CN={f}；因?yàn)辄c(diǎn)e被一個(gè)后到的點(diǎn)ρ-支配而不被后到的點(diǎn)完全支配，所以輔助點(diǎn)AN={e}。

至此，已經(jīng)建立了數(shù)據(jù)流中ρ-支配輪廓查詢(xún)的過(guò)濾方法。根據(jù)點(diǎn)集合的劃分方式可知一個(gè)新到達(dá)的點(diǎn)要么屬于DN，要么屬于CN。由過(guò)濾方法可得SN為計(jì)算ρ-支配輪廓所需要存儲(chǔ)的最小數(shù)據(jù)集合。

4.3 查詢(xún)過(guò)程

由定義1和定義2可以得出，完全支配關(guān)系和ρ-支配關(guān)系只能存在于查詢(xún)點(diǎn)同一側(cè)區(qū)域中的兩個(gè)點(diǎn)之間，因此當(dāng)滑動(dòng)窗口中一個(gè)新的點(diǎn)到達(dá)時(shí)只需判斷該點(diǎn)同一區(qū)域內(nèi)的點(diǎn)與該點(diǎn)的支配關(guān)系（如果一個(gè)點(diǎn)與查詢(xún)點(diǎn)在某幾維上相同，則該點(diǎn)屬于多個(gè)區(qū)域）。在Xin等人[16]的算法中采用了R樹(shù)索引存儲(chǔ)方式，將SN中數(shù)據(jù)分配到2d個(gè)區(qū)域進(jìn)行存儲(chǔ)。

盡管傳統(tǒng)的R樹(shù)索引存儲(chǔ)可以大大減少數(shù)據(jù)查找的時(shí)間消耗，但是當(dāng)數(shù)據(jù)流中的數(shù)據(jù)更新時(shí)，刪除和插入等操作將花費(fèi)大量的維護(hù)時(shí)間，降低了算法的時(shí)間效率。本文將使用2d個(gè)Map容器對(duì)SN中的數(shù)據(jù)進(jìn)行存儲(chǔ)，當(dāng)有新的數(shù)據(jù)更新時(shí)只需計(jì)算該數(shù)據(jù)所屬的區(qū)域R()并存儲(chǔ)即可。此方法既加快了數(shù)據(jù)查找時(shí)的效率，又省去了當(dāng)數(shù)據(jù)更新時(shí)維護(hù)R樹(shù)所需的時(shí)間。

算法1描述了DSSW算法的具體查詢(xún)過(guò)程。當(dāng)n個(gè)新的點(diǎn)p1-pn到達(dá)時(shí)，如果滑動(dòng)窗口已滿(mǎn)，則查找滑動(dòng)窗口中最先到達(dá)的n個(gè)點(diǎn)o1-on，并計(jì)算點(diǎn)所屬的區(qū)域R()，然后將點(diǎn)o1-on在相應(yīng)的R()中刪除，并且在CN中查找被o1-on中的點(diǎn)ρ-支配的點(diǎn)的集合DC，將DC中的點(diǎn)從CN中轉(zhuǎn)移到DN中；計(jì)算出點(diǎn)p1-pn所屬的區(qū)域R()，并根據(jù)R()將p1-pn分成k組；對(duì)于k組中的每一組，在區(qū)域R()中查找被p1-pn中的點(diǎn)完全支配的點(diǎn)的集合DF，并且將這些點(diǎn)在PN中刪除，然后在R()中查找被p1-pn中的點(diǎn)ρ-支配的點(diǎn)的集合DS，并且將DS中的點(diǎn)從DN和CN中移到AN；如果在區(qū)域R(pi)中存在點(diǎn)zρ-支配點(diǎn)pi，將點(diǎn)pi加入到CN中，否則將點(diǎn)pi加入到DN中；最后將點(diǎn)pi存儲(chǔ)到區(qū)域R(pi)中。

算法1DSSW算法

1.while（新的n個(gè)點(diǎn)p1-pn到達(dá)）

2.if（滑動(dòng)窗口已滿(mǎn)）

3.查找最先進(jìn)入窗口的n個(gè)點(diǎn)o1-on

4.分別計(jì)算點(diǎn)o1-on的區(qū)域R()

5.將o1-on分別在所在的區(qū)域R()中刪除

6.在CN中查找以o1-on中的點(diǎn)為pre()的集合DC

7.將DC從CN移動(dòng)到DN

8.計(jì)算點(diǎn)p1-pn的區(qū)域R()

9.將p1-pn按照所在的區(qū)域R()分成k組

10.for（k組中的每一組）

11.在本區(qū)域R()中查找被p1-pn中的點(diǎn)完全支配的集合DF

12.將DF中的點(diǎn)過(guò)濾掉

13.在本區(qū)域R()中查找被點(diǎn)p1-pn中的點(diǎn)ρ-支配的集合DS

14.將DS中的點(diǎn)從DN和CN移動(dòng)到AN

15. for（p從p1-pn）

16. if（存在點(diǎn)z為pre(p)）

17.pre(p)=L(z)

18.將點(diǎn)p加入集合CN

19. else

20.將點(diǎn)p加入集合DN

21.將點(diǎn)p存儲(chǔ)到相應(yīng)的R(p)中

算法2描述了點(diǎn)p所屬區(qū)域的計(jì)算過(guò)程。在此過(guò)程中，假設(shè)點(diǎn)p和查詢(xún)點(diǎn)q都是d維。如果在第一維中點(diǎn)p大于點(diǎn)q，則將1放入R(p)容器中，如果在第一維點(diǎn)p小于點(diǎn)q，則將0放入R(p)容器中，否則將0和1同時(shí)放入R(p)容器中；然后從第二維到第d維遍歷p和q中的數(shù)據(jù)，假設(shè)遍歷到第i維，如果在第i維點(diǎn)p大于點(diǎn)q，則將容器R(p)中的每個(gè)數(shù)與2左移i-1位相加，如果點(diǎn)p等于點(diǎn)q，則將R(p)容器中的數(shù)與2左移i-1位相加，并放入R(p)容器中，且R(p)容器中的原數(shù)據(jù)不變。需要注意的是如果點(diǎn)p和點(diǎn)q在某些維上的值相同，將得到多個(gè)區(qū)域，那么每個(gè)區(qū)域都需要進(jìn)行處理。

算法2計(jì)算點(diǎn)p的區(qū)域號(hào)

input:任意d維數(shù)據(jù)p和查詢(xún)點(diǎn)q

output:點(diǎn)p的區(qū)域號(hào)R(p)

1.定義整型容器R(p)

2.if(p[0]＞q[0])

3.將1加入R(p)

4.else if(p[0]=q[0])

5.將1和0加入R(p)

6.else

7.將0加入R(p)

8.for(i=1;i＜ =d;i++)//表示遍歷第i維

9. if(p[i]＞q[i])

10.將R(p)中的數(shù)據(jù)都加上2＜＜(i+1)

11. else if(p[i]=q[i])

12.將R(p)中數(shù)據(jù)加上2＜＜(i+1)放入R(p)

13.returnR(p)

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

本文系統(tǒng)地測(cè)試了擴(kuò)展的BBDS算法[16]和DSSW算法在ρ值、滑動(dòng)窗口大小、滑動(dòng)因子和數(shù)據(jù)維度變化時(shí)的性能。性能評(píng)估指標(biāo)包括響應(yīng)時(shí)間和滑動(dòng)窗口中的數(shù)據(jù)量，顯然響應(yīng)時(shí)間越短，滑動(dòng)窗口中保留的數(shù)據(jù)量越小，在響應(yīng)時(shí)間及存儲(chǔ)空間上的優(yōu)勢(shì)越明顯。所有算法均采用標(biāo)準(zhǔn)C++實(shí)現(xiàn)，數(shù)據(jù)均采用合成的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集，本文對(duì)獨(dú)立分布、正相關(guān)分布和反相關(guān)分布數(shù)據(jù)分別進(jìn)行測(cè)試。實(shí)驗(yàn)環(huán)境為Intel Core i5-4590 3.30 GHz CPU和8 GB內(nèi)存的PC機(jī)。實(shí)驗(yàn)中參數(shù)的主要變化范圍及其默認(rèn)值如表1所示。

Table 1 Experimentalparameters表1 實(shí)驗(yàn)參數(shù)變化范圍

首先，討論在窗口大小為100，維度為4，滑動(dòng)因子為1時(shí)ρ值對(duì)算法性能的影響。圖4表示了當(dāng)ρ值從2變化到6時(shí)ρ-支配輪廓集的大小變化情況，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，隨著ρ值的增大，ρ-支配輪廓集都逐漸減小。原因在于ρ值增大導(dǎo)致數(shù)據(jù)所支配的面積變大，數(shù)據(jù)越容易被ρ-支配，從而使數(shù)據(jù)成為ρ-支配輪廓點(diǎn)的概率減小。圖5表示了ρ值對(duì)響應(yīng)時(shí)間的影響，從圖中可以看出，當(dāng)ρ值變化時(shí)響應(yīng)時(shí)間沒(méi)有太大的改變，但是不管何種分布數(shù)據(jù)，DSSW算法由于采用了數(shù)據(jù)過(guò)濾技術(shù)、近似R樹(shù)索引和數(shù)據(jù)分類(lèi)方法，響應(yīng)時(shí)間都遠(yuǎn)小于BBDS算法。圖6顯示了ρ值對(duì)滑動(dòng)窗口中保留的數(shù)據(jù)量的影響，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，滑動(dòng)窗口中保留的數(shù)據(jù)量都與ρ值無(wú)關(guān)。原因在于采用的數(shù)據(jù)過(guò)濾方法是過(guò)濾掉被后到的點(diǎn)完全支配的點(diǎn)，對(duì)于相同的數(shù)據(jù)流，當(dāng)ρ大于1時(shí)過(guò)濾掉的點(diǎn)是相同的，但是DSSW算法由于采用了數(shù)據(jù)過(guò)濾方法，滑動(dòng)窗口中保留的數(shù)據(jù)量始終小于BBDS算法滑動(dòng)窗口中保留的數(shù)據(jù)量。圖5和圖6的實(shí)驗(yàn)結(jié)果都證明了DSSW算法的有效性。

Fig.4 Effectofρon skyline size圖4 ρ值對(duì)輪廓集大小的影響

Fig.5 Effectofρon response time圖5 ρ值對(duì)響應(yīng)時(shí)間的影響

Fig.6 Effectofρon data size inw indow圖6 ρ值對(duì)窗口中保留數(shù)據(jù)量的影響

Fig.7 Effectof slidingw indow sizeon skyline size圖7 滑動(dòng)窗口大小對(duì)輪廓集大小的影響

然后，討論ρ值為2，維度為4，滑動(dòng)因子為1時(shí)滑動(dòng)窗口的大小對(duì)算法性能的影響。圖7顯示了當(dāng)滑動(dòng)窗口大小變化時(shí)ρ-支配輪廓集大小的變化情況，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，ρ-支配輪廓集都隨著滑動(dòng)窗口的增大而增大。原因在于當(dāng)滑動(dòng)窗口增大時(shí)，參與輪廓計(jì)算的數(shù)據(jù)點(diǎn)增多，從而ρ-支配輪廓集增大。圖8顯示了滑動(dòng)窗口大小對(duì)算法響應(yīng)時(shí)間的影響，從圖中可以看出，當(dāng)滑動(dòng)窗口變大時(shí)，BBDS算法的響應(yīng)時(shí)間急劇增加，而DSSW算法由于采用了數(shù)據(jù)過(guò)濾、近似R樹(shù)索引和數(shù)據(jù)分類(lèi)，響應(yīng)時(shí)間雖然增加，但始終小于BBDS算法，且滑動(dòng)窗口越大，差距越明顯。圖9顯示了滑動(dòng)窗口大小對(duì)滑動(dòng)窗口中保留的數(shù)據(jù)量的影響，從圖中可以看出，BBDS算法的滑動(dòng)窗口中保留的數(shù)據(jù)量始終與滑動(dòng)窗口的大小相同，而DSSW算法隨著滑動(dòng)窗口的變大，滑動(dòng)窗口中保留的數(shù)據(jù)量逐漸變多，但DSSW算法由于采用了數(shù)據(jù)過(guò)濾方法，滑動(dòng)窗口中保留的數(shù)據(jù)量總是遠(yuǎn)遠(yuǎn)小于BBDS算法的滑動(dòng)窗口中保留的數(shù)據(jù)量。圖8和圖9進(jìn)一步證明了DSSW算法的有效性。

Fig.8 Effectof slidingw indow size on response time圖8 滑動(dòng)窗口大小對(duì)響應(yīng)時(shí)間的影響

Fig.9 Effectof slidingw indow sizeon data size inw indow圖9 滑動(dòng)窗口大小對(duì)窗口中保留數(shù)據(jù)量的影響

Fig.10 Effectof dimension on skyline size圖10 維度對(duì)輪廓集大小的影響

接著，討論當(dāng)ρ值為2，滑動(dòng)窗口大小為100，滑動(dòng)因子為1時(shí)維度對(duì)算法性能的影響。圖10顯示了當(dāng)維度從2變化到6時(shí)ρ-支配輪廓集的大小，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，ρ-支配輪廓集隨著維度的增加而增大。原因在于維度增大時(shí)，數(shù)據(jù)點(diǎn)被ρ-支配的概率降低，數(shù)據(jù)成為ρ-支配輪廓點(diǎn)的可能性增大，從而ρ-支配輪廓集變大，當(dāng)維度超過(guò)一定限度時(shí)，ρ-支配輪廓將為滑動(dòng)窗口中的全部數(shù)據(jù)。圖11顯示了維度對(duì)響應(yīng)時(shí)間的影響，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，當(dāng)維度增加時(shí)響應(yīng)時(shí)間變長(zhǎng)，但是DSSW算法的響應(yīng)時(shí)間遠(yuǎn)小于BBDS算法。圖12顯示了維度對(duì)滑動(dòng)窗口中保留的數(shù)據(jù)量的影響，從圖中可以看出，BBDS算法的滑動(dòng)窗口中保留的數(shù)據(jù)量始終與滑動(dòng)窗口的大小相同，而DSSW算法滑動(dòng)窗口中保留的數(shù)據(jù)量隨著維度的增加而逐漸增加，但數(shù)據(jù)過(guò)濾使其總是小于BBDS算法的該值。圖11和圖12進(jìn)一步證明了DSSW算法的有效性。

Fig.11 Effectof dimension on response time圖11 維度對(duì)響應(yīng)時(shí)間的影響

Fig.12 Effectof dimension on data size inw indow圖12 維度對(duì)窗口中保留數(shù)據(jù)量的影響

Fig.13 Effectof sliding factor on skyline size圖13 滑動(dòng)因子對(duì)輪廓集大小的影響

最后，討論當(dāng)ρ值為2，滑動(dòng)窗口大小為100，維度為4時(shí)滑動(dòng)因子對(duì)算法性能的影響。圖13顯示了當(dāng)滑動(dòng)因子從1變化到5時(shí)相應(yīng)的ρ-支配輪廓集的大小，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，ρ-支配輪廓集都不受滑動(dòng)因子的影響。原因在于滑動(dòng)因子只代表數(shù)據(jù)流更新的快慢，對(duì)數(shù)據(jù)是否成為ρ-支配輪廓點(diǎn)沒(méi)有影響。圖14顯示了滑動(dòng)因子對(duì)響應(yīng)時(shí)間的影響，從圖中可以看出，無(wú)論是何種分布數(shù)據(jù)，當(dāng)滑動(dòng)因子增加時(shí)響應(yīng)時(shí)間變長(zhǎng)。原因在于滑動(dòng)窗口中需要更新的數(shù)據(jù)變多，需要參與ρ-支配計(jì)算的數(shù)據(jù)變多，但是DSSW算法的響應(yīng)時(shí)間始終小于BBDS算法的響應(yīng)時(shí)間。圖15顯示了滑動(dòng)因子對(duì)滑動(dòng)窗口中保留的數(shù)據(jù)量的影響，從圖中可以看出，滑動(dòng)因子對(duì)滑動(dòng)窗口中的數(shù)據(jù)量幾乎沒(méi)有影響，BBDS算法的滑動(dòng)窗口中保留的數(shù)據(jù)量始終與滑動(dòng)窗口的大小相同，而DSSW算法由于采用了數(shù)據(jù)過(guò)濾方法，滑動(dòng)窗口中保留的數(shù)據(jù)量始終小于BBDS算法的滑動(dòng)窗口中保留的數(shù)據(jù)量。圖14和圖15更進(jìn)一步證明了DSSW算法的有效性。

6 結(jié)論

Fig.14 Effectof sliding factoron response time圖14 滑動(dòng)因子對(duì)響應(yīng)時(shí)間的影響

Fig.15 Effectof sliding factor on data size in w indow圖15 滑動(dòng)因子對(duì)窗口中保留數(shù)據(jù)量的影響

ρ-支配輪廓查詢(xún)被廣泛應(yīng)用于數(shù)值間比例關(guān)系的多標(biāo)準(zhǔn)決策中，但在數(shù)據(jù)的流特性日益突出的今天，傳統(tǒng)的ρ-支配輪廓查詢(xún)無(wú)法在數(shù)據(jù)更新頻繁時(shí)滿(mǎn)足查詢(xún)處理的實(shí)時(shí)性需求，因此本文研究了數(shù)據(jù)流上的ρ-支配輪廓查詢(xún)處理技術(shù)。首先，通過(guò)實(shí)際問(wèn)題對(duì)數(shù)據(jù)流上的ρ-支配輪廓查詢(xún)的需求進(jìn)行分析，給出了數(shù)據(jù)流上的ρ-支配輪廓的概念；然后，通過(guò)充分挖掘數(shù)據(jù)流上的ρ-支配輪廓的性質(zhì)，建立了基于時(shí)序支配的數(shù)據(jù)過(guò)濾方法，并將數(shù)據(jù)集進(jìn)行分類(lèi)；接著，提出了數(shù)據(jù)流上的基于滑動(dòng)窗口的ρ-支配輪廓查詢(xún)處理算法DSSW；最后，通過(guò)大量的實(shí)驗(yàn)證明了DSSW算法是計(jì)算數(shù)據(jù)流上的ρ-支配輪廓的高效算法。本文基于計(jì)數(shù)的滑動(dòng)窗口進(jìn)行討論，從中可以看出DSSW算法能夠容易地?cái)U(kuò)展到基于時(shí)間的滑動(dòng)窗口上。

[1]B?rzs?nyi S,Kossmann D,Stocker K.The skyline operator[C]//Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Germany,Apr 2-6,2001.Washington:IEEEComputer Society,2001:421-430.

[2]Papadias D,Tao Yufei,Fu G,etal.An optimal and progressive algorithm for skyline queries[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Managementof Data,San Diego,USA,Jun 9-12,2003.New York:ACM,2003:467-478.

[3]Chen Lei,Lian Xiang.Dynamic skyline queries inmetric spaces[C]//Proceedings of the 11th International Conferenceon Extending Database Technology:Advances in Database Technology,Nantes,France,Mar 25-29,2008.New York:ACM,2008:333-343.

[4]Chan CY,Jagadish H V,Tan K L,etal.On high dimensional skylines[C]//LNCS 3896:Proceedings of the 10th International Conference on Extending Database Technology,Munich,Germany,Mar 26-31,2006.Berlin,Heidelberg:Springer,2006:478-495.

[5]Yiu M L,Mamoulis N.Efficient processing of top-kdominating queries on multi-dimensional data[C]//Proceedings of the 33rd International Conference on Very Large Data Bases,Vienna,Austria,Sep 23-27,2007.New York:ACM,2007:483-494.

[6]Chen Lijiang,Cui Bin,Lu Hua.Constrained skyline query processing against distributed data sites[J].IEEE Transactionson Know ledge and Data Engineering,2011,23(2):204-217.

[7]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,Aug 20-23,2002.New York:ACM,2002:275-286.

[8]Lin Xuemin,Yuan Yidong,Wang Wei,et al.Stabbing the sky:efficientskyline computation over sliding w indows[C]//Proceedings of the 21st International Conference on Data Engineering,Tokyo,Japan,Apr 5-8,2005.Piscataway,USA:IEEE,2005:502-513.

[9]ZhangWenjie,Lin Xuemin,Zhang Ying,etal.Probabilistic skyline operator over sliding w indow s[C]//Proceedings of the 25th International Conference on Data Engineering,Shanghai,Mar 29-Apr 2,2009.Washington:IEEEComputer Society,2009:1060-1071.

[10]Ding Xiaofeng,Lian Xiang,Chen Lei,et al.Continuous monitoring of skylinesoveruncertain data streams[J].Information Sciences,2012,184(1):196-214.

[11]Yang Jing,Qu Bo,LiCuiping,etal.DC-Tree:an algorithm for skyline query on data streams[C]//LNCS 5139:Proceedings of the 4th International Conference on Advanced DataM ining and Applications,Chengdu,China,Oct8-10,2008.Berlin,Heidelberg:Springer,2008:644-651.

[12]Zhu Ling,LiCuiping,Chen Hong.Efficient computation of reverse skyline on data stream[C]//Proceedings of the 2009 International Joint Conference on Computational Sciences and Optim ization,Sanya,China,Apr24-26,2009.Washington:IEEEComputer Society,2009:735-739.

[13]Bai Mei,Xin Junchang,Wang Guoren,et al.Probabilistic reverse skyline query processing on uncertain data streams[J].Journal of Computer Research and Development,2011,48(10):1842-1849.

[14]Dellis E,V lachou A,V ladim irskiy I,etal.Constrained subspace skyline computation[C]//Proceedingsof the 15th International Conference on Information and Know ledge Management,Arlington,USA,Nov 6-11,2006.New York:ACM,2006:415-424.

[15]Morse M,Patel J,Grosky W.Efficient continuous skyline computation[J].Information Sciences,2007,177(17):3411-3437.

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

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

[13]白梅,信俊昌,王國(guó)仁,等.不確定數(shù)據(jù)流上的概率反輪廓查詢(xún)處理[J].計(jì)算機(jī)研究與發(fā)展,2011,48(10):1842-1849.

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

王之瓊（1980—），女，黑龍江哈爾濱人，2014年于東北大學(xué)計(jì)算機(jī)軟件與理論專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為東北大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)處理，計(jì)算機(jī)圖像處理，大數(shù)據(jù)分析等。發(fā)表學(xué)術(shù)論文40余篇，作為負(fù)責(zé)人承擔(dān)了國(guó)家自然科學(xué)基金、遼寧省自然科學(xué)基金和中國(guó)博士后科學(xué)基金等課題5項(xiàng)。

BA Jianm in was born in 1990.He is an M.S.candidate atNortheastern University.His research interest is Skyline query.

霸建民（1990—），男，河北景縣人，東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)镾kyline查詢(xún)處理。

HUANG Da was born in 1983.He is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include data stream,computernetwork andmachine learning,etc.

黃達(dá)（1983—），男，湖南瀏陽(yáng)人，東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)流，計(jì)算機(jī)網(wǎng)絡(luò)，機(jī)器學(xué)習(xí)等。

XIN Junchang was born in 1977.He received theM.S.and Ph.D.degrees in computer science and technology from Northeastern University in 2005 and 2008 respectively.Now he is an associate professor at School of Computer Science and Engineering,Northeastern University,and themember of CCF.His research interests include big data management,sensory datamanagement,uncertain datamanagement,cloud computing andmachine learning,etc.

信俊昌（1977—），男，遼寧遼陽(yáng)人，2005年和2008年于東北大學(xué)分別獲得碩士和博士學(xué)位，現(xiàn)為東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)管理，感知數(shù)據(jù)管理，不確定數(shù)據(jù)管理，云計(jì)算，機(jī)器學(xué)習(xí)等。

ρ-Dom inant Skyline Com putation on Data Stream s*

WANG Zhiqiong1,BA Jianm in2,HUANG Da2,XIN Junchang2+
1.Schoolof Sino-Dutch Biomedicaland Information Engineering,Northeastern University,Shenyang 110819,China
2.Schoolof Computer Scienceand Engineering,Northeastern University,Shenyang 110819,China

Skyline query on data stream can'tdirectly compute ρ-dominantskyline query,and traditionalρ-dominant skyline query can'tmeet the real-time need when data are updated frequently.So this paper proposesρ-dom inant skyline query algorithm on data stream.Firstly,the definitions of full-dom inance,ρ-dom inance and ρ-dominant skyline are introduced,and the definition ofρ-dom inant skyline on data stream is proposed.Next,a data filtering method based on time sequence dom inance is proposed by thoroughly analyzing properties aboutρ-dominantskyline on data stream,and an algorithm,calledρ-dom inantskyline query over slidingw indow(DSSW),is developed to increase the efficiency of skyline computing on data stream.Finally,extensive experiments show that the DSSW algorithm has obvious advantages in response time and storage space compared w ith traditionalρ-dominant skylinealgorithm.

iong was born in 1980.She

the Ph.D.degree in computer software and theory from Northeastern University in 2014.Now she is an associate professor and M.S.supervisor at Northeastern University.Her research interests include data processing,computer image processing and big data analytics,etc.

A

：TP311.13

*The NationalNatural Science Foundation of China underGrantNos.61402089,61472069,61502215(國(guó)家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under GrantNos.N161904001,N161602003(中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金);the Natural Science Foundation of Liaoning Province under Grant No.2015020553(遼寧省自然科學(xué)基金);the Postdoctoral Science Foundation of ChinaunderGrantNo.2016M 591447(中國(guó)博士后科學(xué)基金);the Postdoctoral Science Foundation of Northeastern University underGrantNo.20160203(東北大學(xué)博士后科研基金).

Received 2016-07,Accepted 2016-09.

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

Keywords:ρ-dom inant relationship;ρ-dom inantskyline;data stream;slidingw indow