霸建民，郭永紅，彭龍，趙東陽(yáng)，邵鵬志，杜宏博

(中國(guó)兵器工業(yè)集團(tuán)有限公司 計(jì)算機(jī)應(yīng)用技術(shù)研究所,北京 100089)

0 引言

目前，隨著數(shù)據(jù)采集手段的迅猛發(fā)展，大量的數(shù)據(jù)得以產(chǎn)生并且呈現(xiàn)出數(shù)據(jù)流[1-2]的特點(diǎn)。但是很多情況下數(shù)據(jù)采集區(qū)域的網(wǎng)絡(luò)非常受限，比如網(wǎng)絡(luò)時(shí)斷時(shí)續(xù)、網(wǎng)絡(luò)帶寬較小，而且數(shù)據(jù)應(yīng)用和數(shù)據(jù)采集往往分布在不同的地點(diǎn)，因此怎樣將采集的流式數(shù)據(jù)及時(shí)傳輸?shù)綌?shù)據(jù)應(yīng)用方至關(guān)重要。例如，裝甲車通過(guò)傳感器能夠?qū)崟r(shí)獲取車輛的油壓、水溫等狀態(tài)數(shù)據(jù)，而遠(yuǎn)方的數(shù)據(jù)中心通過(guò)這些車輛的狀態(tài)數(shù)據(jù)可以判斷出車輛的健康狀況，指揮官根據(jù)車輛的健康狀況進(jìn)行某場(chǎng)戰(zhàn)役的指揮，因此在網(wǎng)絡(luò)受限情況下，如何計(jì)算出車輛狀態(tài)數(shù)據(jù)中的關(guān)鍵數(shù)據(jù)進(jìn)行傳輸至關(guān)重要。

作為多目標(biāo)決策與數(shù)據(jù)挖掘的重要手段之一，輪廓查詢[3-5]及其變體輪廓查詢[6-18]在許多實(shí)際應(yīng)用中都發(fā)揮著非常重要的作用，即從海量數(shù)據(jù)中選取最為關(guān)鍵的數(shù)據(jù)。給定一個(gè)多維元組的集合P，則元組P的輪廓指的是P中所有不被其他多維元組支配的元組集合。一個(gè)多維元組x支配另一個(gè)多維元組y等價(jià)于元組x在所有維度上都不比元組y差并且至少在某個(gè)維度上元組x比元組y關(guān)鍵。數(shù)據(jù)元組在各維度上的關(guān)鍵與否，可以是用戶指定的標(biāo)準(zhǔn)，即可以是“大于”、“小于”以及“不等于”等。

當(dāng)以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)進(jìn)行輪廓查詢時(shí)，查詢的結(jié)果為偏向給定查詢點(diǎn)q的數(shù)據(jù)，此種情況下可以被應(yīng)用于個(gè)性化商品推薦，將輪廓結(jié)果反饋給用戶。但是由于裝甲車狀態(tài)數(shù)據(jù)中查詢偏向給定查詢點(diǎn)的狀態(tài)數(shù)據(jù)，在數(shù)據(jù)中心接收到的為最接近查詢點(diǎn)q的狀態(tài)數(shù)據(jù)，而存在健康問(wèn)題的狀態(tài)數(shù)據(jù)不能通過(guò)輪廓查詢算法計(jì)算出來(lái)發(fā)送給數(shù)據(jù)中心，因此數(shù)據(jù)中心無(wú)法判斷哪些裝甲車輛存在問(wèn)題。而當(dāng)采用“大于”作為關(guān)鍵的標(biāo)準(zhǔn)時(shí)，輪廓計(jì)算出的數(shù)據(jù)為偏離查詢點(diǎn)的數(shù)據(jù)，即為相對(duì)異常的數(shù)據(jù)，數(shù)據(jù)中心能夠憑借異常數(shù)據(jù)鑒定裝甲車輛的健康狀況。鑒于此，本文采用“大于”作為關(guān)鍵的標(biāo)準(zhǔn)。以“大于”作為標(biāo)準(zhǔn)和以“小于”作為標(biāo)準(zhǔn)對(duì)輪廓的影響如圖1所示。

圖1 關(guān)鍵標(biāo)準(zhǔn)對(duì)輪廓的影響Fig.1 Effect of key standards on skyline

傳統(tǒng)輪廓查詢中的支配關(guān)系都是依賴于多維數(shù)據(jù)對(duì)應(yīng)數(shù)值之間的大小關(guān)系而進(jìn)行設(shè)計(jì)的，均沒(méi)有考慮數(shù)值間的比例關(guān)系。然而，在一些實(shí)際應(yīng)用中，數(shù)值間的大小關(guān)系并不能完全說(shuō)明兩組數(shù)據(jù)誰(shuí)更關(guān)鍵，這時(shí)就需要使用數(shù)值間的比例關(guān)系進(jìn)行關(guān)鍵數(shù)據(jù)選擇。例如，某型裝甲車的標(biāo)準(zhǔn)油壓和水溫為20 kPa和20 ℃，而某一個(gè)裝甲車有兩組狀態(tài)數(shù)據(jù)在油壓和水溫之外其他的狀態(tài)數(shù)據(jù)都一樣，其中狀態(tài)A油壓為40 kPa、水溫為30 ℃，狀態(tài)B油壓為45 kPa、水溫為25 ℃，要求從狀態(tài)A和狀態(tài)B中選出關(guān)鍵的數(shù)據(jù)傳送到數(shù)據(jù)中心。狀態(tài)A在油壓和水溫上偏離標(biāo)準(zhǔn)狀態(tài)的偏離值分別為20 kPa和10 ℃，狀態(tài)B在油壓和水溫上偏離標(biāo)準(zhǔn)狀態(tài)的偏離值分別為25 kPa和5 ℃，當(dāng)考慮數(shù)值間大小關(guān)系時(shí)，在油壓維度上狀態(tài)A的偏離值比狀態(tài)B的偏離值小5 kPa，而在水溫維度上狀態(tài)A的偏離值比狀態(tài)B的偏離值大5 ℃，因此不能決定狀態(tài)A和狀態(tài)B哪個(gè)更關(guān)鍵。這時(shí)可以考慮基于數(shù)值間比例的支配關(guān)系，在油壓維度上狀態(tài)A的偏離值與狀態(tài)B的偏離值的比值為0.8，在水溫維度上狀態(tài)A的偏離值與狀態(tài)B的偏離值的比值為2，因此在兩維上的比值均≥0.8；在油壓維度上狀態(tài)B的偏離值與狀態(tài)A的偏離值的比值為1.25，在水溫維度上狀態(tài)B的偏離值與狀態(tài)A的偏離值的比值為0.5，不均≥0.8，因此可以判定狀態(tài)A更關(guān)鍵。特別是當(dāng)各維度上數(shù)值不在同一量級(jí)時(shí)，基于對(duì)應(yīng)數(shù)值間比例的支配關(guān)系更能計(jì)算出關(guān)鍵數(shù)據(jù)。將對(duì)應(yīng)數(shù)值間的比值稱之為ρ，因此基于對(duì)應(yīng)數(shù)值間比例的支配關(guān)系也稱之為ρ-支配關(guān)系,在此基礎(chǔ)上的輪廓查詢稱之為ρ-支配輪廓[19]查詢。

