許桂明 孫文俊

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

0 引言

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

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

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

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

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

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

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

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

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

3.1 索引處理技術(shù)

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

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

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

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

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

3.2 查詢處理技術(shù)

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

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

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

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

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

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

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

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

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

5 總結(jié)

本文論述了移動(dòng)對象數(shù)據(jù)庫的數(shù)據(jù)模型，研究了移動(dòng)對象數(shù)據(jù)庫包括索引處理技術(shù)與查詢處理技術(shù)等關(guān)鍵技術(shù)，并對移動(dòng)數(shù)據(jù)庫的具體實(shí)現(xiàn)進(jìn)行了闡述，對有效管理實(shí)時(shí)系統(tǒng)中動(dò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.