基于ρ-支配輪廓及n-of-Nρ-支配輪廓的數(shù)據(jù)流中關(guān)鍵數(shù)據(jù)計算方法

霸建民，郭永紅，彭龍，趙東陽，邵鵬志，杜宏博

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

0 引言

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

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

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

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

傳統(tǒng)輪廓查詢中的支配關(guān)系都是依賴于多維數(shù)據(jù)對應(yīng)數(shù)值之間的大小關(guān)系而進(jìn)行設(shè)計的，均沒有考慮數(shù)值間的比例關(guān)系。然而，在一些實際應(yīng)用中，數(shù)值間的大小關(guān)系并不能完全說明兩組數(shù)據(jù)誰更關(guān)鍵，這時就需要使用數(shù)值間的比例關(guān)系進(jìn)行關(guān)鍵數(shù)據(jù)選擇。例如，某型裝甲車的標(biāo)準(zhǔn)油壓和水溫為20 kPa和20 ℃，而某一個裝甲車有兩組狀態(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)系時，在油壓維度上狀態(tài)A的偏離值比狀態(tài)B的偏離值小5 kPa，而在水溫維度上狀態(tài)A的偏離值比狀態(tài)B的偏離值大5 ℃，因此不能決定狀態(tài)A和狀態(tài)B哪個更關(guān)鍵。這時可以考慮基于數(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ù)值不在同一量級時，基于對應(yīng)數(shù)值間比例的支配關(guān)系更能計算出關(guān)鍵數(shù)據(jù)。將對應(yīng)數(shù)值間的比值稱之為ρ，因此基于對應(yīng)數(shù)值間比例的支配關(guān)系也稱之為ρ-支配關(guān)系,在此基礎(chǔ)上的輪廓查詢稱之為ρ-支配輪廓[19]查詢。

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

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

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

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

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

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

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

2 ρ-支配理論

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

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

?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(ρ-支配) 一個多維數(shù)據(jù)點x關(guān)于查詢點qρ-支配另一個多維數(shù)據(jù)點y當(dāng)且僅當(dāng)滿足以下兩個條件：

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

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

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

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

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

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

圖3 n-of-N中滑動窗口劃分Fig.3 Partition of sliding window in n-of-N

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

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

證明：定理1采用反證法，假設(shè)點p不是ρ2-支配輪廓點，則存在另一點xρ2-支配點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)式可得點xρ1-支配點p，與已知條件p是ρ1-支配輪廓點存在矛盾，所以數(shù)據(jù)點p一定是ρ2-支配輪廓點。

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

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

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

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

證明：由點xρ-支配點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)

由點yρ-支配點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)式可以得出點xρ-支配點y.

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

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

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

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

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

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

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

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

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

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

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

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

圖4 ρ<1時過濾錯誤示例Fig.4 Example of filtering error for ρ<1

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

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

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

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

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

在此基礎(chǔ)上，本文對數(shù)據(jù)流中ρ-支配輪廓查詢算法進(jìn)行了更改和擴(kuò)展，算法1使用偽代碼描述了數(shù)據(jù)流中ρ-支配輪廓計算的過程(見表1)。當(dāng)數(shù)據(jù)流中有新數(shù)據(jù)點p到達(dá)滑動窗口時：首先判斷滑動窗口是否已滿，如果是則先刪除滑動窗口中最先到達(dá)的數(shù)據(jù)，并且將被刪除的點ρ-支配的點從候選集移動到ρ-支配輪廓集；然后將點p插入到相應(yīng)的空間區(qū)域中，在點p所屬的區(qū)域中查找出被點pρ-支配的集合DS，如果ρ≥1或者點p完全支配DS中的點則刪除，否則從ρ-支配輪廓集和候選集中移動到輔助集中；最后判斷是否有其他的點ρ-支配點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表示滑動窗口中進(jìn)行數(shù)據(jù)過濾后的集合，由于當(dāng)ρ≥1時ρ-支配關(guān)系和ρ-支配輪廓的性質(zhì)與前面所述的性質(zhì)沒有改變，所以被后到的點ρ-支配的點不可能成為ρ-支配輪廓點并且對其他點是否是ρ-支配輪廓點不產(chǎn)生影響，因此可以在n-of-Nρ-支配輪廓計算之前過濾掉，因此可得SN為不被后到的點ρ-支配的點的集合。在前面敘述中將不被其他點ρ-支配的點稱之為ρ-支配輪廓點，然而在n-of-Nρ-支配輪廓計算時，有些數(shù)據(jù)點雖然不被其他任意點ρ-支配，但由于位于滑動窗口的無效部分中，仍然不是ρ-支配輪廓點。通過n-of-Nρ-支配輪廓的定義可以得到n-of-Nρ-支配輪廓點只可能存在于滑動窗口的有效部分，因此將滑動窗口中有效部分不被其他任意點ρ-支配的點組成的集合稱之為n-of-Nρ-支配輪廓集。滑動窗口的有效部分除了n-of-Nρ-支配輪廓集之外，還包含被先到的點ρ-支配的點，由于這些點以后可能成為n-of-Nρ-支配輪廓點，因此將此部分點構(gòu)成的集合稱之為候選集。由于滑動窗口中無效部分的數(shù)據(jù)點永遠(yuǎn)不可能成為n-of-Nρ-支配輪廓點，但是可能影響其他點是否為n-of-Nρ-支配輪廓點，因此將無效部分沒有被過濾掉的點組成的集合稱之為輔助集。綜上所述，可以將SN分為3類：

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

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