然而，裝甲車輛的狀態(tài)數(shù)據(jù)具有數(shù)據(jù)流的特性，王之瓊等[20]在ρ≥1時(shí)，以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)討論了ρ-支配關(guān)系的性質(zhì)，并且給出了一種數(shù)據(jù)流中ρ-支配輪廓計(jì)算方法。本文考慮網(wǎng)絡(luò)受限環(huán)境中裝甲車輛狀態(tài)數(shù)據(jù)傳輸?shù)膶?shí)際情況，偏離查詢點(diǎn)的狀態(tài)數(shù)據(jù)對(duì)于評(píng)估裝甲車輛的健康狀態(tài)更為關(guān)鍵，因此以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)進(jìn)行分析，然而當(dāng)以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)時(shí)，ρ-支配關(guān)系的性質(zhì)將發(fā)生改變，原算法不能直接應(yīng)用于以“大于”作為關(guān)鍵標(biāo)準(zhǔn)的數(shù)據(jù)流中ρ-支配輪廓查詢，同時(shí)考慮ρ≥1以及ρ<1的不同情況，對(duì)ρ-支配關(guān)系的性質(zhì)重新進(jìn)行分析，進(jìn)而對(duì)原算法進(jìn)行更改及擴(kuò)展，在此基礎(chǔ)上提出了數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢算法，數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢算法是在滑動(dòng)窗口(大小為N)最近的n(n≤N)個(gè)點(diǎn)中計(jì)算ρ-支配輪廓點(diǎn)，進(jìn)一步滿足網(wǎng)絡(luò)受限環(huán)境中關(guān)鍵數(shù)據(jù)選擇傳輸?shù)囊?。歸結(jié)起來(lái)，本文的主要貢獻(xiàn)如下：

1) 以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)，同時(shí)考慮ρ≥1以及ρ<1的不同情況重新對(duì)ρ-支配關(guān)系和ρ-支配輪廓的定義和性質(zhì)進(jìn)行了分析；

2) 對(duì)數(shù)據(jù)流中ρ-支配輪廓查詢算法進(jìn)行更改及擴(kuò)展，在此基礎(chǔ)上提出了數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢算法；

3) 設(shè)計(jì)了詳盡的實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)表明數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢相比于數(shù)據(jù)流中ρ-支配輪廓查詢具有更廣泛的應(yīng)用。

1 相關(guān)研究工作

一些學(xué)者在傳統(tǒng)輪廓查詢的基礎(chǔ)上提出了輪廓變體查詢：Borzsonyi等[3]使用輪廓查詢?nèi)U(kuò)展數(shù)據(jù)庫(kù)系統(tǒng)，輪廓操作從一組大數(shù)據(jù)集合中篩選出一組用戶所感興趣的子數(shù)據(jù)集合，并提出了嵌套循環(huán)算法；Papadias等[4]分析了NN算法的缺陷并提出了BBS算法，此算法采用鄰近漸進(jìn)搜索方式，僅對(duì)可能包含輪廓點(diǎn)的R樹(shù)節(jié)點(diǎn)執(zhí)行單次訪問(wèn)；Ding等[5]提出了在Map-Reduce框架下處理海量數(shù)據(jù)的輪廓查詢算法，另外給出了高效的優(yōu)化方法用來(lái)提高海量數(shù)據(jù)輪廓查詢的效率；Lai等[7]研究了移動(dòng)物聯(lián)網(wǎng)應(yīng)用中特定范圍內(nèi)的RSQ算法，提出了一種有效、非集中的分布式DCRSQ算法，以滿足移動(dòng)環(huán)境中的范圍輪廓查詢的需求；Tian等[8]針對(duì)高維數(shù)據(jù)集合中計(jì)算輪廓時(shí)檢索數(shù)據(jù)量大的問(wèn)題，提出了一種在MapReduce框架下的并行k-維輪廓查詢算法，提高了k-維輪廓查詢的效率；Chen等[13]考慮到現(xiàn)實(shí)中的數(shù)據(jù)具有動(dòng)態(tài)性，將輪廓查詢擴(kuò)展到變換空間中，提出了變換空間中的輪廓查詢，并提出了一種剪枝技術(shù)提高變換空間中輪廓查詢的效率；周劍剛等[14]提出了一種道路網(wǎng)的輪廓查詢EI算法，通過(guò)分析用戶運(yùn)動(dòng)狀態(tài)與查詢間的關(guān)聯(lián)關(guān)系，根據(jù)時(shí)間通過(guò)協(xié)同過(guò)濾擴(kuò)展方法確定初始輪廓結(jié)果集，并對(duì)數(shù)據(jù)集進(jìn)行剪枝，監(jiān)測(cè)用戶的運(yùn)動(dòng)狀態(tài)，一旦用戶速度發(fā)生變化，就快速根據(jù)出入點(diǎn)信息動(dòng)態(tài)調(diào)整輪廓集；Zou等[15]研究了大型圖表中的動(dòng)態(tài)skyline查詢，并提出了一種基于圖屬性的修剪規(guī)則，以推導(dǎo)DSG查詢的候選對(duì)象；Li等[16]提出了一種基于多層網(wǎng)格模型的數(shù)據(jù)流中動(dòng)態(tài)輪廓查詢方法，模型將工作空間劃分為多層網(wǎng)格，并基于現(xiàn)有數(shù)據(jù)集創(chuàng)建每層網(wǎng)格的skyline影響區(qū)域，僅當(dāng)動(dòng)態(tài)數(shù)據(jù)點(diǎn)在每層網(wǎng)格的skyline影響區(qū)域內(nèi)更新時(shí)，才進(jìn)行連續(xù)skyline查詢；張麗等[17]為了應(yīng)對(duì)元組在數(shù)據(jù)流上隨機(jī)添加和刪除的挑戰(zhàn)，采用了基于網(wǎng)格的索引來(lái)存儲(chǔ)元組，并提出了一種基于該索引的算法來(lái)計(jì)算和維護(hù)輪廓集；Bai等[18]提出了一種改進(jìn)的基于數(shù)據(jù)流的動(dòng)態(tài)輪廓查詢算法IDS2，避免在更新某些點(diǎn)時(shí)計(jì)算量急劇增加，加快數(shù)據(jù)流上更新操作的速度，提高動(dòng)態(tài)skyline的計(jì)算性能。

也有學(xué)者針對(duì)ρ-支配輪廓查詢開(kāi)展了一些研究工作。信俊昌等[19]首先通過(guò)對(duì)實(shí)際應(yīng)用需求進(jìn)行分析，提出了基于數(shù)值間比例值大小的ρ-支配關(guān)系，并且根據(jù)ρ-支配關(guān)系提出了ρ-支配輪廓查詢，進(jìn)一步提出了計(jì)算ρ-支配輪廓的BA算法和基于分支定界的BBDS算法，最后通過(guò)實(shí)驗(yàn)證明了BBDS算法相比于BA算法提升了效率；王之瓊等[20]在ρ≥1時(shí)，以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)給出了完全支配、ρ-支配以及ρ-支配輪廓的定義，進(jìn)一步給出了數(shù)據(jù)流中ρ-支配輪廓的定義，然后分析了數(shù)據(jù)流中ρ-支配輪廓的性質(zhì)并提出了基于時(shí)序支配的數(shù)據(jù)過(guò)濾方法，最后給出了數(shù)據(jù)流中ρ-支配輪廓查詢的DSSW算法，將ρ-支配輪廓計(jì)算方法擴(kuò)展到數(shù)據(jù)流中。

2 ρ-支配理論

數(shù)據(jù)流中ρ-支配輪廓查詢算法[20]以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)給出了完全支配和ρ-支配的定義，本文為了解決裝甲車輛狀態(tài)數(shù)據(jù)中關(guān)鍵數(shù)據(jù)選擇傳輸?shù)男枰?，以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)重新給出相關(guān)定義。

定義1(完全支配) 一個(gè)多維數(shù)據(jù)點(diǎn)x關(guān)于查詢點(diǎn)q完全支配另一個(gè)多維數(shù)據(jù)點(diǎn)y當(dāng)且僅當(dāng)滿足以下兩個(gè)條件：

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥
0∧|x[i]-q[i]|≥|y[i]-q[i]|，

(1)

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])>
0∧|x[i]-q[i]|>|y[i]-q[i]|，

(2)

式中：d為數(shù)據(jù)的維度。

定義2(ρ-支配) 一個(gè)多維數(shù)據(jù)點(diǎn)x關(guān)于查詢點(diǎn)qρ-支配另一個(gè)多維數(shù)據(jù)點(diǎn)y當(dāng)且僅當(dāng)滿足以下兩個(gè)條件：

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥
0∧|x[i]-q[i]|≥ρ×|y[i]-q[i]|，

