面向頻繁位置更新的不確定移動(dòng)對(duì)象索引策略*

張 潮，李博涵，秦小麟

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

2.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，南京 210016

面向頻繁位置更新的不確定移動(dòng)對(duì)象索引策略*

張 潮1+，李博涵1,2，秦小麟1,2

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

2.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，南京 210016

ZHANG Chao,LI Bohan,QIN Xiaolin.Indexing of uncertain moving objects for frequent position updates. Journal of Frontiers of Computer Science and Technology,2016,10(11):1532-1545.

位置不確定性是移動(dòng)對(duì)象的重要特點(diǎn)之一。已有的不確定移動(dòng)對(duì)象索引技術(shù)旨在提高查詢效率，但是當(dāng)移動(dòng)對(duì)象位置頻繁更新時(shí)，存在更新代價(jià)較大的問(wèn)題。針對(duì)移動(dòng)對(duì)象頻繁位置更新引起的開銷增加問(wèn)題，在TPU-tree索引結(jié)構(gòu)上支持移動(dòng)對(duì)象群組劃分策略，給出了一種適用于頻繁位置更新的索引結(jié)構(gòu)GTPU-tree。在此基礎(chǔ)上提出了基于空間軌跡相似度的群組劃分算法STSG（spatial trajectory of similarity group）和不確定移動(dòng)對(duì)象群組更新算法。GTPU-tree通過(guò)減少同一分組中移動(dòng)對(duì)象的更新次數(shù)，降低磁盤I/O次數(shù)，從而降低更新代價(jià)。通過(guò)實(shí)驗(yàn)對(duì)基于GTPU-tree和TPU2M-tree等索引結(jié)構(gòu)的算法效率進(jìn)行了對(duì)比分析，結(jié)果表明GTPU-tree相比于TPU2M-tree在移動(dòng)對(duì)象數(shù)量較大時(shí)，GTPU-tree的更新代價(jià)將低于TPU2M-tree；與TPU-tree相比插入性能提高約30%，更新代價(jià)降低約35%。

位置不確定性；TPU樹；TPU2M樹；群組劃分；更新代價(jià)

1 引言

隨著移動(dòng)計(jì)算和定位技術(shù)的不斷發(fā)展，位置服務(wù)在日常生活中扮演著越發(fā)重要的角色。位置服務(wù)的質(zhì)量依賴于對(duì)移動(dòng)對(duì)象的有效管理[1]。由于存在數(shù)據(jù)采集不精確，移動(dòng)物體延遲更新和隱私保護(hù)等原因，移動(dòng)對(duì)象的位置不確定性普遍存在[2]。為了使數(shù)據(jù)庫(kù)中查詢提供更“靠譜”的數(shù)據(jù)，需要將查詢結(jié)果的不精確性限定在一定的范圍內(nèi)。在索引結(jié)構(gòu)中儲(chǔ)存移動(dòng)對(duì)象不確定性信息已成為時(shí)空數(shù)據(jù)庫(kù)研究的熱點(diǎn)。但是由于移動(dòng)對(duì)象的位置隨時(shí)間而變化，在傳統(tǒng)空間索引結(jié)構(gòu)中存儲(chǔ)空間對(duì)象的具體位置無(wú)法適應(yīng)大量空間對(duì)象的更新操作，因而不適合移動(dòng)對(duì)象的存儲(chǔ)與檢索[3]。

頻繁更新移動(dòng)對(duì)象的位置信息會(huì)導(dǎo)致更新代價(jià)增加，而低頻率的更新可能會(huì)導(dǎo)致查詢結(jié)果返回“過(guò)時(shí)”的數(shù)據(jù)，與當(dāng)下實(shí)際情況可能存在較大誤差。研究支持移動(dòng)對(duì)象位置不確定性且減少移動(dòng)對(duì)象位置更新代價(jià)的索引結(jié)構(gòu)具有現(xiàn)實(shí)意義。已有的位置更新策略主要分為以下兩種：（1）周期性更新，例如每過(guò)n個(gè)時(shí)鐘周期更新一次移動(dòng)對(duì)象的位置信息。這種更新策略主要適合于移動(dòng)對(duì)象運(yùn)動(dòng)較為規(guī)律和穩(wěn)定的場(chǎng)景，通過(guò)周期性地更新移動(dòng)對(duì)象位置信息，使數(shù)據(jù)庫(kù)中保存移動(dòng)對(duì)象當(dāng)前運(yùn)動(dòng)狀態(tài)的最新信息。（2）推測(cè)定位更新[4]，其定義是無(wú)論何時(shí)，只要移動(dòng)對(duì)象的實(shí)際位置和數(shù)據(jù)庫(kù)中記錄的位置超過(guò)一定的閾值（threshold）就對(duì)移動(dòng)對(duì)象的位置信息進(jìn)行一次更新。因此這個(gè)閾值大小決定并且限定了位置不精確性的范圍。然而不論是周期性更新策略，還是推測(cè)定位更新策略，目前對(duì)移動(dòng)對(duì)象位置不確定性的管理（如TPU-tree、U-tree等）都側(cè)重于對(duì)單個(gè)移動(dòng)對(duì)象的位置進(jìn)行管理，缺少在移動(dòng)對(duì)象之間建立關(guān)聯(lián)。

在現(xiàn)實(shí)場(chǎng)景中，一些移動(dòng)對(duì)象集合之間的運(yùn)動(dòng)軌跡往往具有一定的相似性和規(guī)律性。比如：在一個(gè)景區(qū)參觀的旅行團(tuán)，旅行團(tuán)的游客在導(dǎo)游的帶領(lǐng)下對(duì)景區(qū)進(jìn)行參觀，因此游客的運(yùn)動(dòng)方向和速度基本和導(dǎo)游相同，具有相似的運(yùn)動(dòng)軌跡；在超市購(gòu)物的一家三口，在超市中的運(yùn)動(dòng)軌跡也具有相似性，彼此之間的運(yùn)動(dòng)軌跡差異很小；在道路上行駛的車隊(duì)，因?yàn)楹竺娴能囕v需要跟著前車進(jìn)行行駛，車輛之間的速度和方向都基本相同，所以彼此之間具有相似的運(yùn)動(dòng)軌跡。通過(guò)這些實(shí)例可以發(fā)現(xiàn)，對(duì)于存在大量移動(dòng)對(duì)象集合的情況下，往往能找到一些移動(dòng)對(duì)象，它們之間具有相似的運(yùn)動(dòng)軌跡。移動(dòng)對(duì)象的軌跡如果具有一定的相似性，可以將它們劃分為一個(gè)群組（group），對(duì)于同一個(gè)群組中的成員，因?yàn)橐苿?dòng)對(duì)象彼此的位置信息相似，所以在進(jìn)行位置更新時(shí)，只需要對(duì)一個(gè)移動(dòng)對(duì)象進(jìn)行位置更新，不需要實(shí)時(shí)顯式更新每一個(gè)移動(dòng)對(duì)象的位置信息。利用單個(gè)移動(dòng)對(duì)象作為代表群組中具有相似運(yùn)動(dòng)軌跡的移動(dòng)對(duì)象，基于這種更新策略，減少移動(dòng)對(duì)象的更新次數(shù)，從而降低移動(dòng)對(duì)象位置更新代價(jià)。

本文貢獻(xiàn)主要有：

（1）在已有支持移動(dòng)對(duì)象不確定性索引TRU-tree的基礎(chǔ)上，提出一種支持移動(dòng)對(duì)象運(yùn)動(dòng)軌跡關(guān)聯(lián)的索引結(jié)構(gòu)GTRU-tree。GTPU-tree基于移動(dòng)對(duì)象群組劃分，能有效減少因移動(dòng)對(duì)象頻繁位置更新帶來(lái)的巨大更新代價(jià)。

