動態目標移動數據管理技術研究

許桂明 孫文俊

中國電子科技集團公司第二十八研究所 江蘇 210007

0 引言

對于實時處理信息系統而言，準確全面快速地獲取信息的同時還需要能夠對獲取的動態信息進行有效的管理和利用，并能從更高層次上挖掘信息后面的知識。在時域空域全方位的預警監控過程中，信息系統積累了海量的動態目標移動位置數據。由于移動目標數量龐大，位置變更頻繁，造成數據頻繁更新或數據過時失效，使用傳統的數據庫技術和數據挖掘技術難以對這些數據進行有效的管理和利用。當前，在實時信息系統所擁有的數據中，很大一部分是動態目標運動信息，然而：(1)動態目標運動信息沒有得到有效的組織與管理。目標的移動信息不能根據時間和空間約束條件進行基于位置的檢索；(2)動態目標運動信息沒有得到更進一步的挖掘利用。利用有效的挖掘手段，從微觀上說，可以通過目標歷史行為預判其下一步運動軌跡，或者通過目標行為來輔助進行目標屬性的識別判定。從宏觀上說，也可以分析得到相關域的目標時空分布特征。然而在實際應用場景中，缺乏對這些動態目標運動信息的分析與挖掘，甚至經常會由于數據積累過快，大量有價值的目標歷史運動數據被毫不猶豫地刪除。

1 移動對象數據庫概述

移動對象數據庫是以存儲和管理隨著時間變化的移動目標為目標，是從二十世紀末期開始，在空間數據庫、時態數據庫以及時空數據庫的基礎上發展起來的一個比較新的研究領域，主要應用于交通管理領域。已有的研究主要集中于移動對象數據模型、移動對象數據索引結構與查詢技術等方面。一些研究機構開發了原型系統以佐證其研究理論成果。目前，各大數據庫廠商比如ORACLE、IBM等，在其數據庫產品中提供了相關的時空數據管理功能，但是市場上尚沒有可以應用的成熟的移動對象數據庫產品。本文研究如何應用移動數據庫相關的概念來管理動態目標運動信息，為進一步的實際應用提供參考。

海量數據的有效應用之一是數據挖掘。數據挖掘技術的目標是從大量、不完全、有噪聲、模糊、隨機的數據中，提取隱含在其中的，人們事先不知道但又是潛在有用的信息的過程。近年來，數據挖掘的研究對象已經從事務型數據庫擴展到空間數據庫、時空數據庫、移動對象數據庫等。時空數據挖掘，以經典的數據挖掘理論為基礎，主要受到空間數據挖掘和時態數據挖掘研究的影響，并同時還受到時空數據表示和存取方式的限制。通過各種時空數據挖掘技術對移動目標歷史數據進行挖掘，可以實現對目標的運動趨勢的預測，以及輔助判定目標的屬性。

2 數據建模

移動對象數據模型是移動對象數據庫的核心，也是時空數據挖掘的基礎。移動對象的數據模型是描繪現實中移動對象、移動對象之間的時空聯系以及語義約束的模型。以往的研究中提出了多種時空對象模型，主要有基于版本的時空數據模型、基于事件的時空數據模型、基于對象的移動對象數據模型等幾個派系。

在某實時系統中，動態目標以批為單位進行處理，每批目標被視為時空中的一個點，在二維平面上進行無約束的運動，該實時信息系統中動態目標數據形式化定義如下：設D為動態目標數據集，D=g0gggggg，其中d為其中一批目標。設 d={id,F,P}，其中，id為目標惟一標識符；F為目標的屬性集，P為目標運動行為點跡集合，或者稱為目標是動態時空屬性集。設F={f}，f為目標的一個屬性。動態目標的屬性包括大小、形狀、數量、顏色等，所有屬性都是離散的。設f={}，其中，f(ai)=wi，表示目標特征f的值等于ai的概率為 wi。設 P={p}，其中，p為一個目標移動位置點，p=，t為位置點錄取時間，lon為位置點錄取位置經度，lat為位置點錄取位置緯度。

參考O. Wolfson等人提出的MOST模型，將目標位置點p擴充為p=，其中，f(t)為目標位置隨時間變化的函數。因為目標位置是變化頻繁，而目標的運動函數變化會少很多。在允許一定誤差的條件下，可以以低得多的頻率更新目標信息。

3 移動對象數據庫關鍵技術

3.1 索引處理技術

