面向頻繁位置更新的不確定移動對象索引策略*
2016-11-22 02:07:02李博涵秦小麟
計算機與生活 2016年11期
張 潮，李博涵，秦小麟
1.南京航空航天大學 計算機科學與技術學院，南京 210016
2.軟件新技術與產業化協同創新中心，南京 210016
面向頻繁位置更新的不確定移動對象索引策略*
張 潮1+，李博涵1,2，秦小麟1,2
1.南京航空航天大學 計算機科學與技術學院，南京 210016
2.軟件新技術與產業化協同創新中心，南京 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.
位置不確定性是移動對象的重要特點之一。已有的不確定移動對象索引技術旨在提高查詢效率，但是當移動對象位置頻繁更新時，存在更新代價較大的問題。針對移動對象頻繁位置更新引起的開銷增加問題，在TPU-tree索引結構上支持移動對象群組劃分策略，給出了一種適用于頻繁位置更新的索引結構GTPU-tree。在此基礎上提出了基于空間軌跡相似度的群組劃分算法STSG（spatial trajectory of similarity group）和不確定移動對象群組更新算法。GTPU-tree通過減少同一分組中移動對象的更新次數，降低磁盤I/O次數，從而降低更新代價。通過實驗對基于GTPU-tree和TPU2M-tree等索引結構的算法效率進行了對比分析，結果表明GTPU-tree相比于TPU2M-tree在移動對象數量較大時，GTPU-tree的更新代價將低于TPU2M-tree；與TPU-tree相比插入性能提高約30%，更新代價降低約35%。
位置不確定性；TPU樹；TPU2M樹；群組劃分；更新代價
1 引言
隨著移動計算和定位技術的不斷發展，位置服務在日常生活中扮演著越發重要的角色。位置服務的質量依賴于對移動對象的有效管理[1]。由于存在數據采集不精確，移動物體延遲更新和隱私保護等原因，移動對象的位置不確定性普遍存在[2]。為了使數據庫中查詢提供更“靠譜”的數據，需要將查詢結果的不精確性限定在一定的范圍內。在索引結構中儲存移動對象不確定性信息已成為時空數據庫研究的熱點。但是由于移動對象的位置隨時間而變化，在傳統空間索引結構中存儲空間對象的具體位置無法適應大量空間對象的更新操作，因而不適合移動對象的存儲與檢索[3]。
頻繁更新移動對象的位置信息會導致更新代價增加，而低頻率的更新可能會導致查詢結果返回“過時”的數據，與當下實際情況可能存在較大誤差。研究支持移動對象位置不確定性且減少移動對象位置更新代價的索引結構具有現實意義。已有的位置更新策略主要分為以下兩種：（1）周期性更新，例如每過n個時鐘周期更新一次移動對象的位置信息。這種更新策略主要適合于移動對象運動較為規律和穩定的場景，通過周期性地更新移動對象位置信息，使數據庫中保存移動對象當前運動狀態的最新信息。（2）推測定位更新[4]，其定義是無論何時，只要移動對象的實際位置和數據庫中記錄的位置超過一定的閾值（threshold）就對移動對象的位置信息進行一次更新。因此這個閾值大小決定并且限定了位置不精確性的范圍。然而不論是周期性更新策略，還是推測定位更新策略，目前對移動對象位置不確定性的管理（如TPU-tree、U-tree等）都側重于對單個移動對象的位置進行管理，缺少在移動對象之間建立關聯。
在現實場景中，一些移動對象集合之間的運動軌跡往往具有一定的相似性和規律性。比如：在一個景區參觀的旅行團，旅行團的游客在導游的帶領下對景區進行參觀，因此游客的運動方向和速度基本和導游相同，具有相似的運動軌跡；在超市購物的一家三口，在超市中的運動軌跡也具有相似性，彼此之間的運動軌跡差異很小；在道路上行駛的車隊，因為后面的車輛需要跟著前車進行行駛，車輛之間的速度和方向都基本相同，所以彼此之間具有相似的運動軌跡。通過這些實例可以發現，對于存在大量移動對象集合的情況下，往往能找到一些移動對象，它們之間具有相似的運動軌跡。移動對象的軌跡如果具有一定的相似性，可以將它們劃分為一個群組（group），對于同一個群組中的成員，因為移動對象彼此的位置信息相似，所以在進行位置更新時，只需要對一個移動對象進行位置更新，不需要實時顯式更新每一個移動對象的位置信息。利用單個移動對象作為代表群組中具有相似運動軌跡的移動對象，基于這種更新策略，減少移動對象的更新次數，從而降低移動對象位置更新代價。
本文貢獻主要有：
（1）在已有支持移動對象不確定性索引TRU-tree的基礎上，提出一種支持移動對象運動軌跡關聯的索引結構GTRU-tree。GTPU-tree基于移動對象群組劃分，能有效減少因移動對象頻繁位置更新帶來的巨大更新代價。
（2）通過對移動對象歷史軌跡的比較分析，提出了基于空間軌跡相似度的群組劃分算法STSG（spatial trajectory of similarity group）。算法利用空間軌跡相似度（spatial trajectory of similarity，STS）來描述移動對象軌跡的相似性，將空間軌跡相似度大的移動對象劃分為一個群組，同一個群組的移動對象連續存放于GTPU-tree的葉子節點。
（3）在周期性更新和推測定位更新策略基礎上，提出了一種混合的基于軌跡依賴的移動對象位置更新策略。混合更新策略分兩部分：①當移動對象進行位置更新時，只對GTPU-tree中存放于同一葉子節點的一個移動對象的位置信息進行更新，其余同組的移動對象只存放對該移動對象的依賴關系。通過減少位置更新的次數，降低更新代價。②周期性檢測同一個群組中移動對象軌跡相似性，將運動軌跡偏離的移動對象重新分組，保證同一個群組中的移動對象具有較高的軌跡相似度。
2 基礎知識
2.1 相關工作
傳統數據庫索引技術是為了存儲精確數據而設計，其索引結構中存儲著移動對象的精確位置。而因為移動對象的位置不確定性普遍存在，所以需要改進傳統的索引結構來有效管理移動對象的不確定性。
為解決如何高效管理移動對象實時變化的精確位置信息的問題，學者提出了一系列的索引結構，從查詢位置信息的時間角度可分為兩類：一類是針對歷史位置信息的索引；另一類是針對移動對象當前及未來位置信息的索引。如TPR*樹[5]、STAR樹[6]和REXP樹[7]都是基于參數化的索引方法對當前和未來位置信息進行管理。其中TPR樹及其變種TPR*樹都是基于對R-tree的變形，其查詢、插入和刪除操作和R-tree相似，其自頂向下的更新模式會導致較大I/O代價，從而對于那些頻繁進行位置更新的移動對象來說，難以滿足更新要求；REXP樹通過在節點上添加數據時間有效屬性的策略，提高了失效數據的刪除效率，從而提高更新性能；也有學者將移動對象的歷史位置、當前位置和未來位置信息結合起來，提出PPFNx樹[8]、RPPF樹[9]等索引模型，打破了“多線”的限制。上述索引模型對于那些位置更新次數較少的移動對象的不確定性查詢具有很好的查詢效果，但是不能很好地處理移動對象頻繁的位置更新問題。文獻[10]提出了基于R-tree的自底向上的更新思想，其更新過程從樹的葉子節點開始，節省了查詢時間，從而提高了動態更新的性能，但是不足之處在于其索引的維護需要耗費大量的內存資源，從而導致系統的穩定性不高，且不適合解決頻繁位置變化范圍大的移動對象的問題。
Tao等人[11]提出U-tree的索引模型，U-tree具有良好的動態結構，使得數據的插入順序可以任意改變和更新，而且對不確定數據本身的概率密度分布沒有任何的限制。但是U-tree只適合于靜態的移動對象不確定性索引。文獻[12]提出了一種基于U-tree的高效率當前及未來不確定位置信息檢索的TPU-tree。TPU-tree在基本的U-tree結構上增加記錄移動對象不確定狀態特征的數據結構，通過利用概率密度函數描述移動對象在不確定區域的位置分布，在保留原有位置記錄的情況下加入時間特性，從而能對移動對象當前和未來位置信息進行檢索。文獻[13]在TPU-tree的基礎上增加一個記錄不確定移動對象狀態特征的更新備忘錄（UM）內存結構，提出了一種支持頻繁位置更新的不確定移動對象索引策略TPU2M樹，并提出了一種改進的基于備忘錄的更新/插入算法（MMBU/I）。MMBU/I算法利用UM控制不確定移動對象的位置更新，在保留原有記錄的情況下首先插入新記錄，減少了查找時所需要的磁盤I/O，從而提高更新效率。但是TPU2M樹需要額外的內存空間存放備忘錄的信息，當UM中的記錄個數逐漸增加時，需要增加額外的空間清洗操作來保證較高的更新效率，且當不確定移動對象個數較多時，更新后的葉子節點超過舊記錄的MBR（minimum bounding rectangle）的概率會逐漸增加，因此更新效率會逐漸降低。
文獻[14]提出一種基于Bx樹的不確定移動對象索引策略ABx樹，該索引模型利用矩形框推論法則和蒙特卡洛模擬相結合的方法預測移動對象未來的位置信息，并提出了高效的概率范圍查詢和概率K最近鄰查詢。但是ABx樹的不足之處在于，頻繁更新的移動對象位置信息使得資源消耗嚴重，增加更新代價。
通過對上述索引結構的介紹，可知對于頻繁位置更新的移動對象，設計索引結構時，如何減少由于移動對象頻繁的位置更新而引起的更新代價顯得十分必要。然而上述的索引結構，在考慮移動對象的位置變化時，只是針對單個移動對象，沒有將移動對象之間的運動軌跡進行關聯考慮。
基于以上問題，本文在TPU-tree的基礎上引入移動對象群組概念，將具有相似運動軌跡的移動對象劃分為一個群組，在同一個群組中只是對一個移動對象進行位置更新，其余移動對象值存儲分組信息，減少了位置更新次數，從而降低更新代價。
2.2 不確定對象數據模型
文獻[15]提出了目前較為流行的不確定數據模型——推測定位更新模型，其定義是無論何時只要移動對象的實際位置和數據庫中存放的位置超過一定的閾值th，就對移動對象的位置信息進行一次更新。有學者根據移動對象運動的不同應用場景，將數據模型劃分為不確定直線數據模型和不確定自由運動數據模型。前者主要是針對在路網約束下的移動對象，由于道路的約束，移動對象在未來的一段時間內只能分布在某一條直線上；后者對移動對象的運動軌跡沒有限制。結合不確定自由運動數據模型的特點，給出如下移動對象位置不確定數據模型的相關定義。
定義1（不確定區域[16]）移動對象Mi在t時刻的位置處于一個封閉區域URi(t)，其中URi(t)就是Mi在t時刻對應的不確定區域。
定義2（概率密度分布[16]）移動對象Mi在不確定區域URi(t)中的概率密度分布函數記為PDFi(x,t)，表示Mi在t時刻出現在位置x的概率。
結合定義1和定義2可知，在t時刻，移動對象Mi必然位于不確定區域URi(t)，易知概率密度分布函數在t時刻滿足∫URi(t)PDFi(x,t)dt=1。
如圖1所示為不確定移動對象在t時刻的分布示意圖。圖中白色的圓心位置就是移動對象當前存放在數據庫中的記錄位置，而陰影部分是移動對象的不確定區域URi(t)，其中不確定區域的半徑就是設定的閾值th，移動對象Mi可能分布在URi(t)中任意位置。具體的分布與概率密度分布函數PDFi(x,t)有關。最常見的概率密度分布函數為均勻分布。均勻分布認為移動對象Mi出現在不確定區域的任意位置的可能性都是一樣的，并不是在其中的某一點或某一區域具有較高的出現幾率。均勻分布有助于減少域查詢的CPU計算時間和磁盤I/O次數。針對不確定區域內的高斯分布，也有學者提出了基于平均值和方差的查詢計算方法。不同的概率密度分布函數采用不同的查詢處理方法。
Fig.1 Uncertain area圖1 不確定區域示意圖
2.3 軌跡相似性度量的計算
受移動對象的空間布局和不同傳感器采樣周期的限制，移動對象在環境中被感知到的數據通常是離散的。由于移動對象位置、移動速度及方向的動態變化，實時的聚類需要巨大的開銷。本文利用歷史位置和速度來描述對象的移動參數，通過移動參數來分析移動對象的軌跡情況，從而對移動對象進行群組劃分。
移動對象Mi的時空坐標為四元組(l,x,y,t)，其中l是Mi的標簽（label），表示移動對象的語義分類。在兩個移動對象Mi和Mj標簽已知的情況下，如果Mi和Mj具有相同的語義標簽，那么可以直接將他們劃分為一個群組。例如在景區中的同一個旅行團成員，在道路上的同一個車隊等。提前獲知移動對象的語義標簽可以直接進行分組，但更多情況下無法直接獲取移動對象Mi的語義標簽，此時就需要對移動對象的軌跡數據進行分析。x,y,t表示為在t時刻移動對象Mi的空間坐標為(x,y)。
移動對象Mi在t0時刻的位置信息為(l,x0,y0,t0)，經過ΔT,其t1時刻坐標變為(l,x1,y1,t1)。設Δx、Δy分別為沿x、y方向運動的變化量，移動速度為v，移動方向為θ，則：
對于移動對象的移動特性，已有研究側重相對方向[17]（relative direction，RD）和速率比[18]（speed ratio，SR）等方面。在已有研究基礎上，本文提出了空間距離（spatial distance，SD），并且通過RD、SR和SD三者間的結合提出了空間軌跡相似度（STS）度量公式。
關于移動對象Mi和Mj在t時刻的相對方向RD的計算見式（3），其定義為速度夾角的余弦值，夾角差越小，RD就越大，夾角差越小，意味著運動方向就越一致，兩者之間的差異性也就越小。
關于移動對象Mi和Mj在t時刻的速率比SR的計算見式（4），其定義為最小速度和最大速度之比，SR反映了Mi和Mj之間速度差異，當速度的差值越大時，SR越小，當二者速度相同時，SR值為1。
其中關于移動對象Mi和Mj在t時刻的SD的定義為兩者之間空間距離差，采用歐式距離來計算，當移動對象Mi和Mj空間上越接近，SD的值越小，反之越大。SD的計算公式如下：
STS描述了移動對象之間的空間軌跡相似度，STS的值依賴于SR、RD和SD。從前面的公式可知，移動對象之間的速度和方向越一致，RD和SR的值越大，反之則其值越小。而速度和方向越一致，體現兩個移動對象之間的空間軌跡相似度越高，從而說明STS與SR和RD成正相關。移動對象Mi和Mj之間空間距離越大，兩者之間的空間軌跡相似度越小，因此STS與SD成負相關，其計算公式如下：
3 GTPU-tree索引結構及相關算法
3.1 GTPU-tree索引結構
為了使索引結構支持移動對象群組劃分，從而在移動對象位置更新時，在同一組中的移動對象只需要對同組中的一個移動對象進行更新操作，減少更新次數，從而降低更新代價。GTPU-tree將整個索引結構劃分成3層。如圖2所示，GTPU-tree包含空間層、分組層和數據層。
（1）空間層
空間層用于描述移動對象所在空間的位置信息。空間層中節點的記錄形式
Fig.2 GTPU-tree index structure圖2 GTPU-tree索引結構圖
（2）分組層
分組層中GPTU-tree節點的記錄形式
由于GTPU-tree采用周期性更新和推測定位更新相結合的混合更新策略，當分組層中記錄當前組移動對象的位置信息MBR與ptr_r所指空間層節點記錄的位置偏差超過閾值th時，就更新數據，重新指定ptr_r。由于群組劃分基于歷史軌跡，而移動對象軌跡具有不確定性，為了使同一組中移動對象的運動軌跡盡可能保持一致，需要周期性地對分組情況進行更新。更新策略判斷ptr_g中所指向的小組成員過去一段時間的軌跡是否仍然可以劃分為一組，如果出現偏差較大的移動對象，就需要將與群體偏離較大的對象從組中移除。time_update就是記錄下一次檢查同組成員軌跡的時間。
如圖3所示，在T1時刻，移動對象M0～M9共劃分為G1和G2兩個群組。其中G1和G2的圓半徑就是同一組中移動對象之間位置信息差異的最大值。移動對象之間通過空間軌跡相似度STS進行群組劃分，STS越大，體現兩個移動對象運動狀態越相似。因此當STS大于閾值th時，將這些移動對象劃分為同一組，保存在GTPU-tree的同一個節點中，反之則劃分為不同群組，具體算法3.2節會有介紹。如圖（a）所示，T1時刻G1中含有{M1,M3,M5,M7,M9}，G2中含有{M0,M2,M4,M6,M8}。由于移動對象的空間位置和速度是在實時變化的，在T2時刻，M9對象與G1中的大部分對象的偏差較大，空間軌跡相似度STS較小，此時如果仍將M9劃分為G1，顯然是不合適的。因此需要周期性檢查同一組中移動對象之間的偏差，對移動對象重新進行群組劃分。
Fig.3 Group partition update圖3 群組劃分更新示意圖
（3）數據層
在數據層中每個GTPU-tree葉子節點的形式為＜oid,ptr,PCR(pi),MBR,v,pdf_ptr,next_flag＞。其中oid、ptr、PCR(pi)、MBR、v、pdf_ptr、next_flag分別表示移動對象Mi的標記、指向分組層節點的指針、概率限定性區域、記錄在數據庫中的位置、速度向量、概率密度分布函數和是否存在下一個標記。GTPU-tree的同一組中的移動對象彼此之間連續存放，當對組中的移動對象進行周期性檢測時，不僅判斷移動對象的空間位置和速度偏差是否超過閾值，還需要更新移動對象Mi的概率限定性區域。
3.2 移動對象群組劃分算法STSG
GTPU-tree中將歷史一段時間內具有相似運動軌跡的移動對象劃分為一個群組，然后將同一分組中的移動對象存放在GTPU-tree的同一個葉子節點中。關于移動對象群組劃分，提出了基于空間軌跡相似度群組劃分算法STSG。該算法不僅適合二維情況，也很容易擴展到三維或高維情況，為了研究問題的方便，這里以二維為例給出算法說明。下面是STSG算法中利用的一些定義。
定義3（直接可達）最小空間軌跡相似度STSMin是節點直接可達的判斷閾值，是一個常數。當STS (Mi,Mj,t)>STSMin時，認為在t時刻Mi和Mj直接可達，記為Mi?Mj，反之則Mi和Mj非直接可達，記為Mi/?Mj。
定義4（相依度可達）對于任意兩個節點Mi、Mj滿足Mi/?Mj，但存在Mk，令Mi?Mk和Mj?Mk，則稱Mi和Mj相依度可達，記為Mi?Mj，反之則Mi和Mj非相依度可達，記為Mi?Mj。
定義5（連接）對于任意兩個節點Mi、Mj滿足Mi/?Mj且Mi?Mj，但存在節點集合S(M1,M2,…,Mn), n>1，使得Mi和Mj能通過S相依度可達，則稱Mi和Mj連接，記為Mi≈Mj，反之則Mi和Mj非連接，記為Mi?Mj。
定義6（群組）將具有相似運動軌跡的移動對象劃分為一個群組，記為g，當且僅當g滿足下列兩個條件：
（1）任意節點Mi、Mj，如果Mi∈g且Mi?Mj| Mi?Mj，則Mj∈g；
（2）任意節點Mi、Mj，如果Mi∈g且Mj∈g，則Mi≈Mj。
STSG算法的目標是將所有相依度可達或直接可達的移動對象劃分為同一個群組，然后存放于GTPU-tree同一個葉子節點中，在進行位置更新時，對同一個群組中的移動對象只需對一個節點進行位置更新，而不需要對全體成員都進行位置更新，減少更新次數，降低移動對象位置更新的代價。
如算法1所示，首先初始化頂點數組V和鄰接矩陣E（第2～3行）；其次對移動對象數組M，計算任意兩個移動對象之間的空間軌跡相似度關系，將結果記錄在V和E中構成一個無向圖（第4～10行）；然后找到劃分群組的移動對象Mi，給Mi初始化一個分組g，通過廣度優先遍歷Mi所有相依度可達或直接可達的對象，將這些對象加入g中（第13～17行）；最后返回分組集合G。
算法1 STSG算法
3.3 GTPU-tree更新算法
移動對象的更新是比較棘手的問題，特別是高頻率下的位置更新請求。當移動對象發出位置更新請求時，新的記錄信息要插入到GTPU-tree中，且需要將過時的位置信息刪除。GTPU-tree分為空間層、分組層和數據層三層，在進行更新時每層數據都需要更新。其中分組層主要包含一些記錄群組成員的信息和位置信息，在進行更新時主要是進行指針重定位操作和賦值操作。空間層和數據層的更新操作比較復雜，著重介紹這兩層的更新算法。
在空間層，采用預測定位更新方法進行更新，當移動對象的實際位置和GTPU-tree中記錄的位置偏差超過閾值th時，進行更新操作。GTPU-tree空間層的索引結構是在R-tree的基礎上進行改進，更新方法與R-tree類似，按刪除、插入兩階段來進行移動對象的位置更新。
具體如算法2所示。算法主要分為兩個步驟：（1）刪除位置更新Mi所在的葉子節點L的舊記錄，利用CondenseTree函數對索引樹進行壓縮（第1～3行）。（2）將包含新的位置信息的記錄插入到GTPU-tree中，在插入過程中判斷插入位置的節點空間是否足夠，如果夠，則直接插入；如果不夠，則進行節點分裂，然后對GTPU-tree進行調整。
算法2 UpdateTree
在數據層對分組數據進行周期性更新。由于移動對象的軌跡存在不確定性，原先可以劃分為同一個群組中的移動對象，在運動一段時間后移動對象的運動軌跡發生變化，會有一些移動對象偏離群體，此時需要重新劃分群組。GTPU-tree采用周期性檢測的策略，對數據層中的移動對象檢測。
具體如算法3所示，首先獲取系統當前的時間t_now（第1行），將GTPU_tree中每一個群組中記錄的下一次更新時間與t_now進行比較，如果檢測到某分組需要更新，則將該組中所有對象存放進集合M，調用STSG算法重新對M進行分組（第2～5行）；比較新的分組G′和原先的分組G，如果發生改變，則將新的分組G′作為數據層添加到GTPU_tree中（第6～7行）；最后更新下一次更新的時間（第9行）。
算法3 Update_Group
4 實驗及分析
實驗利用Gist[19]對基于GTPU-tree、TPU-tree和TPU2M-tree等索引結構的算法效率進行了對比，并給出了評價與分析。實驗分析與對比主要從五方面進行設計。
第一部分為群組劃分算法STSG中的空間軌跡相似度STSMin大小對群組劃分結果和周期性群組更新的影響比較，通過實驗對比找出合適的STSMin閾值；第二部分比較了GTPU-tree和R-tree在范圍查詢下的性能；第三部分比較了不同移動對象數量下GTPU-tree、TPU-tree和TPU2M-tree的插入性能；第四部分對GTPU-tree、TPU-tree和TPU2M-tree在移動對象頻繁更新的情況下，通過比較I/O和CPU代價，分析三者間的更新性能；第五部分對比分析GTPU-tree、TPU-tree和TPU2M-tree在不同移動對象數量情況下的整體更新代價。
實驗數據集使用空間數據生成器（spatial data generator，SDG）生成，在2 000×2 000的空間區域內模擬移動對象的運動情況。移動對象不確定區域是一半徑為20的圓，移動對象速度控制在[20,30]，移動對象的概率密度分布是均勻分布。實驗假設移動對象在運動當中不會消失，中途沒有新增移動對象且在下一次群組更新時間前，同一分組的移動對象保持相同的運動軌跡，通過不同的移動對象更新數目反映移動對象的頻繁位置更新。實驗的硬件環境：CPU IntelCore i3 3.30 GHz，內存4 GB；操作系統Windows7；開發環境VS2010。
4.1 STSMin對群組劃分和更新的影響
本文算法STSG利用空間軌跡相似度STS的大小來度量移動對象之間歷史軌跡的相似性。在STSG算法中，最小空間軌跡相似度STSMin大小的設置直接影響了群組劃分效果的好壞。如圖4所示為STSMin大小對群組劃分結果的影響。從圖中可以看出，隨著最小空間軌跡相似度STSMin的增加，劃分群組的個數與STSMin呈正相關關系，也逐漸增加。這是因為隨著最小空間軌跡相似度STSMin的增加，移動對象軌跡判定為相似的要求更高，移動對象直接可達和相依度可達的數目減少，從而劃分結果中群組的個數增加。
Fig.4 STSMineffect on group partition圖4 STSMin對群組劃分的影響
為了保證同一分組內的移動對象具有相似的運動軌跡，需要周期性檢測同一分組內移動對象的運動軌跡。將那些偏離群體移動對象的離散個體找出，重新對其進行分組。一個好的群組劃分應該具有在未來一段較長時間內，分組中偏離群體的個數較少的特性。分組中移動對象軌跡越穩定，可以增大群體重新劃分的周期T，從而降低由于群體重新劃分引起的更新代價。如圖5所示為不同STSMin下，分組中偏離群體的移動對象個數變化情況。從圖中可以發現，隨著STSMin的增加，分組中偏離群體的移動個數逐漸減少。這是因為隨著STSMin的增大分組的個數增加，分組中的移動對象個數越少，但是分組內移動對象的歷史運動軌跡越接近。從而在未來一段時間內，移動對象仍然保持相似的概率增加，偏離群體的移動對象個數逐漸減少。
Fig.5 STSMineffect on the number of group deviations圖5 STSMin對群體偏離個數的影響
當群組劃分個數增大時，會增加GTPU-tree插入節點時的代價；同樣當偏離群體的移動對象過多時，為了保證同組中移動對象運動軌跡的相似性，需要縮小周期性群組更新時間T，增加了更新代價。從圖4和圖5中可以發現，當STSMin在[6,8]之間時，曲線變化率較大，表明在這個區間內STSMin取值對降低劃分群組個數和減少偏離群體的移動對象個數都有較好的效果。綜合考慮，在后續實驗中將最小空間軌跡相似度STSMin設置為6。
4.2 查詢性能
范圍查詢是移動對象數據管理中常見的查詢之一。本文通過范圍查詢來檢驗GTPU-tree的查詢性能。如圖6所示為不同查詢窗口大小（query windows size，QS）下GTPU-tree和R-tree的查詢效率對比。從圖中可以發現，GTPU-tree的平均查詢時間略高于R-tree的查詢時間。這是因為GTPU-tree整個索引結構劃分為空間層、分組層和數據層3層，索引結構相比較與R-tree復雜，索引樹的層次增多，所以查詢性能會有所降低。但GTPU-tree在降低更新代價的基礎上，仍和R-tree的查詢性能大致相當。
Fig.6 Performance of query圖6 查詢性能
4.3 插入性能
對于不同規模的移動對象集合，能否成功建立索引樹且構建索引的時間能否保持平穩是驗證索引結構插入性能關鍵。圖7展示的是移動對象分布圖。從圖中可以發現，移動對象均勻分布在2 000× 2 000的空間區域中。
Fig.7 Moving objects distribution圖7 移動對象分布圖
Fig.8 Performance comparison of insert圖8 插入性能對比圖
對于不同移動對象數目，GTPU-tree、TPU-tree和TPU2M-tree的插入時間如圖8所示。從圖中可以發現，這3者隨著移動對象數目的增加，所需時間均呈平穩增加的趨勢，且GTPU-tree花費時間少于TPU-tree和TPU2M-tree，說明GTPU-tree的插入性能優于TPU-tree和TPU2M-tree。這是因為隨著移動對象數目的增加，GTPU-tree中的空間層層次逐漸增加，索引中空閑空間增加，后續插入的新條目可以被直接插入的概率增大，插入所需要的操作也減少，從而減少了插入花費的時間；GTPU-tree相比于TPU-tree和TPU2M-tree提前進行群組劃分的操作，同一個群組中的移動對象可直接連續插入到分組層的節點當中，避免了TPU-tree和TPU2M-tree中逐個插入，所以GTPU-tree的插入性能優于TPU-tree和TPU2M-tree；TPU2M-tree和TPU-tree相比較，因為TPU2M-tree在插入一個新節點時，不僅需要插入到索引樹中而且還需要將其記錄到備忘錄的內存結構中，所以TPU-tree的插入性能會稍優于TPU2M-tree。
4.4 更新代價
由于移動對象位置的不確定性，為了保證查詢結果的精確性，需要同時更新數據庫和索引中的數據。對于位置頻繁更新的移動對象，更新代價十分巨大。考慮更新代價時，磁盤I/O和CPU是主要關心的兩個因素。更新次數和移動對象的數量是影響不確定移動對象更新代價的主要原因。圖9和圖10分別從移動對象群體軌跡穩定和群體頻繁偏離兩種場景下對GTPU-tree、TPU-tree和TPU2M-tree在不同更新次數下需要的更新代價進行了對比分析，分別對比了磁盤I/O代價（圖（a））和CPU代價（圖（b））；圖11和圖12分別從移動對象群體軌跡穩定和群體頻繁偏離兩種場景下對GTPU-tree、TPU-tree和TPU2M-tree在不同移動對象數量下的整體更新代價進行了對比分析。
Fig.9 Comparing I/O+CPU cost with group trajectories stable圖9 群組軌跡穩定下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 群組軌跡穩定下整體更新代價對比
Fig.12 Comparison of total cost with trajectories deviation圖12 群組頻繁更新下整體更新代價對比
從圖9和圖10的圖（a）中可以發現，不管是軌跡穩定還是群體頻繁偏離情況下，GTPU-tree比TPU-tree均大大減少了節點訪問（node access）次數，但略高于TPU2M-tree，而節點訪問次數又直接影響磁盤I/ O，從而可以說明，對于位置頻繁更新的移動對象，GTPU-tree在降低磁盤I/O上具有良好的性能，但略遜于TPU2M-tree。這是因為GTPU-tree與TPU-tree相比進行了移動對象分組處理的改進，將同一分組的移動對象保存在數據層的同一個葉子節點中。在進行位置更新時，對同一分組中的移動對象只需要更新一個移動對象，而不需要全部更新，減少了更新次數，降低了更新代價。而GTPU-tree的節點訪問次數略高于TPU2M-tree，這是因為TPU2M-tree采用自底向上的節點訪問策略，減少了查找時所需要的磁盤I/O，從而提高了更新效率。
對比圖9和圖10的圖（b）可以發現，GTPU-tree的CPU計算代價略高于TPU-tree且所占整體更新代價的比重也大于TPU-tree；但在移動對象群組軌跡穩定時GTPU-tree的CPU計算代價低于TPU2M-tree。這是因為TPU2M-tree在進行節點更新時，需要先查詢備忘錄，且當備忘錄中記錄個數增加時，需要進行額外的空間清洗操作，增加CPU計算代價。GTPU-tree認為在下一次群組更新前，同一分組的移動對象保持相同的運動軌跡，因此在兩個群組更新操作的時間段內，可以用一個移動對象的位置替代同組內的其他對象。但是由于移動對象軌跡具有不確定性，為了保證同一分組中移動對象軌跡的相似性，需要周期性進行群組重新劃分，增加了CPU計算代價。
對比圖11和圖12可以發現，無論是在移動對象群組軌跡穩定還是群組頻繁偏離的場景，GTPU-tree的整體更新代價都小于TPU-tree。當移動對象數量較小時，GTPU-tree的整體更新代價大于TPU2M-tree，但是隨著移動對數量的增加，TPU2M-tree的整體更新代價將超過GTPU-tree。這是因為對于TPU2M-tree，隨著移動對象數量的增加，索引樹的節點個數增加。每一個非葉子節點中含有的子節點個數具有限制，因此每一個非葉子節點的MBR逐漸減小。對于TPU2M-tree，當節點的MBR減小時，新插入節點超過原記錄所在的MBR的概率增加，而新節點超過原記錄的MBR時，此時等價于在索引樹中插入新記錄，更新效率降低。
對于GTPU-tree，當移動對象的數量增加時，每個群組中的移動對象個數也相應的增加，此時更有利于進行整體更新。特別在群組軌跡穩定情況下，GTPU-tree的優勢更加明顯。這是因為在移動對象群體軌跡穩定的情況下，相比于群體頻繁偏離情況進行群組重新劃分的更新周期T可以適當增大，所以在相同時間內，群組軌跡穩定的情況可以減少由群組重新劃分引起的CPU代價開銷，從而降低整體更新代價。此時GTPU-tree與TPU2M-tree的更新代價曲線的交點會提前。說明在群組軌跡穩定的情況下GTPU-tree可以在更少的移動對象數量下，在整體更新性能上優于TPU2M-tree。
5 結束語
本文在TPU-tree的基礎上，針對不確定移動對象頻繁位置更新代價較大等問題，提出了一種支持移動對象群組更新策略索引結構GTPU-tree，并提出了基于空間軌跡相似度的群組劃分算法STSG和移動對象群組更新算法。仿真實驗分析了對不同情形下GTPU-tree、TPU-tree和TPU2M-tree的性能比較，結果表明GTPU-tree在插入性能上全面優于TPU-tree和TPU2M-tree，即使在移動對象群體偏離頻繁的最差情況下，GTPU-tree的更新代價也能優于TPU-tree。GTPU-tree相比于TPU2M-tree，在移動對象數量較少時，更新代價略高于TPU2M-tree，但當移動對象數量較大時，GTPU-tree的更新代價將低于TPU2M-tree；在查詢性能方面，GTPU-tree雖增加了索引結構的復雜度，但查詢性能仍能與傳統索引大致相當。
[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.
附中文參考文獻：
[2]李佳佳,王波濤,王國仁,等.不確定移動對象的查詢處理技術研究綜述[J].計算機科學與探索,2013,7(12):1057-1072.
[12]丁曉鋒,盧炎生,潘鵬,等.基于U-tree的不確定移動對象索引策略[J].軟件學報,2008,19(10):2696-2705.
[13]丁曉鋒,金海,趙娜.支持頻繁位置更新的不確定移動對象索引策略[J].計算機學報,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—），男，浙江紹興人，南京航空航天大學計算機科學與技術學院碩士研究生，CCF會員，主要研究領域為時空數據庫，不確定移動對象索引技術等。
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—），男，吉林永吉人，南京航空航天大學副教授、碩士生導師，CCF會員，主要研究領域為時空數據庫，地理信息系統等。
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—），男，江蘇南京人，南京航空航天大學教授、博士生導師，CCF高級會員，主要研究領域為空間與時空數據庫，分布式數據管理與安全等。
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(國家自然科學基金);the Priority Academic Development Program of Jiangsu Higher Education Institutions(江蘇高校優勢學科建設工程資助項目);the Fundamental Research Funds for the Central Universities of China under Grant Nos.NP2013307,NZ2013306(中央高校基本科研業務費專項資金);the Youth Fund of Natural Science Foundation of Jiangsu Province under Grant No.BK20130819(江蘇省自然科學基金青年基金);the Open Foundation of Graduate Innovation Center in NUAAunder Grant No.kfjj20151607(南京航空航天大學研究生創新實驗室開放基金).
Received 2015-10,Accepted 2015-12.
CNKI網絡優先出版:2015-12-18,http://www.cnki.net/kcms/detail/11.5602.TP.20151218.1038.004.html