3) 輔助集合AN：SN中處于無效部分點的集合。

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

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

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

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

在此基礎(chǔ)上，對數(shù)據(jù)流中n-of-Nρ-支配輪廓的計算過程給出了偽碼描述如算法2所示(見表2)。當(dāng)數(shù)據(jù)流中有新數(shù)據(jù)點p到達(dá)滑動窗口時：首先判斷滑動窗口是否已滿，如果是則先刪除滑動窗口中最先到達(dá)的數(shù)據(jù)；然后將點p插入到相應(yīng)的空間區(qū)域中；最后將n-of-Nρ-支配輪廓集返回給用戶。其中，滑動窗口中最先到達(dá)的數(shù)據(jù)刪除用DeletePoint( )函數(shù)來表示，新到達(dá)的數(shù)據(jù)插入用InsertPoint( )函數(shù)表示。由算法的描述可以看出算法2的時間復(fù)雜度依賴DeletePoint( )函數(shù)和InsertPoint( )函數(shù)的時間復(fù)雜度，由于兩個函數(shù)的時間復(fù)雜度均為O(N)，所以算法2的時間復(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ù)流中計算n-of-Nρ-支配輪廓時將滑動窗口中最先到達(dá)的數(shù)據(jù)點p流出滑動窗口的過程(見表3)。第1行描述的是根據(jù)點p在數(shù)據(jù)流中的編號查找點p；第3行描述了計算要刪除點p所屬的空間區(qū)域的過程，在算法中用RegionCalculation( )函數(shù)[20]來表示，RegionCalculation( )函數(shù)包含兩個參數(shù)，第一個為所要計算的點p在各維上的數(shù)值部分value，第二個為查詢點q；第4～12行描述了對于點p所屬的每一個空間區(qū)域R的處理過程；第5行描述的為在空間區(qū)域R中刪除點p；第6～11行描述了對于空間區(qū)域R中的每一個點x，如果點p為點x的前ρ-支配點并且點x屬于候選集合(第7行)，則將點x從候選集合移動到n-of-Nρ-支配輪廓集合中(第8～9行)。通過算法描述可以看出DeletePoint( )函數(shù)外層循環(huán)為區(qū)域個數(shù)R=2d，內(nèi)層循環(huán)為滑動窗口中所屬R的數(shù)據(jù)N/2d，因此函數(shù)時間復(fù)雜度為O(N)。

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

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

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

4 實驗說明和實驗方案

4.1 實驗說明

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

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

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

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

本節(jié)使用C++語言實現(xiàn)了擴(kuò)展的數(shù)據(jù)流中ρ-支配輪廓查詢算法和數(shù)據(jù)流中n-of-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 實驗方案

4.2.1ρ值對算法的影響

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

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

圖6 ρ值對計算時間的影響Fig.6 Effect of ρ on computing time

4.2.2 滑動窗口大小對算法的影響

本節(jié)測試了滑動窗口大小對于算法的影響。圖7為滑動窗口大小對于輪廓集大小的影響，從中可以看出：隨著滑動窗口的增大輪廓集也變大；但是無論怎樣變化，輪廓集都遠(yuǎn)遠(yuǎn)小于滑動窗口的大小，因此在裝甲車輛狀態(tài)數(shù)據(jù)傳輸過程中應(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為滑動窗口大小對于計算時間的影響，從中可以看出：隨著滑動窗口的增大計算時間也變大，這是由于隨著滑動窗口的增大，所需計算的數(shù)據(jù)量變大，因而導(dǎo)致計算時間增大，但是無論滑動窗口如何變化，兩種算法的計算時間基本一致。

圖7 滑動窗口對輪廓集大小的影響Fig.7 Effect of sliding window on skyline size

圖8 滑動窗口對計算時間的影響Fig.8 Effect of sliding window on computing time

4.2.3 維度對算法的影響

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

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

圖10 維度對計算時間的影響Fig.10 Effect of dimension on computing time

4.2.4 滑動窗口有效部分大小對算法的影響

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

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

5 結(jié)論

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

參考文獻(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é)報,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)的多移動用戶動態(tài)Skyline查詢[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ù)動態(tài)skyline查詢研究[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ī)學(xué)報,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ī)科學(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)