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

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

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

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

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

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

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

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

1 引言

近年來，輪廓查詢[1-3]被廣泛地應(yīng)用于多標(biāo)準(zhǔn)決策中，例如個性化推薦系統(tǒng)、市場監(jiān)測系統(tǒng)等。給定一個數(shù)據(jù)點(diǎn)集合P，則數(shù)據(jù)集P的輪廓是指P中所有不被其他點(diǎn)支配的點(diǎn)的集合。需要指出的是一個點(diǎn)x支配另一個點(diǎn)y必須滿足x在所有維上都不比y差，并且至少在一維上x比y好。不失一般性，假設(shè)一個小的值比大的值好，在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)輪廓與動態(tài)輪廓示例圖

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

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

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

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

2 相關(guān)工作

2.1 輪廓查詢

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

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

2.2 ρ-支配輪廓查詢

2011年，Xin等人[16]首先提出了基于數(shù)值間比例值大小的ρ-支配關(guān)系和ρ-支配輪廓查詢的概念，并建立了一種應(yīng)用于傳統(tǒng)數(shù)據(jù)集上的基于分支定界的ρ-支配輪廓查詢算法（branch and boundρ-dominant skyline algorithm，BBDS）。BBDS算法采用標(biāo)準(zhǔn)的R樹索引存儲數(shù)據(jù)，并將所有數(shù)據(jù)分為兩類：ρ-支配輪廓集合S和非ρ-支配輪廓集合SS，初始時兩集合均為空。采用廣度優(yōu)先遍歷算法遍歷R樹中的節(jié)點(diǎn)e，如果e是中間節(jié)點(diǎn)，判斷e是否被S+SS中的兩個數(shù)據(jù)支配；若不被兩個數(shù)據(jù)支配，則遍歷所有不被兩個元素支配的子節(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ù)更新時便先維護(hù)R樹，再調(diào)用BBDS算法，必將花費(fèi)大量的時間和空間代價?？傊瑐鹘y(tǒng)的ρ-支配輪廓查詢無法在數(shù)據(jù)更新頻繁時滿足查詢處理的實(shí)時性需求，而數(shù)據(jù)流上的輪廓查詢不能滿足數(shù)值間比例關(guān)系的輪廓查詢。因此，本文將深入研究數(shù)據(jù)流中的ρ-支配輪廓查詢問題。

3 問題描述

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