（2）通過(guò)對(duì)移動(dòng)對(duì)象歷史軌跡的比較分析，提出了基于空間軌跡相似度的群組劃分算法STSG（spatial trajectory of similarity group）。算法利用空間軌跡相似度（spatial trajectory of similarity，STS）來(lái)描述移動(dòng)對(duì)象軌跡的相似性，將空間軌跡相似度大的移動(dòng)對(duì)象劃分為一個(gè)群組，同一個(gè)群組的移動(dòng)對(duì)象連續(xù)存放于GTPU-tree的葉子節(jié)點(diǎn)。

（3）在周期性更新和推測(cè)定位更新策略基礎(chǔ)上，提出了一種混合的基于軌跡依賴的移動(dòng)對(duì)象位置更新策略?；旌细虏呗苑謨刹糠郑孩佼?dāng)移動(dòng)對(duì)象進(jìn)行位置更新時(shí)，只對(duì)GTPU-tree中存放于同一葉子節(jié)點(diǎn)的一個(gè)移動(dòng)對(duì)象的位置信息進(jìn)行更新，其余同組的移動(dòng)對(duì)象只存放對(duì)該移動(dòng)對(duì)象的依賴關(guān)系。通過(guò)減少位置更新的次數(shù)，降低更新代價(jià)。②周期性檢測(cè)同一個(gè)群組中移動(dòng)對(duì)象軌跡相似性，將運(yùn)動(dòng)軌跡偏離的移動(dòng)對(duì)象重新分組，保證同一個(gè)群組中的移動(dòng)對(duì)象具有較高的軌跡相似度。

2 基礎(chǔ)知識(shí)

2.1 相關(guān)工作

傳統(tǒng)數(shù)據(jù)庫(kù)索引技術(shù)是為了存儲(chǔ)精確數(shù)據(jù)而設(shè)計(jì)，其索引結(jié)構(gòu)中存儲(chǔ)著移動(dòng)對(duì)象的精確位置。而因?yàn)橐苿?dòng)對(duì)象的位置不確定性普遍存在，所以需要改進(jìn)傳統(tǒng)的索引結(jié)構(gòu)來(lái)有效管理移動(dòng)對(duì)象的不確定性。

為解決如何高效管理移動(dòng)對(duì)象實(shí)時(shí)變化的精確位置信息的問(wèn)題，學(xué)者提出了一系列的索引結(jié)構(gòu)，從查詢位置信息的時(shí)間角度可分為兩類：一類是針對(duì)歷史位置信息的索引；另一類是針對(duì)移動(dòng)對(duì)象當(dāng)前及未來(lái)位置信息的索引。如TPR*樹[5]、STAR樹[6]和REXP樹[7]都是基于參數(shù)化的索引方法對(duì)當(dāng)前和未來(lái)位置信息進(jìn)行管理。其中TPR樹及其變種TPR*樹都是基于對(duì)R-tree的變形，其查詢、插入和刪除操作和R-tree相似，其自頂向下的更新模式會(huì)導(dǎo)致較大I/O代價(jià)，從而對(duì)于那些頻繁進(jìn)行位置更新的移動(dòng)對(duì)象來(lái)說(shuō)，難以滿足更新要求；REXP樹通過(guò)在節(jié)點(diǎn)上添加數(shù)據(jù)時(shí)間有效屬性的策略，提高了失效數(shù)據(jù)的刪除效率，從而提高更新性能；也有學(xué)者將移動(dòng)對(duì)象的歷史位置、當(dāng)前位置和未來(lái)位置信息結(jié)合起來(lái)，提出PPFNx樹[8]、RPPF樹[9]等索引模型，打破了“多線”的限制。上述索引模型對(duì)于那些位置更新次數(shù)較少的移動(dòng)對(duì)象的不確定性查詢具有很好的查詢效果，但是不能很好地處理移動(dòng)對(duì)象頻繁的位置更新問(wèn)題。文獻(xiàn)[10]提出了基于R-tree的自底向上的更新思想，其更新過(guò)程從樹的葉子節(jié)點(diǎn)開始，節(jié)省了查詢時(shí)間，從而提高了動(dòng)態(tài)更新的性能，但是不足之處在于其索引的維護(hù)需要耗費(fèi)大量的內(nèi)存資源，從而導(dǎo)致系統(tǒng)的穩(wěn)定性不高，且不適合解決頻繁位置變化范圍大的移動(dòng)對(duì)象的問(wèn)題。

Tao等人[11]提出U-tree的索引模型，U-tree具有良好的動(dòng)態(tài)結(jié)構(gòu)，使得數(shù)據(jù)的插入順序可以任意改變和更新，而且對(duì)不確定數(shù)據(jù)本身的概率密度分布沒有任何的限制。但是U-tree只適合于靜態(tài)的移動(dòng)對(duì)象不確定性索引。文獻(xiàn)[12]提出了一種基于U-tree的高效率當(dāng)前及未來(lái)不確定位置信息檢索的TPU-tree。TPU-tree在基本的U-tree結(jié)構(gòu)上增加記錄移動(dòng)對(duì)象不確定狀態(tài)特征的數(shù)據(jù)結(jié)構(gòu)，通過(guò)利用概率密度函數(shù)描述移動(dòng)對(duì)象在不確定區(qū)域的位置分布，在保留原有位置記錄的情況下加入時(shí)間特性，從而能對(duì)移動(dòng)對(duì)象當(dāng)前和未來(lái)位置信息進(jìn)行檢索。文獻(xiàn)[13]在TPU-tree的基礎(chǔ)上增加一個(gè)記錄不確定移動(dòng)對(duì)象狀態(tài)特征的更新備忘錄（UM）內(nèi)存結(jié)構(gòu)，提出了一種支持頻繁位置更新的不確定移動(dòng)對(duì)象索引策略TPU2M樹，并提出了一種改進(jìn)的基于備忘錄的更新/插入算法（MMBU/I）。MMBU/I算法利用UM控制不確定移動(dòng)對(duì)象的位置更新，在保留原有記錄的情況下首先插入新記錄，減少了查找時(shí)所需要的磁盤I/O，從而提高更新效率。但是TPU2M樹需要額外的內(nèi)存空間存放備忘錄的信息，當(dāng)UM中的記錄個(gè)數(shù)逐漸增加時(shí)，需要增加額外的空間清洗操作來(lái)保證較高的更新效率，且當(dāng)不確定移動(dòng)對(duì)象個(gè)數(shù)較多時(shí)，更新后的葉子節(jié)點(diǎn)超過(guò)舊記錄的MBR（minimum bounding rectangle）的概率會(huì)逐漸增加，因此更新效率會(huì)逐漸降低。

文獻(xiàn)[14]提出一種基于Bx樹的不確定移動(dòng)對(duì)象索引策略ABx樹，該索引模型利用矩形框推論法則和蒙特卡洛模擬相結(jié)合的方法預(yù)測(cè)移動(dòng)對(duì)象未來(lái)的位置信息，并提出了高效的概率范圍查詢和概率K最近鄰查詢。但是ABx樹的不足之處在于，頻繁更新的移動(dòng)對(duì)象位置信息使得資源消耗嚴(yán)重，增加更新代價(jià)。

通過(guò)對(duì)上述索引結(jié)構(gòu)的介紹，可知對(duì)于頻繁位置更新的移動(dòng)對(duì)象，設(shè)計(jì)索引結(jié)構(gòu)時(shí)，如何減少由于移動(dòng)對(duì)象頻繁的位置更新而引起的更新代價(jià)顯得十分必要。然而上述的索引結(jié)構(gòu)，在考慮移動(dòng)對(duì)象的位置變化時(shí)，只是針對(duì)單個(gè)移動(dòng)對(duì)象，沒有將移動(dòng)對(duì)象之間的運(yùn)動(dòng)軌跡進(jìn)行關(guān)聯(lián)考慮。

