動態(tài)目標(biāo)移動數(shù)據(jù)管理技術(shù)研究

許桂明 孫文俊

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

0 引言

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

1 移動對象數(shù)據(jù)庫概述

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

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

2 數(shù)據(jù)建模

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

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

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

3 移動對象數(shù)據(jù)庫關(guān)鍵技術(shù)

3.1 索引處理技術(shù)

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

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

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

圖1 R-Tree平面示意圖與結(jié)構(gòu)示意圖

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

3.2 查詢處理技術(shù)

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

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

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

移動對象查詢根據(jù)移動對象所在的空間分為歐氏幾何空間的查詢和網(wǎng)絡(luò)空間中的查詢，分別對應(yīng)于有約束的目標(biāo)運動與無約束的目標(biāo)運動，其距離度量分別為歐幾何距離與網(wǎng)絡(luò)距離(網(wǎng)絡(luò)上兩點間的最短路徑距離)。某實時系統(tǒng)中動態(tài)目標(biāo)的運動可近似于二維平面上的無約束運動。

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

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

4 移動對象數(shù)據(jù)庫的實現(xiàn)

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

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

5 總結(jié)

本文論述了移動對象數(shù)據(jù)庫的數(shù)據(jù)模型，研究了移動對象數(shù)據(jù)庫包括索引處理技術(shù)與查詢處理技術(shù)等關(guān)鍵技術(shù)，并對移動數(shù)據(jù)庫的具體實現(xiàn)進行了闡述，對有效管理實時系統(tǒng)中動態(tài)目標(biāo)應(yīng)用產(chǎn)生的海量數(shù)據(jù)具有一定的意義。

[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.