定義1（完全支配）一個點(diǎn)x關(guān)于查詢點(diǎn)q完全支配另一個點(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（ρ-支配）一個點(diǎn)x關(guān)于查詢點(diǎn)qρ-支配另一個點(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）顯示了二維空間中完全支配的一個例子。因?yàn)閷θ我庖痪Sb和q之間的距離比a和q之間的距離短，并且a、b在q的同一側(cè)，所以點(diǎn)b關(guān)于查詢點(diǎn)q完全支配點(diǎn)a。同理，點(diǎn)h關(guā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時的ρ-支配關(guān)系的例子，在本例中使用x′表示x與q的1/3分位點(diǎn)。因?yàn)閷θ我庖痪S點(diǎn)b′和點(diǎn)q之間的距離比點(diǎn)a和點(diǎn)q之間的距離小，并且b′和a在點(diǎn)q的同一側(cè)，所以點(diǎn)b關(guān)于查詢點(diǎn)q1.5-支配點(diǎn)a。同理可得，點(diǎn)f關(guān)于查詢點(diǎn)q1.5-支配點(diǎn)e，并且點(diǎn)e關(guān)于查詢點(diǎn)q1.5-支配點(diǎn)f，點(diǎn)h關(guā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（完全支配輪廓）給定一個數(shù)據(jù)集合P和一個查詢點(diǎn)q，數(shù)據(jù)集P中所有不被P中其他點(diǎn)關(guān)于點(diǎn)q完全支配的點(diǎn)構(gòu)成數(shù)據(jù)集P的完全支配輪廓。

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

根據(jù)定義3可得，如果一個點(diǎn)p不被數(shù)據(jù)集中其他任一點(diǎn)關(guān)于查詢點(diǎn)q完全支配，則點(diǎn)p為一個完全支配輪廓點(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ù)據(jù)流上的ρ-支配輪廓的定義。用PN表示數(shù)據(jù)流中最近的N組數(shù)據(jù)，即滑動窗口中的數(shù)據(jù)，并且用L(p)表示點(diǎn)p在數(shù)據(jù)流中的位置，L(p)大的點(diǎn)表示后到，數(shù)據(jù)流中的ρ-支配輪廓如定義5所示。

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

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

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

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

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

如圖2（a）和圖2（b）所示，對于同一個數(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給定兩個值ρ1和ρ2，并且ρ1＞ρ2，如果一個點(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可以看出，通過調(diào)節(jié)ρ值的大小可以控制結(jié)果集的大小，因此 ρ-支配輪廓查詢有更廣泛的應(yīng)用。

定理2給定兩個點(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可以看出，如果一個點(diǎn)x被另一個點(diǎn)y完全支配，那么當(dāng) ρ＞1時點(diǎn)x也被點(diǎn)yρ-支配。由定理2的證明過程可以容易地得出反之不成立。

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

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

引理1給定數(shù)據(jù)流中的兩個點(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]|，則通過兩式分別相乘得 ?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]|，因此。 □

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

4.2 過濾方法

考慮圖3中的例子，其中點(diǎn)按照它們的字母表順序依次到達(dá)，并且 ρ值為2。假設(shè)點(diǎn)c剛剛到達(dá)滑動窗口，并且滑動窗口的大小大于3，因?yàn)辄c(diǎn)a被點(diǎn)b2-支配，所以點(diǎn)a不可能成為ρ-支配輪廓點(diǎn)，但是如果將a過濾掉，因?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)過濾掉。

Fig.3 Counterexampleof filtering圖3 過濾的反例

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

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

（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è)滑動窗口的大小不小于8，并且點(diǎn)按照字母表順序到達(dá)。因?yàn)辄c(diǎn)a和g分別被b和h完全支配，所以計算前過濾掉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被一個先到的點(diǎn)eρ-支配而不被后到的點(diǎn)ρ-支配，所以候選點(diǎn)CN={f}；因?yàn)辄c(diǎn)e被一個后到的點(diǎn)ρ-支配而不被后到的點(diǎn)完全支配，所以輔助點(diǎn)AN={e}。

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

4.3 查詢過程

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

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