基于以上問(wèn)題，本文在TPU-tree的基礎(chǔ)上引入移動(dòng)對(duì)象群組概念，將具有相似運(yùn)動(dòng)軌跡的移動(dòng)對(duì)象劃分為一個(gè)群組，在同一個(gè)群組中只是對(duì)一個(gè)移動(dòng)對(duì)象進(jìn)行位置更新，其余移動(dòng)對(duì)象值存儲(chǔ)分組信息，減少了位置更新次數(shù)，從而降低更新代價(jià)。

2.2 不確定對(duì)象數(shù)據(jù)模型

文獻(xiàn)[15]提出了目前較為流行的不確定數(shù)據(jù)模型——推測(cè)定位更新模型，其定義是無(wú)論何時(shí)只要移動(dòng)對(duì)象的實(shí)際位置和數(shù)據(jù)庫(kù)中存放的位置超過(guò)一定的閾值th，就對(duì)移動(dòng)對(duì)象的位置信息進(jìn)行一次更新。有學(xué)者根據(jù)移動(dòng)對(duì)象運(yùn)動(dòng)的不同應(yīng)用場(chǎng)景，將數(shù)據(jù)模型劃分為不確定直線數(shù)據(jù)模型和不確定自由運(yùn)動(dòng)數(shù)據(jù)模型。前者主要是針對(duì)在路網(wǎng)約束下的移動(dòng)對(duì)象，由于道路的約束，移動(dòng)對(duì)象在未來(lái)的一段時(shí)間內(nèi)只能分布在某一條直線上；后者對(duì)移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡沒有限制。結(jié)合不確定自由運(yùn)動(dòng)數(shù)據(jù)模型的特點(diǎn)，給出如下移動(dòng)對(duì)象位置不確定數(shù)據(jù)模型的相關(guān)定義。

定義1（不確定區(qū)域[16]）移動(dòng)對(duì)象Mi在t時(shí)刻的位置處于一個(gè)封閉區(qū)域URi(t)，其中URi(t)就是Mi在t時(shí)刻對(duì)應(yīng)的不確定區(qū)域。

定義2（概率密度分布[16]）移動(dòng)對(duì)象Mi在不確定區(qū)域URi(t)中的概率密度分布函數(shù)記為PDFi(x,t)，表示Mi在t時(shí)刻出現(xiàn)在位置x的概率。

結(jié)合定義1和定義2可知，在t時(shí)刻，移動(dòng)對(duì)象Mi必然位于不確定區(qū)域URi(t)，易知概率密度分布函數(shù)在t時(shí)刻滿足∫URi(t)PDFi(x,t)dt=1。

如圖1所示為不確定移動(dòng)對(duì)象在t時(shí)刻的分布示意圖。圖中白色的圓心位置就是移動(dòng)對(duì)象當(dāng)前存放在數(shù)據(jù)庫(kù)中的記錄位置，而陰影部分是移動(dòng)對(duì)象的不確定區(qū)域URi(t)，其中不確定區(qū)域的半徑就是設(shè)定的閾值th，移動(dòng)對(duì)象Mi可能分布在URi(t)中任意位置。具體的分布與概率密度分布函數(shù)PDFi(x,t)有關(guān)。最常見的概率密度分布函數(shù)為均勻分布。均勻分布認(rèn)為移動(dòng)對(duì)象Mi出現(xiàn)在不確定區(qū)域的任意位置的可能性都是一樣的，并不是在其中的某一點(diǎn)或某一區(qū)域具有較高的出現(xiàn)幾率。均勻分布有助于減少域查詢的CPU計(jì)算時(shí)間和磁盤I/O次數(shù)。針對(duì)不確定區(qū)域內(nèi)的高斯分布，也有學(xué)者提出了基于平均值和方差的查詢計(jì)算方法。不同的概率密度分布函數(shù)采用不同的查詢處理方法。

Fig.1 Uncertain area圖1 不確定區(qū)域示意圖

2.3 軌跡相似性度量的計(jì)算

受移動(dòng)對(duì)象的空間布局和不同傳感器采樣周期的限制，移動(dòng)對(duì)象在環(huán)境中被感知到的數(shù)據(jù)通常是離散的。由于移動(dòng)對(duì)象位置、移動(dòng)速度及方向的動(dòng)態(tài)變化，實(shí)時(shí)的聚類需要巨大的開銷。本文利用歷史位置和速度來(lái)描述對(duì)象的移動(dòng)參數(shù)，通過(guò)移動(dòng)參數(shù)來(lái)分析移動(dòng)對(duì)象的軌跡情況，從而對(duì)移動(dòng)對(duì)象進(jìn)行群組劃分。

移動(dòng)對(duì)象Mi的時(shí)空坐標(biāo)為四元組(l,x,y,t)，其中l(wèi)是Mi的標(biāo)簽（label），表示移動(dòng)對(duì)象的語(yǔ)義分類。在兩個(gè)移動(dòng)對(duì)象Mi和Mj標(biāo)簽已知的情況下，如果Mi和Mj具有相同的語(yǔ)義標(biāo)簽，那么可以直接將他們劃分為一個(gè)群組。例如在景區(qū)中的同一個(gè)旅行團(tuán)成員，在道路上的同一個(gè)車隊(duì)等。提前獲知移動(dòng)對(duì)象的語(yǔ)義標(biāo)簽可以直接進(jìn)行分組，但更多情況下無(wú)法直接獲取移動(dòng)對(duì)象Mi的語(yǔ)義標(biāo)簽，此時(shí)就需要對(duì)移動(dòng)對(duì)象的軌跡數(shù)據(jù)進(jìn)行分析。x,y,t表示為在t時(shí)刻移動(dòng)對(duì)象Mi的空間坐標(biāo)為(x,y)。

移動(dòng)對(duì)象Mi在t0時(shí)刻的位置信息為(l,x0,y0,t0)，經(jīng)過(guò)ΔT,其t1時(shí)刻坐標(biāo)變?yōu)?l,x1,y1,t1)。設(shè)Δx、Δy分別為沿x、y方向運(yùn)動(dòng)的變化量，移動(dòng)速度為v，移動(dòng)方向?yàn)棣龋瑒t：

對(duì)于移動(dòng)對(duì)象的移動(dòng)特性，已有研究側(cè)重相對(duì)方向[17]（relative direction，RD）和速率比[18]（speed ratio，SR）等方面。在已有研究基礎(chǔ)上，本文提出了空間距離（spatial distance，SD），并且通過(guò)RD、SR和SD三者間的結(jié)合提出了空間軌跡相似度（STS）度量公式。

關(guān)于移動(dòng)對(duì)象Mi和Mj在t時(shí)刻的相對(duì)方向RD的計(jì)算見式（3），其定義為速度夾角的余弦值，夾角差越小，RD就越大，夾角差越小，意味著運(yùn)動(dòng)方向就越一致，兩者之間的差異性也就越小。

關(guān)于移動(dòng)對(duì)象Mi和Mj在t時(shí)刻的速率比SR的計(jì)算見式（4），其定義為最小速度和最大速度之比，SR反映了Mi和Mj之間速度差異，當(dāng)速度的差值越大時(shí)，SR越小，當(dāng)二者速度相同時(shí)，SR值為1。

其中關(guān)于移動(dòng)對(duì)象Mi和Mj在t時(shí)刻的SD的定義為兩者之間空間距離差，采用歐式距離來(lái)計(jì)算，當(dāng)移動(dòng)對(duì)象Mi和Mj空間上越接近，SD的值越小，反之越大。SD的計(jì)算公式如下：

STS描述了移動(dòng)對(duì)象之間的空間軌跡相似度，STS的值依賴于SR、RD和SD。從前面的公式可知，移動(dòng)對(duì)象之間的速度和方向越一致，RD和SR的值越大，反之則其值越小。而速度和方向越一致，體現(xiàn)兩個(gè)移動(dòng)對(duì)象之間的空間軌跡相似度越高，從而說(shuō)明STS與SR和RD成正相關(guān)。移動(dòng)對(duì)象Mi和Mj之間空間距離越大，兩者之間的空間軌跡相似度越小，因此STS與SD成負(fù)相關(guān)，其計(jì)算公式如下：