(3)

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])>
0∧|x[i]-q[i]|>ρ×|y[i]-q[i]|.

(4)

由定義1和定義2可以看出，以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)時(shí)完全支配和ρ-支配的定義與以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)時(shí)完全支配和ρ-支配的定義有所不同，所滿足的條件由“小于”和“小于等于”變?yōu)榱恕按笥凇焙汀按笥诘扔凇薄?/p>

圖2為二維空間中完全支配和ρ-支配的示意圖。圖2(a)是完全支配的一個(gè)例子，其中：由于數(shù)據(jù)點(diǎn)a和數(shù)據(jù)點(diǎn)b在以點(diǎn)q為中心的同一象限內(nèi)，并且在任意維度上數(shù)據(jù)點(diǎn)a和點(diǎn)q間的長(zhǎng)度都大于數(shù)據(jù)點(diǎn)b和點(diǎn)q間的長(zhǎng)度，所以點(diǎn)a關(guān)于查詢點(diǎn)q完全支配點(diǎn)b.圖2(b)展示了當(dāng)ρ=2時(shí)的ρ-支配關(guān)系示例，其中：點(diǎn)a′是點(diǎn)a和點(diǎn)q的中點(diǎn)，點(diǎn)b′是點(diǎn)b和點(diǎn)q的中點(diǎn)；由于數(shù)據(jù)點(diǎn)a和數(shù)據(jù)點(diǎn)b在以點(diǎn)q為中心的同一象限內(nèi)并且點(diǎn)a′與點(diǎn)q的距離并不在任意維度上都大于等于點(diǎn)b與點(diǎn)q的距離，因此點(diǎn)a不能ρ-支配點(diǎn)b，同理點(diǎn)b不能ρ-支配點(diǎn)a.從上述分析中可以看出，當(dāng)ρ改變時(shí)，相同數(shù)據(jù)集合的ρ-支配關(guān)系將發(fā)生改變。

圖2 完全支配和ρ-支配Fig.2 Full dominance and ρ-dominance

定義3(數(shù)據(jù)流中ρ-支配輪廓[20]) 給定一個(gè)數(shù)據(jù)流P、滑動(dòng)窗口大小N和一個(gè)查詢點(diǎn)q，則數(shù)據(jù)流上位于滑動(dòng)窗口的數(shù)據(jù)集PN中不被其他任何點(diǎn)ρ-支配的點(diǎn)構(gòu)成數(shù)據(jù)流中ρ-支配輪廓。

定義4(數(shù)據(jù)流中n-of-Nρ-支配輪廓) 給定一個(gè)數(shù)據(jù)流P、滑動(dòng)窗口大小N和一個(gè)查詢點(diǎn)q，則滑動(dòng)窗口PN中最近的n(n≤N)個(gè)點(diǎn)中不被滑動(dòng)窗口中其他任何點(diǎn)關(guān)于查詢點(diǎn)qρ-支配的點(diǎn)構(gòu)成數(shù)據(jù)流中n-of-Nρ-支配輪廓。

數(shù)據(jù)流中最近的N組多維數(shù)據(jù)點(diǎn)即為滑動(dòng)窗口中的點(diǎn)，而最近的n組多維數(shù)據(jù)點(diǎn)為滑動(dòng)窗口中的部分點(diǎn)。由定義4可知，數(shù)據(jù)流中n-of-Nρ-支配輪廓點(diǎn)只可能在滑動(dòng)窗口中最近的n組數(shù)據(jù)點(diǎn)中產(chǎn)生，因此可以將滑動(dòng)窗口中的N個(gè)數(shù)據(jù)點(diǎn)分為兩部分。如圖3所示，其中編號(hào)[N-n+1,N]的數(shù)據(jù)點(diǎn)是最近的n組數(shù)據(jù)點(diǎn)稱為有效部分，編號(hào)[1,N-n]的數(shù)據(jù)點(diǎn)為其余N-n組數(shù)據(jù)點(diǎn)稱為無(wú)效部分。對(duì)于一個(gè)剛剛到達(dá)滑動(dòng)窗口的數(shù)據(jù)點(diǎn)p來(lái)說(shuō)，由于點(diǎn)p為最近的一個(gè)點(diǎn)，所以點(diǎn)p一定位于滑動(dòng)窗口的有效部分。由定義3和定義4可以看出，數(shù)據(jù)流中ρ-支配輪廓是數(shù)據(jù)流中n-of-Nρ-支配輪廓當(dāng)n=N時(shí)的特例。另一種特例為n=1時(shí)，代表的是僅僅考慮最新的數(shù)據(jù)點(diǎn)是否為關(guān)鍵數(shù)據(jù)，如果是則傳輸給數(shù)據(jù)應(yīng)用方，如果不是則不傳輸。因此數(shù)據(jù)流中n-of-Nρ-支配輪廓是數(shù)據(jù)流中ρ-支配輪廓的擴(kuò)展，相比于ρ-支配輪廓擁有更廣泛的應(yīng)用。

圖3 n-of-N中滑動(dòng)窗口劃分Fig.3 Partition of sliding window in n-of-N

由于王之瓊等[20]給出的ρ-支配關(guān)系的性質(zhì)是在ρ≥1時(shí)并且以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)來(lái)進(jìn)行的，因此不適用于本文的相關(guān)研究。本文以“大于”為關(guān)鍵的標(biāo)準(zhǔn)并且在ρ>0時(shí)重新對(duì)ρ-支配關(guān)系的性質(zhì)進(jìn)行討論。

定理1給定兩個(gè)值ρ1和ρ2并且ρ1<ρ2，如果一個(gè)多維數(shù)據(jù)點(diǎn)p是ρ1-支配輪廓點(diǎn)，那么點(diǎn)p一定也是ρ2-支配輪廓點(diǎn)。

證明：定理1采用反證法，假設(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]|，

(5)

?i∈[1,d],(x[i]-q[i])(p[i]-q[i])>0∧
|x[i]-q[i]|>ρ2×|p[i]-q[i]|,

(6)

又由于ρ1<ρ2，因此

?i∈[1,d],(x[i]-q[i])(p[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ1×|p[i]-q[i]|，

(7)

?i∈[1,d],(x[i]-q[i])(p[i]-q[i])>0∧
|x[i]-q[i]|>ρ1×|p[i]-q[i]|.

(8)

由(7)式和(8)式可得點(diǎn)xρ1-支配點(diǎn)p，與已知條件p是ρ1-支配輪廓點(diǎn)存在矛盾，所以數(shù)據(jù)點(diǎn)p一定是ρ2-支配輪廓點(diǎn)。

定理1的證明過(guò)程與數(shù)據(jù)流中ρ-支配輪廓查詢算法[20]的證明思路類似，但是結(jié)論正好相反。由定理1可以看出以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)時(shí)，如果一點(diǎn)是較小ρ值的ρ-支配輪廓點(diǎn)，也必將是較大ρ值的ρ-支配輪廓點(diǎn)。

定理2給定數(shù)據(jù)流中的兩組多維數(shù)據(jù)點(diǎn)x和y，如果點(diǎn)yρ-支配點(diǎn)x并且L(x)

證明：由于點(diǎn)yρ-支配點(diǎn)x，所以當(dāng)y屬于滑動(dòng)窗口時(shí)點(diǎn)x不是ρ-支配輪廓點(diǎn)。又由于L(x)

定理3如果ρ≥1并且點(diǎn)xρ-支配點(diǎn)y以及點(diǎn)yρ-支配點(diǎn)z,則點(diǎn)xρ-支配點(diǎn)z.

證明：由點(diǎn)xρ-支配點(diǎn)y可得

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ×|y[i]-q[i]|，

(9)

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])>0∧
|x[i]-q[i]|>ρ×|y[i]-q[i]|.

(10)

由點(diǎn)yρ-支配點(diǎn)z可得