如果要實現基于時間范圍與位置范圍的查詢，必須對移動對象數據庫建立具有相應功能的索引結構。在移動對象數據庫中，移動對象都不斷地更新它們的位置，在大多數情況下其更新頻率遠遠高于查詢頻率，因此，理想的移動對象索引不僅需要能夠支持快速的查詢，更應該具備高效的更新能力。迄今為止，研究人員提出了一系列時空對象索引技術。按照索引的數據時間范圍，索引方法可以歷史位置索引和當前位置索引；按照索引的數據類型，索引方法可以分為基于離散數據的索引方法和基于連續數據的索引方法；按照移動對象所處環境不同，索引方法可以分為無約束環境和有約束環境的索引方法等等。為了增加索引更新效率，可以采取基于緩沖(基于內存緩沖或者基于磁盤緩沖)的方法進行批量插入和批量刪除操作。

在這里，簡單介紹一下R-Tree索引結構。其它各種時空數據索引，大多是在 R-Tree基礎上進行改進得到。R-Tree是B-Tree在二維空間的擴展，是一種典型的空間索引技術，結構見圖1。

R-Tree的節點元素是二元組{oi , MBRi}，其中，oi表示對象標識(葉子節點)或者指向子樹根節點的指針，MBRi表示該目標在數據空間內的最小包含矩形框。樹的性質與B-Tree相似，具有自動平衡、空間利用率高、適合外存存儲等。但是有一點重要的區別，如圖1左所示，中間節點的矩形框存在重疊，導致查詢可能有多條路徑。

圖1 R-Tree平面示意圖與結構示意圖

動態目標索引屬于連續數據類型的無約束運動索引，因此可以將基于歷史位置的索引和基于當前與將來位置的索引分開創建以支持不同的查詢任務。(1)基于歷史位置的索引，只執行插入工作，因為數據量大，需要龐大的存儲空間，以文件的形式存在。已有的基于歷史位置的索引結構如RT-Tree，在現有空間數據索引技術上添加時間信息，難以進行時間片查詢；MR-Tree、HR-Tree、MV3R-Tree等，將時間作為獨立的維度處理，能有效支持時間片查詢，但是空間消耗大。為了節省空間，參考系統的實際需求，設計相應的數據選擇與數據過期策略，比如只索引關注目標的信息，另外根據時間范圍進行分區索引，等等。(2)基于當前與將來位置的索引。這類索引會存儲并更新移動對象當前位置及位置隨時間變化的函數，即目標的MOST模型，所以可以查詢將來一定時間內的位置信息。典型的基于當前與將來的索引有TPR-Tree，LGU結構以及BX-Tree等。TPR-Tree在R-Tree的基礎上，另外存儲最小矩形框四邊的當前速度。TPR-Tree支持對現在和將來的查詢，其中間節點元素可以表達為，其中，V=，四個變量分別表示最小矩形四邊的運動速度，而葉子節點可以表示為，其中V=，兩個變量分別表示為目標在兩個方向上的速度。LGU結構在TPR-Tree上加入輔助結構以提高插入、刪除與檢索的效率。

3.2 查詢處理技術

動態目標的查詢，需滿足屬性值約束、時空約束兩類條件，比如查詢某區域范圍一周內某類目標活動情況等。因移動對象的查詢類型根據查詢的空間謂詞不同，時間謂詞以及對象所在空間的不同分為不同的類型。

按空間謂詞不同，移動對象的查詢可以分為：(1)范圍查詢，即查詢一定時間段內給定區域的所有對象，是最基本的應用，最廣泛的查詢類型；(2)鄰近查詢，即查詢某時間段哪些對象距離給定目標點最近。鄰近查詢中最通常的類型是K鄰近查詢(KNN)，即查找最靠近查詢點的K個對象。(3)連續查詢，即指在某個時間區域內查詢符合條件的目標集。在該時間區域內，由于移動對象位置的改變，查詢結果隨著數據的不斷更新也要不斷的改變；(4)密度查詢，即查找在某段時間內移動對象密集的空間區域，或找到移動對象在某個時刻點的密集區域。

按時間謂詞不同，移動對象的查詢可以分為歷史查詢、當前查詢和將來查詢，分別對應三種時態的數據，使用不同類型的索引支持。(1)對于歷史查詢和當前查詢，R樹的點查詢和范圍查詢算法是比較有效的，因此這些索引基本上沿用R樹的傳統查詢處理方法；(2)對于將來查詢，需要使用基于將來位置的索引，而查詢的準確程度則取決于索引中使用的預測模型。針對歷史數據和當前數據的范圍查詢，因為結果確定，所以處理比較簡單，各種移動對象索引對它們的處理方式大同小異；而將來范圍查詢，由于帶有預測性質，難度大大增加，因此成為人們研究的焦點。