3 GTPU-tree索引結(jié)構(gòu)及相關(guān)算法

3.1 GTPU-tree索引結(jié)構(gòu)

為了使索引結(jié)構(gòu)支持移動(dòng)對(duì)象群組劃分，從而在移動(dòng)對(duì)象位置更新時(shí)，在同一組中的移動(dòng)對(duì)象只需要對(duì)同組中的一個(gè)移動(dòng)對(duì)象進(jìn)行更新操作，減少更新次數(shù)，從而降低更新代價(jià)。GTPU-tree將整個(gè)索引結(jié)構(gòu)劃分成3層。如圖2所示，GTPU-tree包含空間層、分組層和數(shù)據(jù)層。

（1）空間層

空間層用于描述移動(dòng)對(duì)象所在空間的位置信息?？臻g層中節(jié)點(diǎn)的記錄形式。其中flag、MBR、ptr分別作為葉子節(jié)點(diǎn)標(biāo)記位、最小邊界矩形和指向下一層的指針。對(duì)于葉子節(jié)點(diǎn)，ptr指向分組層的節(jié)點(diǎn)。由于移動(dòng)對(duì)象的位置時(shí)刻發(fā)生改變，移動(dòng)對(duì)象所在群組的空間位置也發(fā)生著變化，當(dāng)分組層中Gi組的移動(dòng)對(duì)象的空間位置與當(dāng)前記錄葉子節(jié)點(diǎn)的位置距離差距大于閾值th時(shí)，就會(huì)進(jìn)行位置更新操作。斷開分組層與葉子節(jié)點(diǎn)的指針，使分組層指向當(dāng)前移動(dòng)對(duì)象實(shí)際位置所在的葉子節(jié)點(diǎn)。

Fig.2 GTPU-tree index structure圖2 GTPU-tree索引結(jié)構(gòu)圖

（2）分組層

分組層中GPTU-tree節(jié)點(diǎn)的記錄形式。其中g(shù)_id、ptr_r、ptr_g、MBR、th、time_update分別是群組標(biāo)記位、空間層葉子指針、數(shù)據(jù)層指針、分組空間位置范圍、位置更新閾值和下一次位置更新時(shí)間。

由于GTPU-tree采用周期性更新和推測(cè)定位更新相結(jié)合的混合更新策略，當(dāng)分組層中記錄當(dāng)前組移動(dòng)對(duì)象的位置信息MBR與ptr_r所指空間層節(jié)點(diǎn)記錄的位置偏差超過(guò)閾值th時(shí)，就更新數(shù)據(jù)，重新指定ptr_r。由于群組劃分基于歷史軌跡，而移動(dòng)對(duì)象軌跡具有不確定性，為了使同一組中移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡盡可能保持一致，需要周期性地對(duì)分組情況進(jìn)行更新。更新策略判斷ptr_g中所指向的小組成員過(guò)去一段時(shí)間的軌跡是否仍然可以劃分為一組，如果出現(xiàn)偏差較大的移動(dòng)對(duì)象，就需要將與群體偏離較大的對(duì)象從組中移除。time_update就是記錄下一次檢查同組成員軌跡的時(shí)間。

如圖3所示，在T1時(shí)刻，移動(dòng)對(duì)象M0～M9共劃分為G1和G2兩個(gè)群組。其中G1和G2的圓半徑就是同一組中移動(dòng)對(duì)象之間位置信息差異的最大值。移動(dòng)對(duì)象之間通過(guò)空間軌跡相似度STS進(jìn)行群組劃分，STS越大，體現(xiàn)兩個(gè)移動(dòng)對(duì)象運(yùn)動(dòng)狀態(tài)越相似。因此當(dāng)STS大于閾值th時(shí)，將這些移動(dòng)對(duì)象劃分為同一組，保存在GTPU-tree的同一個(gè)節(jié)點(diǎn)中，反之則劃分為不同群組，具體算法3.2節(jié)會(huì)有介紹。如圖（a）所示，T1時(shí)刻G1中含有{M1,M3,M5,M7,M9}，G2中含有{M0,M2,M4,M6,M8}。由于移動(dòng)對(duì)象的空間位置和速度是在實(shí)時(shí)變化的，在T2時(shí)刻，M9對(duì)象與G1中的大部分對(duì)象的偏差較大，空間軌跡相似度STS較小，此時(shí)如果仍將M9劃分為G1，顯然是不合適的。因此需要周期性檢查同一組中移動(dòng)對(duì)象之間的偏差，對(duì)移動(dòng)對(duì)象重新進(jìn)行群組劃分。

Fig.3 Group partition update圖3 群組劃分更新示意圖

（3）數(shù)據(jù)層

在數(shù)據(jù)層中每個(gè)GTPU-tree葉子節(jié)點(diǎn)的形式為＜o(jì)id,ptr,PCR(pi),MBR,v,pdf_ptr,next_flag＞。其中oid、ptr、PCR(pi)、MBR、v、pdf_ptr、next_flag分別表示移動(dòng)對(duì)象Mi的標(biāo)記、指向分組層節(jié)點(diǎn)的指針、概率限定性區(qū)域、記錄在數(shù)據(jù)庫(kù)中的位置、速度向量、概率密度分布函數(shù)和是否存在下一個(gè)標(biāo)記。GTPU-tree的同一組中的移動(dòng)對(duì)象彼此之間連續(xù)存放，當(dāng)對(duì)組中的移動(dòng)對(duì)象進(jìn)行周期性檢測(cè)時(shí)，不僅判斷移動(dòng)對(duì)象的空間位置和速度偏差是否超過(guò)閾值，還需要更新移動(dòng)對(duì)象Mi的概率限定性區(qū)域。

3.2 移動(dòng)對(duì)象群組劃分算法STSG

GTPU-tree中將歷史一段時(shí)間內(nèi)具有相似運(yùn)動(dòng)軌跡的移動(dòng)對(duì)象劃分為一個(gè)群組，然后將同一分組中的移動(dòng)對(duì)象存放在GTPU-tree的同一個(gè)葉子節(jié)點(diǎn)中。關(guān)于移動(dòng)對(duì)象群組劃分，提出了基于空間軌跡相似度群組劃分算法STSG。該算法不僅適合二維情況，也很容易擴(kuò)展到三維或高維情況，為了研究問(wèn)題的方便，這里以二維為例給出算法說(shuō)明。下面是STSG算法中利用的一些定義。

定義3（直接可達(dá)）最小空間軌跡相似度STSMin是節(jié)點(diǎn)直接可達(dá)的判斷閾值，是一個(gè)常數(shù)。當(dāng)STS (Mi,Mj,t)>STSMin時(shí)，認(rèn)為在t時(shí)刻Mi和Mj直接可達(dá)，記為Mi?Mj，反之則Mi和Mj非直接可達(dá)，記為Mi/?Mj。

定義4（相依度可達(dá)）對(duì)于任意兩個(gè)節(jié)點(diǎn)Mi、Mj滿足Mi/?Mj，但存在Mk，令Mi?Mk和Mj?Mk，則稱Mi和Mj相依度可達(dá)，記為Mi?Mj，反之則Mi和Mj非相依度可達(dá)，記為Mi?Mj。

定義5（連接）對(duì)于任意兩個(gè)節(jié)點(diǎn)Mi、Mj滿足Mi/?Mj且Mi?Mj，但存在節(jié)點(diǎn)集合S(M1,M2,…,Mn), n>1，使得Mi和Mj能通過(guò)S相依度可達(dá)，則稱Mi和Mj連接，記為Mi≈Mj，反之則Mi和Mj非連接，記為Mi?Mj。