?i∈[1,d],(y[i]-q[i])(z[i]-q[i])≥0∧
|y[i]-q[i]|≥ρ×|z[i]-q[i]|，

(11)

?i∈[1,d],(y[i]-q[i])(z[i]-q[i])>0∧
|y[i]-q[i]|>ρ×|z[i]-q[i]|.

(12)

由(9)式乘以(11)式、(10)式乘以(12)式分別可得

?i∈[1,d],(x[i]-q[i])(y[j]-q[i])2(z[i]-
q[i])≥0∧|x[i]-q[i]|≥ρ2×|z[i]-q[i]|，

(13)

?i∈[1,d],(x[i]-q[i])(y[i]-q[i])2(z[i]-
q[i])>0∧|x[i]-q[i]|>ρ2×|z[i]-q[i]|.

(14)

又由于(y[i]-q[i])2≥0并且ρ2>ρ，所以

?i∈[1,d],(x[i]-q[i])(z[i]-q[i])≥0∧
|x[i]-q[i]|≥ρ×|z[i]-q[i]|，

(15)

?i∈[1,d],(x[i]-q[i])(z[i]-q[i])>0∧
|x[i]-q[i]|>ρ×|z[i]-q[i]|.

(16)

由(15)式和(16)式可以得出點(diǎn)xρ-支配點(diǎn)y.

從定理3可以看出，以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)，在ρ≥1時(shí)ρ-支配關(guān)系具有傳遞性，而在以“小于”作為關(guān)鍵的標(biāo)準(zhǔn)時(shí)不具有此性質(zhì)。

定理4當(dāng)ρ<1時(shí)，給定兩個(gè)點(diǎn)x和y并且x完全支配y，則xρ-支配y.

由于定理4的證明過(guò)程與定理1的證明過(guò)程類似，所以此處不再累述。

定理5如果ρ<1并且xρ-支配y以及y完全支配z,則xρ-支配z.

由于定理5與定理3的證明過(guò)程類似，所以此處不再累述。

3 數(shù)據(jù)流中ρ-支配輪廓和n-of-Nρ-支配輪廓

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

當(dāng)ρ≥1時(shí)，由定理3可知ρ-支配關(guān)系具有傳遞性，因此如果一點(diǎn)x被點(diǎn)yρ-支配，則被點(diǎn)xρ-支配的點(diǎn)一定被點(diǎn)yρ-支配。因此如果滑動(dòng)窗口中的一個(gè)點(diǎn)x被后到達(dá)的另一個(gè)點(diǎn)yρ-支配，則點(diǎn)x不可能影響其他點(diǎn)是否為ρ-支配輪廓點(diǎn)。同時(shí)由定理2可得，如果滑動(dòng)窗口中的一個(gè)點(diǎn)x被后到達(dá)的另一個(gè)點(diǎn)yρ-支配，則點(diǎn)x不可能成為ρ-支配輪廓點(diǎn)。綜上可以得出被后到達(dá)的點(diǎn)ρ-支配的點(diǎn)不可能成為ρ-支配輪廓點(diǎn)并且對(duì)其他點(diǎn)是否為ρ-支配輪廓點(diǎn)不產(chǎn)生影響。因此可以將滑動(dòng)窗口中被后到達(dá)的點(diǎn)ρ-支配的點(diǎn)在ρ-支配輪廓計(jì)算之前過(guò)濾掉。用SN表示滑動(dòng)窗口中過(guò)濾后點(diǎn)的集合，則SN中不包含被后到的點(diǎn)ρ-支配的點(diǎn)。由于要求計(jì)算出的結(jié)果是不被其他任意點(diǎn)ρ-支配的點(diǎn)的集合，因此可以將這些點(diǎn)分為一類，稱之為ρ-支配輪廓集合。SN中除了ρ-支配輪廓集合之外，還包含被先到達(dá)的點(diǎn)ρ-支配而不被后到達(dá)的點(diǎn)ρ-支配的點(diǎn)的集合，由于是被先到達(dá)的點(diǎn)ρ-支配，因此當(dāng)ρ-支配它的點(diǎn)流出滑動(dòng)窗口時(shí)，這些點(diǎn)有可能成為ρ-支配輪廓點(diǎn)，所以稱之為候選集合。綜上所述，在ρ≥1可以將SN分為兩類：

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

2) 候選集合CN：SN中不被后到達(dá)的點(diǎn)ρ-支配但是被先到達(dá)的點(diǎn)ρ-支配的點(diǎn)的集合。

從ρ≥1時(shí)的數(shù)據(jù)過(guò)濾方法和數(shù)據(jù)分類方法可以看出，ρ≥1時(shí)滑動(dòng)窗口中數(shù)據(jù)過(guò)濾方式及集合劃分方式與以“小于”作為關(guān)鍵標(biāo)準(zhǔn)時(shí)不同，以“小于”作為關(guān)鍵標(biāo)準(zhǔn)時(shí)過(guò)濾掉的為被后到的點(diǎn)完全支配的點(diǎn)的集合，同時(shí)將滑動(dòng)窗口中的數(shù)據(jù)分為了3類。

當(dāng)ρ<1時(shí)，由定理2可知，如果滑動(dòng)窗口中的一個(gè)點(diǎn)x被后到達(dá)的另一個(gè)點(diǎn)yρ-支配，則點(diǎn)x不可能成為ρ-支配輪廓點(diǎn)；然而，如果滑動(dòng)窗口中的一個(gè)點(diǎn)x被后到達(dá)的另一個(gè)點(diǎn)yρ-支配，則點(diǎn)x不一定不影響其他的點(diǎn)是否為ρ-支配輪廓點(diǎn)，如圖4所示，圖中的數(shù)據(jù)點(diǎn)按照點(diǎn)a最先到達(dá)，b其次到達(dá)，c最后到達(dá)，并且ρ值取0.5，某個(gè)時(shí)刻點(diǎn)c剛剛到達(dá)滑動(dòng)窗口且點(diǎn)a和點(diǎn)b沒(méi)有滑出滑動(dòng)窗口。圖4中點(diǎn)a′與點(diǎn)q的距離為點(diǎn)a與點(diǎn)q距離的2倍，點(diǎn)b′與點(diǎn)q的距離為點(diǎn)b與點(diǎn)q距離的2倍。從圖4中可以看出：當(dāng)ρ值為0.5時(shí)，點(diǎn)a的ρ-支配區(qū)域?yàn)辄c(diǎn)a′與點(diǎn)q形成的區(qū)域，點(diǎn)b的ρ-支配區(qū)域?yàn)辄c(diǎn)b′與點(diǎn)q形成的區(qū)域，由于數(shù)據(jù)點(diǎn)bρ-支配數(shù)據(jù)點(diǎn)a，所以數(shù)據(jù)點(diǎn)a不是ρ-支配輪廓點(diǎn)；按照ρ≥1時(shí)的數(shù)據(jù)過(guò)濾方法則將點(diǎn)a過(guò)濾掉，假如將數(shù)據(jù)點(diǎn)a過(guò)濾掉，由于點(diǎn)c不被點(diǎn)bρ-支配，因此點(diǎn)c為ρ-支配輪廓點(diǎn)。但是從圖4中可以看出點(diǎn)c被點(diǎn)aρ-支配，因此點(diǎn)c不是ρ-支配輪廓點(diǎn)，因此不能像ρ≥1時(shí)對(duì)滑動(dòng)窗口中的數(shù)據(jù)進(jìn)行過(guò)濾。

圖4 ρ<1時(shí)過(guò)濾錯(cuò)誤示例Fig.4 Example of filtering error for ρ<1