算法1描述了DSSW算法的具體查詢過程。當(dāng)n個新的點(diǎn)p1-pn到達(dá)時，如果滑動窗口已滿，則查找滑動窗口中最先到達(dá)的n個點(diǎn)o1-on，并計算點(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中；計算出點(diǎn)p1-pn所屬的區(qū)域R()，并根據(jù)R()將p1-pn分成k組；對于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存儲到區(qū)域R(pi)中。

算法1DSSW算法

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

2.if（滑動窗口已滿）

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

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

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

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

7.將DC從CN移動到DN

8.計算點(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)過濾掉

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

14.將DS中的點(diǎn)從DN和CN移動到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存儲到相應(yīng)的R(p)中

算法2描述了點(diǎn)p所屬區(qū)域的計算過程。在此過程中，假設(shè)點(diǎn)p和查詢點(diǎn)q都是d維。如果在第一維中點(diǎn)p大于點(diǎn)q，則將1放入R(p)容器中，如果在第一維點(diǎn)p小于點(diǎn)q，則將0放入R(p)容器中，否則將0和1同時放入R(p)容器中；然后從第二維到第d維遍歷p和q中的數(shù)據(jù)，假設(shè)遍歷到第i維，如果在第i維點(diǎn)p大于點(diǎn)q，則將容器R(p)中的每個數(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在某些維上的值相同，將得到多個區(qū)域，那么每個區(qū)域都需要進(jìn)行處理。

算法2計算點(diǎn)p的區(qū)域號

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

output:點(diǎn)p的區(qū)域號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)地測試了擴(kuò)展的BBDS算法[16]和DSSW算法在ρ值、滑動窗口大小、滑動因子和數(shù)據(jù)維度變化時的性能。性能評估指標(biāo)包括響應(yīng)時間和滑動窗口中的數(shù)據(jù)量，顯然響應(yīng)時間越短，滑動窗口中保留的數(shù)據(jù)量越小，在響應(yīng)時間及存儲空間上的優(yōu)勢越明顯。所有算法均采用標(biāo)準(zhǔn)C++實(shí)現(xiàn)，數(shù)據(jù)均采用合成的標(biāo)準(zhǔn)測試數(shù)據(jù)集，本文對獨(dú)立分布、正相關(guān)分布和反相關(guān)分布數(shù)據(jù)分別進(jìn)行測試。實(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，滑動因子為1時ρ值對算法性能的影響。圖4表示了當(dāng)ρ值從2變化到6時ρ-支配輪廓集的大小變化情況，從圖中可以看出，無論是何種分布數(shù)據(jù)，隨著ρ值的增大，ρ-支配輪廓集都逐漸減小。原因在于ρ值增大導(dǎo)致數(shù)據(jù)所支配的面積變大，數(shù)據(jù)越容易被ρ-支配，從而使數(shù)據(jù)成為ρ-支配輪廓點(diǎn)的概率減小。圖5表示了ρ值對響應(yīng)時間的影響，從圖中可以看出，當(dāng)ρ值變化時響應(yīng)時間沒有太大的改變，但是不管何種分布數(shù)據(jù)，DSSW算法由于采用了數(shù)據(jù)過濾技術(shù)、近似R樹索引和數(shù)據(jù)分類方法，響應(yīng)時間都遠(yuǎn)小于BBDS算法。圖6顯示了ρ值對滑動窗口中保留的數(shù)據(jù)量的影響，從圖中可以看出，無論是何種分布數(shù)據(jù)，滑動窗口中保留的數(shù)據(jù)量都與ρ值無關(guān)。原因在于采用的數(shù)據(jù)過濾方法是過濾掉被后到的點(diǎn)完全支配的點(diǎn)，對于相同的數(shù)據(jù)流，當(dāng)ρ大于1時過濾掉的點(diǎn)是相同的，但是DSSW算法由于采用了數(shù)據(jù)過濾方法，滑動窗口中保留的數(shù)據(jù)量始終小于BBDS算法滑動窗口中保留的數(shù)據(jù)量。圖5和圖6的實(shí)驗(yàn)結(jié)果都證明了DSSW算法的有效性。

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

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

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

Fig.7 Effectof slidingw indow sizeon skyline size圖7 滑動窗口大小對輪廓集大小的影響

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

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

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

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

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

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

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

Fig.13 Effectof sliding factor on skyline size圖13 滑動因子對輪廓集大小的影響

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

6 結(jié)論

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

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

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

[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]白梅,信俊昌,王國仁,等.不確定數(shù)據(jù)流上的概率反輪廓查詢處理[J].計算機(jī)研究與發(fā)展,2011,48(10):1842-1849.

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

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

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—），男，湖南瀏陽人，東北大學(xué)計算機(jī)科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(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—），男，遼寧遼陽人，2005年和2008年于東北大學(xué)分別獲得碩士和博士學(xué)位，現(xiàn)為東北大學(xué)計算機(jī)科學(xué)與工程學(xué)院副教授，CCF會員，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)管理，感知數(shù)據(jù)管理，不確定數(shù)據(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(國家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under GrantNos.N161904001,N161602003(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金);the Natural Science Foundation of Liaoning Province under Grant No.2015020553(遼寧省自然科學(xué)基金);the Postdoctoral Science Foundation of ChinaunderGrantNo.2016M 591447(中國博士后科學(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