定義6（群組）將具有相似運(yùn)動(dòng)軌跡的移動(dòng)對(duì)象劃分為一個(gè)群組，記為g，當(dāng)且僅當(dāng)g滿足下列兩個(gè)條件：

（1）任意節(jié)點(diǎn)Mi、Mj，如果Mi∈g且Mi?Mj| Mi?Mj，則Mj∈g；

（2）任意節(jié)點(diǎn)Mi、Mj，如果Mi∈g且Mj∈g，則Mi≈Mj。

STSG算法的目標(biāo)是將所有相依度可達(dá)或直接可達(dá)的移動(dòng)對(duì)象劃分為同一個(gè)群組，然后存放于GTPU-tree同一個(gè)葉子節(jié)點(diǎn)中，在進(jìn)行位置更新時(shí)，對(duì)同一個(gè)群組中的移動(dòng)對(duì)象只需對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行位置更新，而不需要對(duì)全體成員都進(jìn)行位置更新，減少更新次數(shù)，降低移動(dòng)對(duì)象位置更新的代價(jià)。

如算法1所示，首先初始化頂點(diǎn)數(shù)組V和鄰接矩陣E（第2～3行）；其次對(duì)移動(dòng)對(duì)象數(shù)組M，計(jì)算任意兩個(gè)移動(dòng)對(duì)象之間的空間軌跡相似度關(guān)系，將結(jié)果記錄在V和E中構(gòu)成一個(gè)無(wú)向圖（第4～10行）；然后找到劃分群組的移動(dòng)對(duì)象Mi，給Mi初始化一個(gè)分組g，通過(guò)廣度優(yōu)先遍歷Mi所有相依度可達(dá)或直接可達(dá)的對(duì)象，將這些對(duì)象加入g中（第13～17行）；最后返回分組集合G。

算法1 STSG算法

3.3 GTPU-tree更新算法

移動(dòng)對(duì)象的更新是比較棘手的問(wèn)題，特別是高頻率下的位置更新請(qǐng)求。當(dāng)移動(dòng)對(duì)象發(fā)出位置更新請(qǐng)求時(shí)，新的記錄信息要插入到GTPU-tree中，且需要將過(guò)時(shí)的位置信息刪除。GTPU-tree分為空間層、分組層和數(shù)據(jù)層三層，在進(jìn)行更新時(shí)每層數(shù)據(jù)都需要更新。其中分組層主要包含一些記錄群組成員的信息和位置信息，在進(jìn)行更新時(shí)主要是進(jìn)行指針重定位操作和賦值操作?？臻g層和數(shù)據(jù)層的更新操作比較復(fù)雜，著重介紹這兩層的更新算法。

在空間層，采用預(yù)測(cè)定位更新方法進(jìn)行更新，當(dāng)移動(dòng)對(duì)象的實(shí)際位置和GTPU-tree中記錄的位置偏差超過(guò)閾值th時(shí)，進(jìn)行更新操作。GTPU-tree空間層的索引結(jié)構(gòu)是在R-tree的基礎(chǔ)上進(jìn)行改進(jìn)，更新方法與R-tree類似，按刪除、插入兩階段來(lái)進(jìn)行移動(dòng)對(duì)象的位置更新。

具體如算法2所示。算法主要分為兩個(gè)步驟：（1）刪除位置更新Mi所在的葉子節(jié)點(diǎn)L的舊記錄，利用CondenseTree函數(shù)對(duì)索引樹進(jìn)行壓縮（第1～3行）。（2）將包含新的位置信息的記錄插入到GTPU-tree中，在插入過(guò)程中判斷插入位置的節(jié)點(diǎn)空間是否足夠，如果夠，則直接插入；如果不夠，則進(jìn)行節(jié)點(diǎn)分裂，然后對(duì)GTPU-tree進(jìn)行調(diào)整。

算法2 UpdateTree

在數(shù)據(jù)層對(duì)分組數(shù)據(jù)進(jìn)行周期性更新。由于移動(dòng)對(duì)象的軌跡存在不確定性，原先可以劃分為同一個(gè)群組中的移動(dòng)對(duì)象，在運(yùn)動(dòng)一段時(shí)間后移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡發(fā)生變化，會(huì)有一些移動(dòng)對(duì)象偏離群體，此時(shí)需要重新劃分群組。GTPU-tree采用周期性檢測(cè)的策略，對(duì)數(shù)據(jù)層中的移動(dòng)對(duì)象檢測(cè)。

具體如算法3所示，首先獲取系統(tǒng)當(dāng)前的時(shí)間t_now（第1行），將GTPU_tree中每一個(gè)群組中記錄的下一次更新時(shí)間與t_now進(jìn)行比較，如果檢測(cè)到某分組需要更新，則將該組中所有對(duì)象存放進(jìn)集合M，調(diào)用STSG算法重新對(duì)M進(jìn)行分組（第2～5行）；比較新的分組G′和原先的分組G，如果發(fā)生改變，則將新的分組G′作為數(shù)據(jù)層添加到GTPU_tree中（第6～7行）；最后更新下一次更新的時(shí)間（第9行）。

算法3 Update_Group

4 實(shí)驗(yàn)及分析

實(shí)驗(yàn)利用Gist[19]對(duì)基于GTPU-tree、TPU-tree和TPU2M-tree等索引結(jié)構(gòu)的算法效率進(jìn)行了對(duì)比，并給出了評(píng)價(jià)與分析。實(shí)驗(yàn)分析與對(duì)比主要從五方面進(jìn)行設(shè)計(jì)。

第一部分為群組劃分算法STSG中的空間軌跡相似度STSMin大小對(duì)群組劃分結(jié)果和周期性群組更新的影響比較，通過(guò)實(shí)驗(yàn)對(duì)比找出合適的STSMin閾值；第二部分比較了GTPU-tree和R-tree在范圍查詢下的性能；第三部分比較了不同移動(dòng)對(duì)象數(shù)量下GTPU-tree、TPU-tree和TPU2M-tree的插入性能；第四部分對(duì)GTPU-tree、TPU-tree和TPU2M-tree在移動(dòng)對(duì)象頻繁更新的情況下，通過(guò)比較I/O和CPU代價(jià)，分析三者間的更新性能；第五部分對(duì)比分析GTPU-tree、TPU-tree和TPU2M-tree在不同移動(dòng)對(duì)象數(shù)量情況下的整體更新代價(jià)。

實(shí)驗(yàn)數(shù)據(jù)集使用空間數(shù)據(jù)生成器（spatial data generator，SDG）生成，在2 000×2 000的空間區(qū)域內(nèi)模擬移動(dòng)對(duì)象的運(yùn)動(dòng)情況。移動(dòng)對(duì)象不確定區(qū)域是一半徑為20的圓，移動(dòng)對(duì)象速度控制在[20,30]，移動(dòng)對(duì)象的概率密度分布是均勻分布。實(shí)驗(yàn)假設(shè)移動(dòng)對(duì)象在運(yùn)動(dòng)當(dāng)中不會(huì)消失，中途沒有新增移動(dòng)對(duì)象且在下一次群組更新時(shí)間前，同一分組的移動(dòng)對(duì)象保持相同的運(yùn)動(dòng)軌跡，通過(guò)不同的移動(dòng)對(duì)象更新數(shù)目反映移動(dòng)對(duì)象的頻繁位置更新。實(shí)驗(yàn)的硬件環(huán)境：CPU IntelCore i3 3.30 GHz，內(nèi)存4 GB；操作系統(tǒng)Windows7；開發(fā)環(huán)境VS2010。

4.1 STSMin對(duì)群組劃分和更新的影響