由定理2、定理4、定理5可得，如果滑動(dòng)窗口中的一個(gè)點(diǎn)x被后到達(dá)的另一個(gè)點(diǎn)y完全支配，則點(diǎn)x被點(diǎn)yρ-支配并且點(diǎn)x不可能影響其他的點(diǎn)是否為ρ-支配輪廓點(diǎn)。綜上可以得出被后到達(dá)的點(diǎn)完全支配的點(diǎn)不可能成為ρ-支配輪廓點(diǎn)并且對(duì)其他點(diǎn)是否為ρ-支配輪廓點(diǎn)不產(chǎn)生影響。因此可以將滑動(dòng)窗口中被后到達(dá)的點(diǎn)完全支配的點(diǎn)在ρ-支配輪廓計(jì)算之前過(guò)濾掉，同樣用SN表示滑動(dòng)窗口中過(guò)濾后點(diǎn)的集合。當(dāng)ρ≥1時(shí)，將SN分成了DN和CN，DN為不被任何數(shù)據(jù)點(diǎn)ρ-支配的點(diǎn)的集合，CN為被先到的數(shù)據(jù)點(diǎn)ρ-支配但是不被后到的數(shù)據(jù)點(diǎn)ρ-支配的點(diǎn)的集合。但是當(dāng)ρ<1時(shí)，由于過(guò)濾掉的是被后到的點(diǎn)完全支配的點(diǎn)的集合，因此除了以上兩類集合之外，SN中還有一些點(diǎn)是被后到的點(diǎn)ρ-支配而不被后到的點(diǎn)完全支配，這些點(diǎn)不可能成為ρ-支配輪廓點(diǎn)，因此將此類點(diǎn)稱之為輔助集合。綜上所述，當(dāng)ρ<1時(shí)，可以將SN分為3類：

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

2) 候選集合CN：SN中不被后到的點(diǎn)ρ-支配但是被先到的點(diǎn)ρ-支配的點(diǎn)的集合；

3) 輔助集合AN：SN中不被后到的點(diǎn)完全支配但是被后到的點(diǎn)ρ-支配的點(diǎn)的集合。

從上述對(duì)數(shù)據(jù)流中ρ-支配輪廓查詢的數(shù)據(jù)過(guò)濾和數(shù)據(jù)分類方法可以看出，以“大于”作為關(guān)鍵標(biāo)準(zhǔn)當(dāng)ρ<1時(shí)的數(shù)據(jù)過(guò)濾和分類方法與數(shù)據(jù)流中ρ-支配輪廓查詢算法[20]中當(dāng)ρ≥1時(shí)的數(shù)據(jù)過(guò)濾和分類方法類似，而以“大于”作為關(guān)鍵標(biāo)準(zhǔn)當(dāng)ρ≥1時(shí)無(wú)相關(guān)方法。

在此基礎(chǔ)上，本文對(duì)數(shù)據(jù)流中ρ-支配輪廓查詢算法進(jìn)行了更改和擴(kuò)展，算法1使用偽代碼描述了數(shù)據(jù)流中ρ-支配輪廓計(jì)算的過(guò)程(見(jiàn)表1)。當(dāng)數(shù)據(jù)流中有新數(shù)據(jù)點(diǎn)p到達(dá)滑動(dòng)窗口時(shí)：首先判斷滑動(dòng)窗口是否已滿，如果是則先刪除滑動(dòng)窗口中最先到達(dá)的數(shù)據(jù)，并且將被刪除的點(diǎn)ρ-支配的點(diǎn)從候選集移動(dòng)到ρ-支配輪廓集；然后將點(diǎn)p插入到相應(yīng)的空間區(qū)域中，在點(diǎn)p所屬的區(qū)域中查找出被點(diǎn)pρ-支配的集合DS，如果ρ≥1或者點(diǎn)p完全支配DS中的點(diǎn)則刪除，否則從ρ-支配輪廓集和候選集中移動(dòng)到輔助集中；最后判斷是否有其他的點(diǎn)ρ-支配點(diǎn)p，如果有則將p加入到候選集，否則加入到ρ-支配輪廓集。

表1 算法1：數(shù)據(jù)流中ρ-支配輪廓查詢Tab.1 Algorithm 1:ρ-dominant skyline query in data stream

3.2 數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢

同3.1節(jié)所描述的一樣，用SN表示滑動(dòng)窗口中進(jìn)行數(shù)據(jù)過(guò)濾后的集合，由于當(dāng)ρ≥1時(shí)ρ-支配關(guān)系和ρ-支配輪廓的性質(zhì)與前面所述的性質(zhì)沒(méi)有改變，所以被后到的點(diǎn)ρ-支配的點(diǎn)不可能成為ρ-支配輪廓點(diǎn)并且對(duì)其他點(diǎn)是否是ρ-支配輪廓點(diǎn)不產(chǎn)生影響，因此可以在n-of-Nρ-支配輪廓計(jì)算之前過(guò)濾掉，因此可得SN為不被后到的點(diǎn)ρ-支配的點(diǎn)的集合。在前面敘述中將不被其他點(diǎn)ρ-支配的點(diǎn)稱之為ρ-支配輪廓點(diǎn)，然而在n-of-Nρ-支配輪廓計(jì)算時(shí)，有些數(shù)據(jù)點(diǎn)雖然不被其他任意點(diǎn)ρ-支配，但由于位于滑動(dòng)窗口的無(wú)效部分中，仍然不是ρ-支配輪廓點(diǎn)。通過(guò)n-of-Nρ-支配輪廓的定義可以得到n-of-Nρ-支配輪廓點(diǎn)只可能存在于滑動(dòng)窗口的有效部分，因此將滑動(dòng)窗口中有效部分不被其他任意點(diǎn)ρ-支配的點(diǎn)組成的集合稱之為n-of-Nρ-支配輪廓集?；瑒?dòng)窗口的有效部分除了n-of-Nρ-支配輪廓集之外，還包含被先到的點(diǎn)ρ-支配的點(diǎn)，由于這些點(diǎn)以后可能成為n-of-Nρ-支配輪廓點(diǎn)，因此將此部分點(diǎn)構(gòu)成的集合稱之為候選集。由于滑動(dòng)窗口中無(wú)效部分的數(shù)據(jù)點(diǎn)永遠(yuǎn)不可能成為n-of-Nρ-支配輪廓點(diǎn)，但是可能影響其他點(diǎn)是否為n-of-Nρ-支配輪廓點(diǎn)，因此將無(wú)效部分沒(méi)有被過(guò)濾掉的點(diǎn)組成的集合稱之為輔助集。綜上所述，可以將SN分為3類：

1)n-of-Nρ-支配輪廓集合DN：SN中處于有效部分內(nèi)并且不被其他任何點(diǎn)ρ-支配的點(diǎn)的集合；

2) 候選集合CN：SN中處于有效部分內(nèi)并且不被滑動(dòng)窗口中后到的點(diǎn)ρ-支配但是被先到的點(diǎn)ρ-支配的點(diǎn)的集合；

3) 輔助集合AN：SN中處于無(wú)效部分點(diǎn)的集合。

當(dāng)ρ<1時(shí)，由于與ρ≥1時(shí)滿足不同的性質(zhì)，所以當(dāng)ρ<1時(shí)存在不同的數(shù)據(jù)過(guò)濾方式。同樣用SN表示滑動(dòng)窗口中進(jìn)行數(shù)據(jù)過(guò)濾后的集合，采用3.1節(jié)所述的同樣數(shù)據(jù)過(guò)濾方式，將滑動(dòng)窗口中被后到達(dá)的點(diǎn)完全支配的點(diǎn)在n-of-Nρ-支配輪廓計(jì)算之前過(guò)濾掉，則可得SN為不被后到的點(diǎn)完全支配的點(diǎn)的集合。由于過(guò)濾掉的是被后到的點(diǎn)完全支配的點(diǎn)的集合，因此在滑動(dòng)窗口的有效部分除了n-of-Nρ-支配輪廓集和候選集之外，還存在著被后到的點(diǎn)ρ-支配但是不被后到的點(diǎn)完全支配的點(diǎn)組成的集合。由于這部分點(diǎn)只是影響其他點(diǎn)是否為n-of-Nρ-支配輪廓點(diǎn)，并不可能成為n-of-Nρ-支配輪廓點(diǎn)，所以將這部分加入到輔助集合中。因此，滑動(dòng)窗口中的數(shù)據(jù)點(diǎn)仍然可以分為3部分，只是3部分所包含的數(shù)據(jù)點(diǎn)與ρ≥1時(shí)有所不同。當(dāng)ρ<1時(shí)，對(duì)SN的分類方法如下所示：