移動對象查詢根據移動對象所在的空間分為歐氏幾何空間的查詢和網絡空間中的查詢，分別對應于有約束的目標運動與無約束的目標運動，其距離度量分別為歐幾何距離與網絡距離(網絡上兩點間的最短路徑距離)。某實時系統中動態目標的運動可近似于二維平面上的無約束運動。

現有研究主要以K近鄰思想為主進行相應的擴展。這里簡單介紹一下TPR-Tree上的KNN查詢。TPR-Tree是最基本的基于當前與將來的移動對象索引結構，其它類型索引上的查詢可以參照TPR-Tree上的算法改進得到。

首先，定義設對象 o1，o2之間在 t時刻的距離為d(o1,o2,t)；同時設對象o與矩形框MBR在t時刻的最小最大距離分別為min(o,MBR,t)和max(o,MBR,t)。距離的計算為歐式距離，公式略。確定查詢時間間隔為 t，查詢結果為{}，表示在t1至t2時間范圍內，目標o是屬于查詢對象的最近K個鄰居之內。設查詢對象為o，只對當前目標進行查詢的思想為：根據與查詢對象的最小距離，對TPR-Tree所有層上的節點進行排序。深度周游 TPR-Tree，在訪問的過程中更新查詢對象的k近鄰列表。這其中最重要的是高效的剪枝策略，盡量避免無效的子樹周游。如果要對某個時間范圍進行查詢，則需要對時間范圍進行分片，對其中的所有時刻進行如上查詢，最后綜合得到查詢結果。

4 移動對象數據庫的實現

當前僅有少數學者和研究機構實現了用于試驗理論或算法效果的移動對象數據庫原型系統(比如O. Wolfson等人實現的DOMINO)，尚沒有可以應用的移動對象數據庫產品。已有的研究提出了多種實現結構，包括層次型結構，即在傳統的關系型數據庫管理系統上加入一個時空層，來承擔時空數據操作與傳統關系型數據操作之間的翻譯及查詢優化等工作，限于關系型數據庫的局限，這種方式基本不可取；另一種是擴展性結構，在對象關系數據庫管理系統上進行內核層次的時空數據擴展，包括各種索引結構、查詢實現等，這種方式是比較自然而清晰的，但是會缺少數據庫本身提供的查詢優化支持。

如今主流的數據庫產品逐步提供了對象擴展功能，ORACLE提供了 Cartridge技術，以及空間數據管理擴展模塊Oracle Spatial和時間序列模塊Oracle Timeseries。如今移動對象數據庫的各種研究尚在開展階段，存在很多問題，難以實現完備的移動對象數據庫管理系統，但是借助如 Oracle等廠商提供的工具的支持，可以借鑒研究中的合理的思想，進行相應的擴展，以更好地管理和利用海量的動態目標運動數據。

5 總結

本文論述了移動對象數據庫的數據模型，研究了移動對象數據庫包括索引處理技術與查詢處理技術等關鍵技術，并對移動數據庫的具體實現進行了闡述，對有效管理實時系統中動態目標應用產生的海量數據具有一定的意義。

[1]Ouri Wolfson, Bo Xu, S. Chamberlam, Moving Objects Databases: Issues and Solutions. In: Proc. of 10th Intl. Conf. on Scientific and Statistical Database Management.1998.

[2]Ouri Wolfson, Moving Objects Information Management:The Database Challenge In Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems.2002.

[3]Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref, et al.PLACE: A Query Processor for Handling Real-time Spatiotemporal Data Streams. In: Nascimento, Mario A, zsu eds. 30th International Conference on Very Large Databases. Toronto,Canada. 2004. St. Louis, SA: Morgan Kaufmann Publishers Inc.1377～1380.

[4]T.Sellis,Chorochronos:research on spatiotemporal database systems.In:Trevor Bench-Capon, Giovanni Soda, A Min Tjoa.10th International Conference on Database and Expert Systems Applications. Florence, Italy. 1999. Springer Verlag :Springer-Verlag Telos.452～456.

[5]A.Guttman. R-Trees:A Dynamic Index Structure for Spatial Searching, Proc. ACM SIGMOD. 1984.