本文算法STSG利用空間軌跡相似度STS的大小來(lái)度量移動(dòng)對(duì)象之間歷史軌跡的相似性。在STSG算法中，最小空間軌跡相似度STSMin大小的設(shè)置直接影響了群組劃分效果的好壞。如圖4所示為STSMin大小對(duì)群組劃分結(jié)果的影響。從圖中可以看出，隨著最小空間軌跡相似度STSMin的增加，劃分群組的個(gè)數(shù)與STSMin呈正相關(guān)關(guān)系，也逐漸增加。這是因?yàn)殡S著最小空間軌跡相似度STSMin的增加，移動(dòng)對(duì)象軌跡判定為相似的要求更高，移動(dòng)對(duì)象直接可達(dá)和相依度可達(dá)的數(shù)目減少，從而劃分結(jié)果中群組的個(gè)數(shù)增加。

Fig.4 STSMineffect on group partition圖4 STSMin對(duì)群組劃分的影響

為了保證同一分組內(nèi)的移動(dòng)對(duì)象具有相似的運(yùn)動(dòng)軌跡，需要周期性檢測(cè)同一分組內(nèi)移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡。將那些偏離群體移動(dòng)對(duì)象的離散個(gè)體找出，重新對(duì)其進(jìn)行分組。一個(gè)好的群組劃分應(yīng)該具有在未來(lái)一段較長(zhǎng)時(shí)間內(nèi)，分組中偏離群體的個(gè)數(shù)較少的特性。分組中移動(dòng)對(duì)象軌跡越穩(wěn)定，可以增大群體重新劃分的周期T，從而降低由于群體重新劃分引起的更新代價(jià)。如圖5所示為不同STSMin下，分組中偏離群體的移動(dòng)對(duì)象個(gè)數(shù)變化情況。從圖中可以發(fā)現(xiàn)，隨著STSMin的增加，分組中偏離群體的移動(dòng)個(gè)數(shù)逐漸減少。這是因?yàn)殡S著STSMin的增大分組的個(gè)數(shù)增加，分組中的移動(dòng)對(duì)象個(gè)數(shù)越少，但是分組內(nèi)移動(dòng)對(duì)象的歷史運(yùn)動(dòng)軌跡越接近。從而在未來(lái)一段時(shí)間內(nèi)，移動(dòng)對(duì)象仍然保持相似的概率增加，偏離群體的移動(dòng)對(duì)象個(gè)數(shù)逐漸減少。

Fig.5 STSMineffect on the number of group deviations圖5 STSMin對(duì)群體偏離個(gè)數(shù)的影響

當(dāng)群組劃分個(gè)數(shù)增大時(shí)，會(huì)增加GTPU-tree插入節(jié)點(diǎn)時(shí)的代價(jià)；同樣當(dāng)偏離群體的移動(dòng)對(duì)象過(guò)多時(shí)，為了保證同組中移動(dòng)對(duì)象運(yùn)動(dòng)軌跡的相似性，需要縮小周期性群組更新時(shí)間T，增加了更新代價(jià)。從圖4和圖5中可以發(fā)現(xiàn)，當(dāng)STSMin在[6,8]之間時(shí)，曲線變化率較大，表明在這個(gè)區(qū)間內(nèi)STSMin取值對(duì)降低劃分群組個(gè)數(shù)和減少偏離群體的移動(dòng)對(duì)象個(gè)數(shù)都有較好的效果。綜合考慮，在后續(xù)實(shí)驗(yàn)中將最小空間軌跡相似度STSMin設(shè)置為6。

4.2 查詢性能

范圍查詢是移動(dòng)對(duì)象數(shù)據(jù)管理中常見的查詢之一。本文通過(guò)范圍查詢來(lái)檢驗(yàn)GTPU-tree的查詢性能。如圖6所示為不同查詢窗口大?。╭uery windows size，QS）下GTPU-tree和R-tree的查詢效率對(duì)比。從圖中可以發(fā)現(xiàn)，GTPU-tree的平均查詢時(shí)間略高于R-tree的查詢時(shí)間。這是因?yàn)镚TPU-tree整個(gè)索引結(jié)構(gòu)劃分為空間層、分組層和數(shù)據(jù)層3層，索引結(jié)構(gòu)相比較與R-tree復(fù)雜，索引樹的層次增多，所以查詢性能會(huì)有所降低。但GTPU-tree在降低更新代價(jià)的基礎(chǔ)上，仍和R-tree的查詢性能大致相當(dāng)。

Fig.6 Performance of query圖6 查詢性能

4.3 插入性能

對(duì)于不同規(guī)模的移動(dòng)對(duì)象集合，能否成功建立索引樹且構(gòu)建索引的時(shí)間能否保持平穩(wěn)是驗(yàn)證索引結(jié)構(gòu)插入性能關(guān)鍵。圖7展示的是移動(dòng)對(duì)象分布圖。從圖中可以發(fā)現(xiàn)，移動(dòng)對(duì)象均勻分布在2 000× 2 000的空間區(qū)域中。

Fig.7 Moving objects distribution圖7 移動(dòng)對(duì)象分布圖

Fig.8 Performance comparison of insert圖8 插入性能對(duì)比圖

對(duì)于不同移動(dòng)對(duì)象數(shù)目，GTPU-tree、TPU-tree和TPU2M-tree的插入時(shí)間如圖8所示。從圖中可以發(fā)現(xiàn)，這3者隨著移動(dòng)對(duì)象數(shù)目的增加，所需時(shí)間均呈平穩(wěn)增加的趨勢(shì)，且GTPU-tree花費(fèi)時(shí)間少于TPU-tree和TPU2M-tree，說(shuō)明GTPU-tree的插入性能優(yōu)于TPU-tree和TPU2M-tree。這是因?yàn)殡S著移動(dòng)對(duì)象數(shù)目的增加，GTPU-tree中的空間層層次逐漸增加，索引中空閑空間增加，后續(xù)插入的新條目可以被直接插入的概率增大，插入所需要的操作也減少，從而減少了插入花費(fèi)的時(shí)間；GTPU-tree相比于TPU-tree和TPU2M-tree提前進(jìn)行群組劃分的操作，同一個(gè)群組中的移動(dòng)對(duì)象可直接連續(xù)插入到分組層的節(jié)點(diǎn)當(dāng)中，避免了TPU-tree和TPU2M-tree中逐個(gè)插入，所以GTPU-tree的插入性能優(yōu)于TPU-tree和TPU2M-tree；TPU2M-tree和TPU-tree相比較，因?yàn)門PU2M-tree在插入一個(gè)新節(jié)點(diǎn)時(shí)，不僅需要插入到索引樹中而且還需要將其記錄到備忘錄的內(nèi)存結(jié)構(gòu)中，所以TPU-tree的插入性能會(huì)稍優(yōu)于TPU2M-tree。

4.4 更新代價(jià)

由于移動(dòng)對(duì)象位置的不確定性，為了保證查詢結(jié)果的精確性，需要同時(shí)更新數(shù)據(jù)庫(kù)和索引中的數(shù)據(jù)。對(duì)于位置頻繁更新的移動(dòng)對(duì)象，更新代價(jià)十分巨大?？紤]更新代價(jià)時(shí)，磁盤I/O和CPU是主要關(guān)心的兩個(gè)因素。更新次數(shù)和移動(dòng)對(duì)象的數(shù)量是影響不確定移動(dòng)對(duì)象更新代價(jià)的主要原因。圖9和圖10分別從移動(dòng)對(duì)象群體軌跡穩(wěn)定和群體頻繁偏離兩種場(chǎng)景下對(duì)GTPU-tree、TPU-tree和TPU2M-tree在不同更新次數(shù)下需要的更新代價(jià)進(jìn)行了對(duì)比分析，分別對(duì)比了磁盤I/O代價(jià)（圖（a））和CPU代價(jià)（圖（b））；圖11和圖12分別從移動(dòng)對(duì)象群體軌跡穩(wěn)定和群體頻繁偏離兩種場(chǎng)景下對(duì)GTPU-tree、TPU-tree和TPU2M-tree在不同移動(dòng)對(duì)象數(shù)量下的整體更新代價(jià)進(jìn)行了對(duì)比分析。