1)n-of-Nρ-支配輪廓集合DN:SN中處于有效部分內(nèi)并且不被其他任何點(diǎn)ρ-支配的點(diǎn)的集合；

2) 候選集合CN:SN中處于有效部分內(nèi)并且不被滑動(dòng)窗口中后到的點(diǎn)ρ-支配但是被先到的點(diǎn)ρ-支配的點(diǎn)的集合；

3) 輔助集合AN:SN中處于無(wú)效部分的點(diǎn)和有效部分中被后到的點(diǎn)ρ-支配但是不被后到的點(diǎn)完全支配的點(diǎn)的集合。

在此基礎(chǔ)上，對(duì)數(shù)據(jù)流中n-of-Nρ-支配輪廓的計(jì)算過(guò)程給出了偽碼描述如算法2所示(見(jiàn)表2)。當(dāng)數(shù)據(jù)流中有新數(shù)據(jù)點(diǎn)p到達(dá)滑動(dòng)窗口時(shí)：首先判斷滑動(dòng)窗口是否已滿，如果是則先刪除滑動(dòng)窗口中最先到達(dá)的數(shù)據(jù)；然后將點(diǎn)p插入到相應(yīng)的空間區(qū)域中；最后將n-of-Nρ-支配輪廓集返回給用戶。其中，滑動(dòng)窗口中最先到達(dá)的數(shù)據(jù)刪除用DeletePoint( )函數(shù)來(lái)表示，新到達(dá)的數(shù)據(jù)插入用InsertPoint( )函數(shù)表示。由算法的描述可以看出算法2的時(shí)間復(fù)雜度依賴DeletePoint( )函數(shù)和InsertPoint( )函數(shù)的時(shí)間復(fù)雜度，由于兩個(gè)函數(shù)的時(shí)間復(fù)雜度均為O(N)，所以算法2的時(shí)間復(fù)雜度為O(N)。

表2 算法2：數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢Tab.2 Algorithm 2:n-of-Nρ-dominant skyline query in data stream

算法3描述了在數(shù)據(jù)流中計(jì)算n-of-Nρ-支配輪廓時(shí)將滑動(dòng)窗口中最先到達(dá)的數(shù)據(jù)點(diǎn)p流出滑動(dòng)窗口的過(guò)程(見(jiàn)表3)。第1行描述的是根據(jù)點(diǎn)p在數(shù)據(jù)流中的編號(hào)查找點(diǎn)p；第3行描述了計(jì)算要?jiǎng)h除點(diǎn)p所屬的空間區(qū)域的過(guò)程，在算法中用RegionCalculation( )函數(shù)[20]來(lái)表示，RegionCalculation( )函數(shù)包含兩個(gè)參數(shù)，第一個(gè)為所要計(jì)算的點(diǎn)p在各維上的數(shù)值部分value，第二個(gè)為查詢點(diǎn)q；第4～12行描述了對(duì)于點(diǎn)p所屬的每一個(gè)空間區(qū)域R的處理過(guò)程；第5行描述的為在空間區(qū)域R中刪除點(diǎn)p；第6～11行描述了對(duì)于空間區(qū)域R中的每一個(gè)點(diǎn)x，如果點(diǎn)p為點(diǎn)x的前ρ-支配點(diǎn)并且點(diǎn)x屬于候選集合(第7行)，則將點(diǎn)x從候選集合移動(dòng)到n-of-Nρ-支配輪廓集合中(第8～9行)。通過(guò)算法描述可以看出DeletePoint( )函數(shù)外層循環(huán)為區(qū)域個(gè)數(shù)R=2d，內(nèi)層循環(huán)為滑動(dòng)窗口中所屬R的數(shù)據(jù)N/2d，因此函數(shù)時(shí)間復(fù)雜度為O(N)。

表3 算法3：滑動(dòng)窗口中數(shù)據(jù)刪除-DeletePoint( )Tab.3 Algorithm 3:data deletion in sliding window-DeletePoint( )

算法4描述了在數(shù)據(jù)流中計(jì)算n-of-Nρ-支配輪廓時(shí)將新到達(dá)的點(diǎn)p插入到滑動(dòng)窗口中的處理過(guò)程(見(jiàn)表4)。第1行通過(guò)調(diào)用RegionCalculation( )函數(shù)計(jì)算點(diǎn)p所屬的空間區(qū)域；第2～19行對(duì)于所屬的每一個(gè)區(qū)域進(jìn)行處理，其中第3～17行為對(duì)滑動(dòng)窗口中同一區(qū)域的其他數(shù)據(jù)進(jìn)行處理，第18行描述的為將點(diǎn)p插入到所在空間區(qū)域中；第4～6行描述的為對(duì)于點(diǎn)p所屬區(qū)域中的一個(gè)點(diǎn)x，判斷其是否ρ-支配點(diǎn)p并且比已經(jīng)ρ-支配點(diǎn)p的點(diǎn)編號(hào)大，如果是則更改點(diǎn)p的前ρ-支配點(diǎn)為x；第7～16行為討論點(diǎn)pρ-支配點(diǎn)x的情況，其中第8～10行描述的為如果點(diǎn)x屬于n-of-Nρ-支配輪廓集或者候選集并且位于滑動(dòng)窗口的有效部分，則在其所屬的集合中將其移除；第11～12行為討論點(diǎn)x是否符合過(guò)濾的要求，如果符合，則將點(diǎn)x過(guò)濾掉；第13～15行描述的為點(diǎn)x不符合過(guò)濾的條件，如果位于滑動(dòng)窗口的有效部分，則將點(diǎn)x轉(zhuǎn)換為輔助點(diǎn)；第20～23行描述了滑動(dòng)窗口的有效部分中最先到達(dá)的一個(gè)點(diǎn)之前如果沒(méi)有被過(guò)濾掉，則從滑動(dòng)窗口的有效部分轉(zhuǎn)移到無(wú)效部分；第24～28行描述的為如果點(diǎn)p在滑動(dòng)窗口中不被先到的點(diǎn)ρ-支配，則將點(diǎn)p加入到n-of-Nρ-支配輪廓集，否則將其加入到候選集中。通過(guò)算法描述可以看出InsertPoint( )函數(shù)外層循環(huán)為區(qū)域個(gè)數(shù)R=2d，內(nèi)層循環(huán)為滑動(dòng)窗口中所屬R的數(shù)據(jù)N/2d，因此函數(shù)時(shí)間復(fù)雜度為O(N)。

表4 算法4：滑動(dòng)窗口中新數(shù)據(jù)插入-InsertPoint( )Tab.4 Algorithm 4:new data insertion in slinding window-InsertPoint( )

4 實(shí)驗(yàn)說(shuō)明和實(shí)驗(yàn)方案

4.1 實(shí)驗(yàn)說(shuō)明

本節(jié)實(shí)驗(yàn)中，系統(tǒng)地測(cè)試了ρ值、滑動(dòng)窗口大小、維度對(duì)于計(jì)算時(shí)間和ρ-支配輪廓集大小的影響。由于每次滑動(dòng)窗口內(nèi)的數(shù)據(jù)統(tǒng)計(jì)可能存在差異，所以本節(jié)采用綜合滑動(dòng)窗口滑動(dòng)1 000次的情況，即統(tǒng)計(jì)ρ-支配輪廓集大小采用滑動(dòng)窗口滑動(dòng)1 000次過(guò)程中ρ-支配輪廓集大小的平均值，計(jì)算時(shí)間采用滑動(dòng)窗口滑動(dòng)1 000次過(guò)程中的計(jì)算時(shí)間總和。實(shí)驗(yàn)中所要考察的主要參數(shù)及其變化范圍和默認(rèn)值如表5所示，每次進(jìn)行實(shí)驗(yàn)只變化其中的一個(gè)參數(shù)，而其他參數(shù)設(shè)置為默認(rèn)值。

