張 潮，李博涵，秦小麟

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

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

面向頻繁位置更新的不確定移動對象索引策略*

張 潮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.

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

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

1 引言

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

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

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

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

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

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

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

2 基礎(chǔ)知識

2.1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

STS描述了移動對象之間的空間軌跡相似度，STS的值依賴于SR、RD和SD。從前面的公式可知，移動對象之間的速度和方向越一致，RD和SR的值越大，反之則其值越小。而速度和方向越一致，體現(xiàn)兩個移動對象之間的空間軌跡相似度越高，從而說明STS與SR和RD成正相關(guān)。移動對象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)支持移動對象群組劃分，從而在移動對象位置更新時，在同一組中的移動對象只需要對同組中的一個移動對象進(jìn)行更新操作，減少更新次數(shù)，從而降低更新代價。GTPU-tree將整個索引結(jié)構(gòu)劃分成3層。如圖2所示，GTPU-tree包含空間層、分組層和數(shù)據(jù)層。

（1）空間層

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

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

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

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

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

在數(shù)據(jù)層中每個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分別表示移動對象Mi的標(biāo)記、指向分組層節(jié)點(diǎn)的指針、概率限定性區(qū)域、記錄在數(shù)據(jù)庫中的位置、速度向量、概率密度分布函數(shù)和是否存在下一個標(biāo)記。GTPU-tree的同一組中的移動對象彼此之間連續(xù)存放，當(dāng)對組中的移動對象進(jìn)行周期性檢測時，不僅判斷移動對象的空間位置和速度偏差是否超過閾值，還需要更新移動對象Mi的概率限定性區(qū)域。

3.2 移動對象群組劃分算法STSG

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

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

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

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

定義6（群組）將具有相似運(yùn)動軌跡的移動對象劃分為一個群組，記為g，當(dāng)且僅當(dāng)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á)的移動對象劃分為同一個群組，然后存放于GTPU-tree同一個葉子節(jié)點(diǎn)中，在進(jìn)行位置更新時，對同一個群組中的移動對象只需對一個節(jié)點(diǎn)進(jìn)行位置更新，而不需要對全體成員都進(jìn)行位置更新，減少更新次數(shù)，降低移動對象位置更新的代價。

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

算法1 STSG算法

3.3 GTPU-tree更新算法

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

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

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

算法2 UpdateTree

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

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

算法3 Update_Group

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

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

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

實(shí)驗(yàn)數(shù)據(jù)集使用空間數(shù)據(jù)生成器（spatial data generator，SDG）生成，在2 000×2 000的空間區(qū)域內(nèi)模擬移動對象的運(yùn)動情況。移動對象不確定區(qū)域是一半徑為20的圓，移動對象速度控制在[20,30]，移動對象的概率密度分布是均勻分布。實(shí)驗(yàn)假設(shè)移動對象在運(yùn)動當(dāng)中不會消失，中途沒有新增移動對象且在下一次群組更新時間前，同一分組的移動對象保持相同的運(yùn)動軌跡，通過不同的移動對象更新數(shù)目反映移動對象的頻繁位置更新。實(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對群組劃分和更新的影響

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

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

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

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

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

4.2 查詢性能

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

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

4.3 插入性能

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

Fig.7 Moving objects distribution圖7 移動對象分布圖

Fig.8 Performance comparison of insert圖8 插入性能對比圖

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

4.4 更新代價

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文在TPU-tree的基礎(chǔ)上，針對不確定移動對象頻繁位置更新代價較大等問題，提出了一種支持移動對象群組更新策略索引結(jié)構(gòu)GTPU-tree，并提出了基于空間軌跡相似度的群組劃分算法STSG和移動對象群組更新算法。仿真實(shí)驗(yàn)分析了對不同情形下GTPU-tree、TPU-tree和TPU2M-tree的性能比較，結(jié)果表明GTPU-tree在插入性能上全面優(yōu)于TPU-tree和TPU2M-tree，即使在移動對象群體偏離頻繁的最差情況下，GTPU-tree的更新代價也能優(yōu)于TPU-tree。GTPU-tree相比于TPU2M-tree，在移動對象數(shù)量較少時，更新代價略高于TPU2M-tree，但當(dāng)移動對象數(shù)量較大時，GTPU-tree的更新代價將低于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]李佳佳,王波濤,王國仁,等.不確定移動對象的查詢處理技術(shù)研究綜述[J].計(jì)算機(jī)科學(xué)與探索,2013,7(12):1057-1072.

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

[13]丁曉鋒,金海,趙娜.支持頻繁位置更新的不確定移動對象索引策略[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會員，主要研究領(lǐng)域?yàn)闀r空數(shù)據(jù)庫，不確定移動對象索引技術(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會員，主要研究領(lǐng)域?yàn)闀r空數(shù)據(jù)庫，地理信息系統(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高級會員，主要研究領(lǐng)域?yàn)榭臻g與時空數(shù)據(jù)庫，分布式數(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(國家自然科學(xué)基金);the Priority Academic Development Program of Jiangsu Higher Education Institutions(江蘇高校優(yōu)勢學(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