Fig.9 Comparing I/O+CPU cost with group trajectories stable圖9 群組軌跡穩(wěn)定下I/O+CPU更新代價(jià)分析

Fig.10 Comparing I/O+CPU cost with group frequent updates圖10 群組頻繁更新下I/O+CPU更新代價(jià)分析

Fig.11 Comparison of total cost with trajectories stability圖11 群組軌跡穩(wěn)定下整體更新代價(jià)對(duì)比

Fig.12 Comparison of total cost with trajectories deviation圖12 群組頻繁更新下整體更新代價(jià)對(duì)比

從圖9和圖10的圖（a）中可以發(fā)現(xiàn)，不管是軌跡穩(wěn)定還是群體頻繁偏離情況下，GTPU-tree比TPU-tree均大大減少了節(jié)點(diǎn)訪問(wèn)（node access）次數(shù)，但略高于TPU2M-tree，而節(jié)點(diǎn)訪問(wèn)次數(shù)又直接影響磁盤I/ O，從而可以說(shuō)明，對(duì)于位置頻繁更新的移動(dòng)對(duì)象，GTPU-tree在降低磁盤I/O上具有良好的性能，但略遜于TPU2M-tree。這是因?yàn)镚TPU-tree與TPU-tree相比進(jìn)行了移動(dòng)對(duì)象分組處理的改進(jìn)，將同一分組的移動(dòng)對(duì)象保存在數(shù)據(jù)層的同一個(gè)葉子節(jié)點(diǎn)中。在進(jìn)行位置更新時(shí)，對(duì)同一分組中的移動(dòng)對(duì)象只需要更新一個(gè)移動(dòng)對(duì)象，而不需要全部更新，減少了更新次數(shù)，降低了更新代價(jià)。而GTPU-tree的節(jié)點(diǎn)訪問(wèn)次數(shù)略高于TPU2M-tree，這是因?yàn)門PU2M-tree采用自底向上的節(jié)點(diǎn)訪問(wèn)策略，減少了查找時(shí)所需要的磁盤I/O，從而提高了更新效率。

對(duì)比圖9和圖10的圖（b）可以發(fā)現(xiàn)，GTPU-tree的CPU計(jì)算代價(jià)略高于TPU-tree且所占整體更新代價(jià)的比重也大于TPU-tree；但在移動(dòng)對(duì)象群組軌跡穩(wěn)定時(shí)GTPU-tree的CPU計(jì)算代價(jià)低于TPU2M-tree。這是因?yàn)門PU2M-tree在進(jìn)行節(jié)點(diǎn)更新時(shí)，需要先查詢備忘錄，且當(dāng)備忘錄中記錄個(gè)數(shù)增加時(shí)，需要進(jìn)行額外的空間清洗操作，增加CPU計(jì)算代價(jià)。GTPU-tree認(rèn)為在下一次群組更新前，同一分組的移動(dòng)對(duì)象保持相同的運(yùn)動(dòng)軌跡，因此在兩個(gè)群組更新操作的時(shí)間段內(nèi)，可以用一個(gè)移動(dòng)對(duì)象的位置替代同組內(nèi)的其他對(duì)象。但是由于移動(dòng)對(duì)象軌跡具有不確定性，為了保證同一分組中移動(dòng)對(duì)象軌跡的相似性，需要周期性進(jìn)行群組重新劃分，增加了CPU計(jì)算代價(jià)。

對(duì)比圖11和圖12可以發(fā)現(xiàn)，無(wú)論是在移動(dòng)對(duì)象群組軌跡穩(wěn)定還是群組頻繁偏離的場(chǎng)景，GTPU-tree的整體更新代價(jià)都小于TPU-tree。當(dāng)移動(dòng)對(duì)象數(shù)量較小時(shí)，GTPU-tree的整體更新代價(jià)大于TPU2M-tree，但是隨著移動(dòng)對(duì)數(shù)量的增加，TPU2M-tree的整體更新代價(jià)將超過(guò)GTPU-tree。這是因?yàn)閷?duì)于TPU2M-tree，隨著移動(dòng)對(duì)象數(shù)量的增加，索引樹的節(jié)點(diǎn)個(gè)數(shù)增加。每一個(gè)非葉子節(jié)點(diǎn)中含有的子節(jié)點(diǎn)個(gè)數(shù)具有限制，因此每一個(gè)非葉子節(jié)點(diǎn)的MBR逐漸減小。對(duì)于TPU2M-tree，當(dāng)節(jié)點(diǎn)的MBR減小時(shí)，新插入節(jié)點(diǎn)超過(guò)原記錄所在的MBR的概率增加，而新節(jié)點(diǎn)超過(guò)原記錄的MBR時(shí)，此時(shí)等價(jià)于在索引樹中插入新記錄，更新效率降低。

對(duì)于GTPU-tree，當(dāng)移動(dòng)對(duì)象的數(shù)量增加時(shí)，每個(gè)群組中的移動(dòng)對(duì)象個(gè)數(shù)也相應(yīng)的增加，此時(shí)更有利于進(jìn)行整體更新。特別在群組軌跡穩(wěn)定情況下，GTPU-tree的優(yōu)勢(shì)更加明顯。這是因?yàn)樵谝苿?dòng)對(duì)象群體軌跡穩(wěn)定的情況下，相比于群體頻繁偏離情況進(jìn)行群組重新劃分的更新周期T可以適當(dāng)增大，所以在相同時(shí)間內(nèi)，群組軌跡穩(wěn)定的情況可以減少由群組重新劃分引起的CPU代價(jià)開銷，從而降低整體更新代價(jià)。此時(shí)GTPU-tree與TPU2M-tree的更新代價(jià)曲線的交點(diǎn)會(huì)提前。說(shuō)明在群組軌跡穩(wěn)定的情況下GTPU-tree可以在更少的移動(dòng)對(duì)象數(shù)量下，在整體更新性能上優(yōu)于TPU2M-tree。

5 結(jié)束語(yǔ)

本文在TPU-tree的基礎(chǔ)上，針對(duì)不確定移動(dòng)對(duì)象頻繁位置更新代價(jià)較大等問(wèn)題，提出了一種支持移動(dòng)對(duì)象群組更新策略索引結(jié)構(gòu)GTPU-tree，并提出了基于空間軌跡相似度的群組劃分算法STSG和移動(dòng)對(duì)象群組更新算法。仿真實(shí)驗(yàn)分析了對(duì)不同情形下GTPU-tree、TPU-tree和TPU2M-tree的性能比較，結(jié)果表明GTPU-tree在插入性能上全面優(yōu)于TPU-tree和TPU2M-tree，即使在移動(dòng)對(duì)象群體偏離頻繁的最差情況下，GTPU-tree的更新代價(jià)也能優(yōu)于TPU-tree。GTPU-tree相比于TPU2M-tree，在移動(dòng)對(duì)象數(shù)量較少時(shí)，更新代價(jià)略高于TPU2M-tree，但當(dāng)移動(dòng)對(duì)象數(shù)量較大時(shí)，GTPU-tree的更新代價(jià)將低于TPU2M-tree；在查詢性能方面，GTPU-tree雖增加了索引結(jié)構(gòu)的復(fù)雜度，但查詢性能仍能與傳統(tǒng)索引大致相當(dāng)。

[1]Meng Xiaofeng,Ding Zhiming,Xu Jiajie.Moving objects management[M].Berlin:Springer,2013:69-80.

[2]Li Jiajia,Wang Botao,Wang Guoren,et al.A survey of query processing techniques over uncertain mobile objects[J]. Journal of Frontiers of Computer Science and Technology, 2013,7(12):1057-1072.