表5 實(shí)驗(yàn)參數(shù)變化范圍和默認(rèn)值Tab.5 Changing range and default values of parameters

實(shí)驗(yàn)數(shù)據(jù)為隨機(jī)生成的獨(dú)立分布數(shù)據(jù)，屬性包括裝甲車輛狀態(tài)的發(fā)動(dòng)機(jī)水溫、發(fā)動(dòng)機(jī)油壓、分動(dòng)箱溫度、電流、儲(chǔ)氣瓶氣壓、水上液壓油溫、變速箱油溫及發(fā)動(dòng)機(jī)轉(zhuǎn)速等，實(shí)驗(yàn)時(shí)隨機(jī)選擇其中的兩維或者多維。數(shù)據(jù)自動(dòng)生成時(shí)將數(shù)據(jù)限定在裝甲車輛的各屬性真實(shí)值域內(nèi)，其中發(fā)動(dòng)機(jī)水溫為-50～200 ℃，發(fā)動(dòng)機(jī)油壓為0～1 000 kPa，分動(dòng)箱溫度為0～150 ℃，電流為0～400 A，儲(chǔ)氣瓶氣壓為0～1.5 MPa，水上液壓油溫0～150 ℃，變速箱油溫為0～150 ℃，發(fā)動(dòng)機(jī)轉(zhuǎn)速0～3 000 r/min. 部分隨機(jī)生成數(shù)據(jù)如表6所示。

表6 實(shí)驗(yàn)數(shù)據(jù)示例Tab.6 Example of experimental data

本節(jié)使用C++語(yǔ)言實(shí)現(xiàn)了擴(kuò)展的數(shù)據(jù)流中ρ-支配輪廓查詢算法和數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢算法。實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i7-7700HQ CPU @2.80 GHz、8.00 G RAM內(nèi)存和64位Win10操作系統(tǒng)。

4.2 實(shí)驗(yàn)方案

4.2.1ρ值對(duì)算法的影響

本節(jié)測(cè)試了ρ值對(duì)于算法的影響。圖5顯示了ρ值對(duì)于輪廓集大小的影響，從中可以看出：隨著ρ值的增大輪廓集也變大，這是因?yàn)楫?dāng)ρ值增大時(shí)數(shù)據(jù)點(diǎn)所支配的面積變小，因此數(shù)據(jù)越難以被支配；但是無(wú)論ρ值如何變化，兩種算法的輪廓集都遠(yuǎn)遠(yuǎn)小于滑動(dòng)窗口大小，因此應(yīng)用于裝甲車輛狀態(tài)數(shù)據(jù)傳輸過(guò)程中所需傳輸?shù)臓顟B(tài)數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于原數(shù)據(jù)量；而且n-of-Nρ-支配輪廓查詢算法的輪廓集遠(yuǎn)遠(yuǎn)小于ρ-支配輪廓算法的輪廓集，因此在裝甲車輛狀態(tài)傳輸過(guò)程中所需傳輸?shù)臄?shù)據(jù)量更小。圖6顯示了ρ值對(duì)于計(jì)算時(shí)間的影響，從中可以看出：當(dāng)ρ<1時(shí)計(jì)算時(shí)間變化不大，當(dāng)ρ>1時(shí)計(jì)算時(shí)間隨著ρ值的增大而增大，這是由于當(dāng)ρ<1時(shí)過(guò)濾掉的為被后到的數(shù)據(jù)點(diǎn)完全支配的數(shù)據(jù)，因此過(guò)濾掉的數(shù)據(jù)相同；當(dāng)ρ>1時(shí)過(guò)濾掉的數(shù)據(jù)為被后到的數(shù)據(jù)點(diǎn)ρ-支配的數(shù)據(jù)，隨著ρ增大，過(guò)濾掉的數(shù)據(jù)減少，因此計(jì)算時(shí)間變長(zhǎng)；無(wú)論ρ值如何變化，兩種ρ-支配輪廓算法的計(jì)算時(shí)間相差不大。

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

圖6 ρ值對(duì)計(jì)算時(shí)間的影響Fig.6 Effect of ρ on computing time

4.2.2 滑動(dòng)窗口大小對(duì)算法的影響

本節(jié)測(cè)試了滑動(dòng)窗口大小對(duì)于算法的影響。圖7為滑動(dòng)窗口大小對(duì)于輪廓集大小的影響，從中可以看出：隨著滑動(dòng)窗口的增大輪廓集也變大；但是無(wú)論怎樣變化，輪廓集都遠(yuǎn)遠(yuǎn)小于滑動(dòng)窗口的大小，因此在裝甲車輛狀態(tài)數(shù)據(jù)傳輸過(guò)程中應(yīng)用ρ-支配輪廓查詢算法或者n-of-Nρ-支配輪廓查詢算法后所需傳輸?shù)臓顟B(tài)數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于原數(shù)據(jù)量；而且n-of-Nρ-支配輪廓查詢算法的輪廓集遠(yuǎn)遠(yuǎn)小于ρ-支配輪廓算法的輪廓集，因此應(yīng)用n-of-Nρ-支配輪廓查詢算法所需傳輸?shù)臓顟B(tài)數(shù)據(jù)量更小。圖8為滑動(dòng)窗口大小對(duì)于計(jì)算時(shí)間的影響，從中可以看出：隨著滑動(dòng)窗口的增大計(jì)算時(shí)間也變大，這是由于隨著滑動(dòng)窗口的增大，所需計(jì)算的數(shù)據(jù)量變大，因而導(dǎo)致計(jì)算時(shí)間增大，但是無(wú)論滑動(dòng)窗口如何變化，兩種算法的計(jì)算時(shí)間基本一致。

圖7 滑動(dòng)窗口對(duì)輪廓集大小的影響Fig.7 Effect of sliding window on skyline size

圖8 滑動(dòng)窗口對(duì)計(jì)算時(shí)間的影響Fig.8 Effect of sliding window on computing time

4.2.3 維度對(duì)算法的影響

本節(jié)測(cè)試了裝甲車輛狀態(tài)數(shù)據(jù)的維度對(duì)于算法的影響。圖9顯示了輪廓集大小隨著數(shù)據(jù)維度的變化情況，從中可以看出：狀態(tài)數(shù)據(jù)的維度越大輪廓集越大，這是由于當(dāng)維度增大時(shí)數(shù)據(jù)被支配的概率降低，從而使得數(shù)據(jù)成為輪廓點(diǎn)的概率增加，但是不管維度如何變化，輪廓集都遠(yuǎn)遠(yuǎn)小于滑動(dòng)窗口大小，因此應(yīng)用于裝甲車輛狀態(tài)數(shù)據(jù)傳輸過(guò)程中所需傳輸?shù)臓顟B(tài)數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于原數(shù)據(jù)量；而且n-of-Nρ-支配輪廓查詢算法的輪廓集遠(yuǎn)遠(yuǎn)小于ρ-支配輪廓算法的輪廓集，因此在裝甲車輛狀態(tài)傳輸過(guò)程中所需傳輸?shù)臄?shù)據(jù)量更小。圖10顯示了計(jì)算時(shí)間隨著維度的變化情況，從中可以看出：計(jì)算時(shí)間隨著維度的變大而變大，這是由于當(dāng)維度變大時(shí)，需要計(jì)算的數(shù)值增多，從而計(jì)算時(shí)間變大。

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

圖10 維度對(duì)計(jì)算時(shí)間的影響Fig.10 Effect of dimension on computing time

4.2.4 滑動(dòng)窗口有效部分大小對(duì)算法的影響