[3]Saltenis S,Jensen C S,Leutenegger S T,et al.Indexing the positions of continuously moving objects[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data,Dallas,USA,2000.New York:ACM, 2000:331-342.

[4]Güting R H,Schneider M.Moving objects databases[M]. [S.l.]:Elsevier,2005:220-268.

[5]Tao Yufei,Papadias D,Sun Jimeng.The TPR*-tree:an optimized spatio-temporal access method for predictive queries [C]//Proceedings of the 29th International Conference on Very Large Data Bases,Berlin,Germany,Sep 9-12,2003: 790-801.

[6]Procopiuc C M,Agarwal P K,Har-Peled S.STAR-tree:an efficient self-adjusting index for moving objects[C]//LNCS 2409:Proceedings of the 4th International Workshops on Algorithm Engineering and Experiments,San Francisco, USA,Jan 4-5,2002.Berlin,Heidelberg:Springer,2002: 178-193.

[7]Saltenis S,Jensen C S.Indexing of moving objects for locationbased services[C]//Proceedings of the 18th International Conference on Data Engineering,San Jose,USA,Feb 26-Mar 1,2002.Washington:IEEE Computer Society,2002:463.

[8]Fang Ying,Cao Jiaheng,Peng Yuwei,et al.Efficient indexing of the past,present and future positions of moving objects on road network[C]//LNCS 7901:Proceedings of the 2013 International Workshops on Web-Age Information Management,Beidaihe,China,Jun 14-16,2013.Berlin,Heidelberg: Springer,2013:223-235.

[9]Pelanis M,Saltenis S,Jensen C S.Indexing the past,present, and anticipated future positions of moving objects[J].ACM Transactions on Database Systems,2006,31(1):255-298.

[10]Lee M L,Hsu W,Jensen C S,et al.Supporting frequent updates in R-trees:a bottom-up approach[C]//Proceedings of the 29th International Conference on Very Large Data Bases, Berlin,Germany,Sep 9-12,2003:608-619.

[11]Tao Yufei,Cheng R,Xiao Xiaokui,et al.Indexing multidimensional uncertain data with arbitrary probability density functions[C]//Proceedings of the 31st International Conference on Very Large Data Bases,Trondheim,Norway,Aug 30-Sep 2,2005:922-933.

[12]Ding Xiaofeng,Lu Yansheng,Pan Peng,et al.U-tree based indexing method for uncertain moving objects[J].Journal of Software,2008,19(10):2696-2705.

[13]Ding Xiaofeng,Jin Hai,Zhao Na.Indexing of uncertain moving objects with frequent updates[J].Chinese Journal of Computers,2012,35(12):2587-2597.

[14]Zhang Meihui,Chen Su,Jensen C S,et al.Effectively indexing uncertain moving objects for predictive queries[J]. Proceedings of the VLDB Endowment,2009,2(1):1198-1209.

[15]Cheng R,Kalashnikov D V,Prabhakar S.Querying imprecise data in moving object environments[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9): 1112-1127.

[16]Wang Zhijie,Wang Donghua,Yao Bin,et al.Probabilistic range query over uncertain moving objects in constrained two-dimensional space[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(3):866-879.

[17]Sadahiro Y,Lay R,Kobayashi T.Trajectories of moving objects on a network:detection of similarities,visualization of relations,and classification of trajectories[J].Transactions in GIS,2013,17(1):18-40.

[18]Ra M,Lim C,Song Y H,et al.Effective trajectory similarity measure for moving objects in real-world scene[M]//Lecture Notes in Electrical Engineering 339:Information Science and Applications.Berlin,Heidelberg:Springer,2015: 641-648. [19]Stamatakos M,Douzinas E,Stefanaki C,et al.Gastrointestinal stromal tumor[J].World Journal of Surgical Oncology,2009, 7(1):61.

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

[2]李佳佳,王波濤,王國(guó)仁,等.不確定移動(dòng)對(duì)象的查詢處理技術(shù)研究綜述[J].計(jì)算機(jī)科學(xué)與探索,2013,7(12):1057-1072.

[12]丁曉鋒,盧炎生,潘鵬,等.基于U-tree的不確定移動(dòng)對(duì)象索引策略[J].軟件學(xué)報(bào),2008,19(10):2696-2705.

[13]丁曉鋒,金海,趙娜.支持頻繁位置更新的不確定移動(dòng)對(duì)象索引策略[J].計(jì)算機(jī)學(xué)報(bào),2012,35(12):2587-2597.

ZHANG Chao was born in 1991.He is an M.S.candidate at Nanjing University of Aeronautics and Astronautics, and the member of CCF.His research interests include spatio-temporal databases and uncertain moving objects indexing technology,etc.

張潮（1991—），男，浙江紹興人，南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，CCF會(huì)員，主要研究領(lǐng)域?yàn)闀r(shí)空數(shù)據(jù)庫(kù)，不確定移動(dòng)對(duì)象索引技術(shù)等。

LI Bohan was born in 1979.He is an associate professor and M.S.supervisor at Nanjing University of Aeronautics and Astronautics,and the member of CCF.His research interests include spatio-temporal databases and geographic information system,etc.

李博涵（1979—），男，吉林永吉人，南京航空航天大學(xué)副教授、碩士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)闀r(shí)空數(shù)據(jù)庫(kù)，地理信息系統(tǒng)等。

QIN Xiaolin was born in 1953.He is a professor and Ph.D.supervisor at Nanjing University of Aeronautics and Astronautics,and the senior member of CCF.His research interests include spatial and spatio-temporal databases, data management and security in distributed environment,etc.

秦小麟（1953—），男，江蘇南京人，南京航空航天大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榭臻g與時(shí)空數(shù)據(jù)庫(kù)，分布式數(shù)據(jù)管理與安全等。

Indexing of Uncertain Moving Objects for Frequent Position Updates?

ZHANG Chao1+,LI Bohan1,2,QIN Xiaolin1,2
1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
2.Collaborative Innovation Center for Novel Software and Industrialization,Nanjing 210016,China
+Corresponding author:E-mail:zhangchao0607@nuaa.edu.cn

Positional uncertainty is one key feature of the moving objects.Existing uncertain moving objects indexing technology aims to improve the efficiency of querying.However,when moving objects? positions update frequently, the update cost is huge.In order to solve this cost problem,this paper modifies the group partition strategy of TPU-tree and gives an index structure named GTPU-tree that supports frequent position update.Furthermore,this paper proposes a group partition algorithm STSG based on spatial trajectory of similarity and moving objects group updating algorithm.GTPU-tree reduces the number of disk I/O by reducing the update number in the same group,thus decreasing the update cost.This paper compares and analyzes the algorithm efficiency of GTPU-tree and TPU2M-tree.The exper-imental results demonstrate that while the number of moving objects is large,GTPU-tree update cost will be lower than TPU2M-tree;Compared with TPU-tree,GTPU-tree performs better than TPU-tree,which improves the inserting performance by 30%and reduces the update cost by 35%.

position uncertainty;TPU-tree;TPU2M-tree;group partition;update cost

10.3778/j.issn.1673-9418.1510078

A

TP311

*The National Natural Science Foundation of China under Grant Nos.61373015,61300052,41301047(國(guó)家自然科學(xué)基金);the Priority Academic Development Program of Jiangsu Higher Education Institutions(江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目);the Fundamental Research Funds for the Central Universities of China under Grant Nos.NP2013307,NZ2013306(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金);the Youth Fund of Natural Science Foundation of Jiangsu Province under Grant No.BK20130819(江蘇省自然科學(xué)基金青年基金);the Open Foundation of Graduate Innovation Center in NUAAunder Grant No.kfjj20151607(南京航空航天大學(xué)研究生創(chuàng)新實(shí)驗(yàn)室開放基金).

Received 2015-10,Accepted 2015-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-12-18,http://www.cnki.net/kcms/detail/11.5602.TP.20151218.1038.004.html