最后，測(cè)試滑動(dòng)窗口有效部分大小對(duì)于輪廓集大小的影響。圖11顯示了n-of-Nρ-支配輪廓集隨著滑動(dòng)窗口有效部分增加而增大。這是由于只有位于滑動(dòng)窗口中有效部分的數(shù)據(jù)點(diǎn)才可能成為n-of-Nρ-支配輪廓點(diǎn)，雖然整個(gè)滑動(dòng)窗口的大小保持不變，但是滑動(dòng)窗口中的有效部分所占的比例增大，所以滑動(dòng)窗口中產(chǎn)生輪廓集的區(qū)間變大，因此相應(yīng)的n-of-Nρ-支配輪廓集變大，進(jìn)而通過(guò)調(diào)節(jié)滑動(dòng)窗口有效部分的大小可以調(diào)整裝甲車輛狀態(tài)數(shù)據(jù)的傳輸量。

圖11 滑動(dòng)窗口有效部分大小對(duì)輪廓集大小的影響Fig.11 Effect of effectiveness portion of sliding window on skyline size

5 結(jié)論

在網(wǎng)絡(luò)時(shí)斷時(shí)續(xù)、網(wǎng)絡(luò)帶寬較小的網(wǎng)絡(luò)狀況受限情況下，采集的數(shù)據(jù)難以實(shí)時(shí)準(zhǔn)確地傳輸?shù)綌?shù)據(jù)應(yīng)用方，這嚴(yán)重制約著數(shù)據(jù)應(yīng)用方利用數(shù)據(jù)對(duì)當(dāng)前態(tài)勢(shì)進(jìn)行評(píng)判。本文以裝甲車輛狀態(tài)數(shù)據(jù)傳輸應(yīng)用為出發(fā)點(diǎn)，以“大于”作為關(guān)鍵的標(biāo)準(zhǔn)，重新對(duì)ρ-支配關(guān)系和ρ-支配輪廓進(jìn)行討論，并對(duì)數(shù)據(jù)流中的ρ-支配輪廓查詢算法進(jìn)行更改和擴(kuò)展，用來(lái)滿足裝甲車輛狀態(tài)數(shù)據(jù)傳輸問(wèn)題的需要；更進(jìn)一步，對(duì)數(shù)據(jù)流中ρ-支配輪廓查詢算法進(jìn)行擴(kuò)展，提出了數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢算法，進(jìn)一步滿足網(wǎng)絡(luò)受限環(huán)境中裝甲車輛狀態(tài)關(guān)鍵數(shù)據(jù)選擇傳輸?shù)囊?；最后?duì)算法進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)表明改進(jìn)的數(shù)據(jù)流中ρ-支配輪廓查詢算法以及數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢算法能夠計(jì)算出數(shù)據(jù)流中的關(guān)鍵數(shù)據(jù)，對(duì)于網(wǎng)絡(luò)受限情況下裝甲車輛狀態(tài)數(shù)據(jù)傳輸起到重要的作用，并且數(shù)據(jù)流中n-of-Nρ-支配輪廓查詢相比于數(shù)據(jù)流中ρ-支配輪廓查詢具有更廣泛的應(yīng)用，更適合應(yīng)用于裝甲車輛狀態(tài)數(shù)據(jù)選擇傳輸過(guò)程中。

參考文獻(xiàn)(References)

[1] TATBUL N,ETINTEMEL U,ZDONIK SB,et al.Load shedding in a data stream manager[C]∥Proceedings of the 29th International Conference on Very Large Data Bases.Berlin,Germany:VLDBEndowment,2003:309-320.

[2] DE ASSUNCAO M D,VEITH A D S,BUYYA R.Distributed data stream processing and edge computing:asurvey on resource elasticity and future directions[J].Journal of Network &Computer Applications,2018,103:1-17.

[3] BORZSONY S,KOSSMANN D,STOCKER K.The skyline operator [C]∥Proceedings of 17th International Conference on Data Engineering.Heidelberg,Germany:IEEE,2001:421-430.

[4] PAPADIAS D,TAO Y F,FU G,et al.An optimal and progressive algorithm for skyline queries[C]∥Proceedings of the 2003 ACMSIGMOD International Conference on Management of Data.San Diego,CA,US:ACM,2003:467-478.

[5] DING L L,XIN J C,WANG G R,et al.Efficient skyline query processing of massive data based on map-reduce[J].Chinese Journal of Computers,2011,34(10):1785-1796.

[6] 余靖,劉盼盼.MapReduce框架下k-支配輪廓查詢算法[J].燕山大學(xué)學(xué)報(bào),2014,38(6):532-537.

YU J,LIU P P.k-dominant skyline query algorithm based on Map Reduce framework[J].Journal of Yanshan University,2014,38(6):532-537.(in Chinese)

[7] LAI C C,AKBAR Z F,LIU C M,et al.Distributed continuous range-skyline query monitoring over the internet of mobile things[J].IEEE Internet of Things Journal,2019,6(4):6652-6667.

[8] TIAN H,SIDDIQUE M A,MORIMOTO Y,et al.An efficient processing ofk-dominant skyline query in MapReduce[C]∥Proceedings of International Workshop on Bringing the Value of Big Data to Users.Hangzhou,China:ACM,2014:29-34.

[9] ZHENG B,LEE K C,LEE W C.Location-dependent skyline query[C]∥Proceedings of International Conference on Mobile Data Management.Beijing,China:IEEE,2008:148-155.

[10] LIU X,YANG D N,YE M,et al.U-Skyline:a new skyline query for uncertain databases[J].IEEE Transactions on Know-ledge and Data Engineering,2013,25(4):945-960.

[11] REN W L,LIAN X,GHAZINOUR K.Skyline queries over incomplete data streams[J].The VLDB Journal,2019,28(6):961-985.

[12] XIE M,WONG C W,LAL L A.An experimental survey of regret minimization query and variants:bridging the best worlds between top-k query and skyline query[J].The VLDB Journal,2020,29(1):147-175.

[13] CHEN L,LIAN X.Dynamic skyline queries in metric spaces[C] ∥Proceedings of the 11th International Conference on Extending Database Technology:Advances in Database Technology.Nantes,France:ACM,2008:333-343.

[14] 周劍剛,秦小麟,張珂珩,等.基于道路網(wǎng)的多移動(dòng)用戶動(dòng)態(tài)Skyline查詢[J].計(jì)算機(jī)科學(xué),2019,46 (9):73-78.

ZHOU J G,QIN X L,ZHANF K H,et al.Dynamic skyline query for multiple mobile users based on road network[J].Computer Science,2019,46 (9):73-78.(in Chinese)

[15] ZOU L,CHEN L,?ZSU M T,et al.Dynamic skyline queries in large graphs[C]∥Proceedings of International Conference on Database Systems for Advanced Applications.Tsukuba,Japan:Springer,2010:62-78.

[16] LI H,YOO J.An efficient scheme for continuous skyline query processing over dynamic data set[C]∥Proceedings of 2014 International Conference on Big Data and Smart Computing.Bangkok,Thailand:IEEE,2014:1197-1206.

[17] 張麗，鄒鵬，賈焰，等.數(shù)據(jù)流上連續(xù)動(dòng)態(tài)skyline查詢研究[J].計(jì)算機(jī)研究與發(fā)展，2015,48(1):77-85.

ZHANG L,ZOU P,JIA Y,et al.Continuous dynamic skyline queries over data stream[J].Journal of Computer Research and Development,2015,48(1):77-85.(in Chinese)

[18] BAI M,XIN J C,WANG G R,et al.Research on dynamic skyline query processing over data streams[J].Chinese Journal of Computers,2011,34(10):1876-1884.

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

XIN J C,BAI M,DONG H,et al.An efficient processing algorithm forρ-dominant skyline query[J].Chinese Journal of Computers,2011,34(10):1876-1884.(in Chinese)

[20] 王之瓊,霸建民,黃達(dá),等.數(shù)據(jù)流中ρ-支配輪廓查詢算法[J].計(jì)算機(jī)科學(xué)與探索,2017,11(7):1080-1091.

WANG Z Q,BA J M,HUANG D,et al.ρ-dominant skyline computation on data streams[J].Journal of Frontiers of Computer Science and Technology,2017,11(7):1080-1091.(in Chinese)