時空數(shù)據(jù)庫索引技術(shù)研究

摘要:對時空數(shù)據(jù)庫中移動對象進行有效存取、查詢和更新的關(guān)鍵技術(shù)在于索引。深入分析了時空數(shù)據(jù)庫中的各種索引技術(shù)，最后討論了移動對象索引技術(shù)研究中的問題并對未來方向進行了展望。

關(guān)鍵詞: 時空數(shù)據(jù)庫; 移動對象軌跡;索引

中圖分類號:TP311文獻標識碼:A 文章編號:1009-3044(2010)02-268-03

Research on Spationtemporal Database Indices

ZHOU Yong-gang

(Department of Computer Technology， Anhui Vocational College of Posts and Telecom，Hefei 230031，China)

Abstract: To efficiently store， query and update trajectories of moving objects in spatio-temporal database，indexing techniques are sticking points. This paper thoroughly analyzed indexing methods for Spatio-Temporal Database， and finally some open researching problems and interesting direction were presented.

Key words: spatiotemporal database ; trajectories of moving objects; index

因為出現(xiàn)許多需要有效對移動對象管理的應(yīng)用，STDB受到很多關(guān)注。這些應(yīng)用需要在不同的時間戳記錄對象的地理位置(有時也記錄對象的形狀)，而且支持對它們歷史的和將來預(yù)期的特征進行查詢。

STDB的目的是根據(jù)數(shù)據(jù)的時間屬性作歷史性和預(yù)言性的檢索。具體地說，給定對象集合o1， o2，… ， oN(N是基數(shù))，對于每個對象oi(1≤i≤N)，歷史性STDB會存儲oi在歷史的所有時間戳t的有效范圍oi.E(t)。根據(jù)空間數(shù)據(jù)庫的原理，oi.E(t)能夠表示為一個描述對象在時刻t的真實形狀。尤其是，如果其形狀不是重要屬性，oi.E(t)則以一個點代替以表示oi在時刻t的位置。實際上，在連續(xù)時間戳，同一對象的有效范圍可以用不同的方法壓縮(例如:如果對象在幾個連續(xù)時間戳保持靜止，則它的有效范圍在該時間內(nèi)只需存儲一次)。

另一方面，對每個對象oi，預(yù)期性STDB會存儲它的最新更新的位置oi.L(tupd)(tupd:對象最新更新的時間)和用于描述它當(dāng)前移動特性時間函數(shù)。最適合的時間函數(shù)是線性函數(shù)，因為1)線性函數(shù)能夠近似描述任何運動軌跡，2)線性函數(shù)要求的參數(shù)個數(shù)最少。具體來說，除了oi.L(tupd)，系統(tǒng)只需記錄對象的速度oi.vel，就可以計算出在將來任何時刻t>tupd對象的位置:

oi.L(t) = oi.L(tupd)+oi.vel(t-tupd)

用這種模型只需在對象的時間函數(shù)的參數(shù)(如:速度)發(fā)生變化時采取更新數(shù)據(jù)庫。

人們已經(jīng)對作為支持時空查詢的輔助結(jié)構(gòu)的時空索引方法做了很多研究。時空存取方法主要集中在兩個正交方向:1)對對象過去位置的索引，2)對現(xiàn)在的位置和將來預(yù)期位置的索引。

1 移動對象歷史數(shù)據(jù)的時空索引

考慮到移動對象連續(xù)不斷發(fā)送它們的位置，保持所有的更新幾乎是不可能的。有兩種方法可用來減少歷史數(shù)據(jù):1)采樣，對數(shù)據(jù)流在某一時刻進行采樣。可以采用線性插值計算出相鄰采樣點間的線性軌跡。2)僅在變化時更新，移動對象僅當(dāng)它們的數(shù)據(jù)屬性(速度或方向)發(fā)生變化時才發(fā)送數(shù)據(jù)。我們把對歷史數(shù)據(jù)的時空索引機制分為三類。

第一類是在現(xiàn)存的空間索引方法加入時間屬性。這類時空索引方法主要是處理空間維，時間維是第二要素。

RT-tree[1]結(jié)合了作為空間存取方法的R樹和作為時間存取方法的TSB樹。在RT樹中，時間和空間信息是分開維護的。不管是葉結(jié)點還是非葉結(jié)點，每個索引項都包含(S，T， P) 形式。S是空間信息，T是時態(tài)信息(時間間隔)， P是指向子樹或?qū)ο蟮闹羔槨ｋS著時間變化，如果對象空間位置不變，則它的空間信息S不變，僅對時態(tài)信息進行更新。如果對象空間位置發(fā)生變化，則需要創(chuàng)建一個新的索引項插入RT樹。這種方法有許多局限性，一方面，如果變化對象的數(shù)量很大，許多索引項被創(chuàng)建，RT樹會迅速膨脹;另一方面，當(dāng)結(jié)點溢出時，怎樣分裂結(jié)點還沒有很好的解決辦法。

3D R-tree[2]把時間看作除了空間維以外的另一維。主要思想是為了避開時間和空間查詢之間的區(qū)別。3D R-tree可以直接利用現(xiàn)有的R樹算法來處理空間及時態(tài)查詢而無需修改，其前提是必須知道移動對象歷史軌跡存在的有效時間范圍，如果移動對象軌跡結(jié)束時刻不確定，那么3D R-tree將無法有效工作。比如若移動對象運動軌跡從某個歷史時刻開始一直延伸到當(dāng)前時刻，顯然包圍移動對象軌跡的3D MBR將會非常巨大且造成空間區(qū)域的大量重疊，直接導(dǎo)致3D R-tree的查詢搜索性能下降。因此，在應(yīng)用中要求移動對象軌跡是封閉的(closed)，即移動對象歷史軌跡必須在某個過去時刻終止而不能延伸到當(dāng)前時刻。由于3D R-tree將時間維與空間維等同索引，時間片查詢則必須掃描整個3D R-tree而非在此時間片下的有效子樹， 因此性能非常低下。

第二類是同時把空間和時間加入某一結(jié)構(gòu)中，但它們是各自獨立的。這是為了使在某一時刻所有有效的空間數(shù)據(jù)同時在一個索引結(jié)構(gòu)(R-tree)中。最高目標使為每一時間項都建立一個單獨的R-tree。這種方法需要很大的存儲量。

MR-tree[3]采用了在R-tree的背景下可重疊B-tree的思想。主要思想是避免每個時間戳都有單獨的R-tree而引起的存儲量過大。通過在連續(xù)的R-tree中不存儲相同的對象實現(xiàn)減少存儲量。作為替代，以不同根結(jié)點的鏈接指向同一結(jié)點，而所有的結(jié)點項都保存著它們在不同時間戳的值。這種思想對時間片查詢來說是完美的。搜索被指向適合的根結(jié)點，然后利用R-tree進行空間搜索。然而，它對時間窗口查詢的執(zhí)行是無效的。而且，一個主要的缺陷是存在許多重復(fù)項。考慮到這樣的情況，在連續(xù)兩個時間戳僅有一個結(jié)點項發(fā)生變化，而在這連續(xù)兩個R-tree的所有其它結(jié)點也必須重新復(fù)制。

HR-tree與[4]MR-tree非常相似。HR-tree是一種采用重疊技術(shù)、將單一版本的結(jié)構(gòu)轉(zhuǎn)換為部分固定結(jié)構(gòu)的高效時空索引結(jié)構(gòu)。該結(jié)構(gòu)為兩級索引機制，分別對時空對象的時間信息和空間信息進行索引:1)HR-tree是對事務(wù)時間進行索引，它按時間遞增順序?qū)r空對象的時間信息組織為有序表，并將時空對象不發(fā)生空間變化的那個時間片作為時空對象的時間信息值;2)用R-tree索引結(jié)構(gòu)為每個時間片的空間對象建立索引，并將R-tree的存儲信息(根結(jié)點存儲地址)保存到對應(yīng)時間片的時間索引結(jié)點中。為了節(jié)省空間，相鄰時間片的R-tree可能會重疊，即若相鄰時間片的R-tree有共同的分枝，則只保存該分枝的一個版本。

第三類是主要考慮時間維索引，其次考慮空間維。第三類方法主要集中在面向軌跡的查詢。在此類中處理空間查詢處于次要位置。

Trajectory-bundle(TB-tree)[5]是完全保持軌跡的類似R-tree結(jié)構(gòu)。一個葉子結(jié)點僅能包含屬于同一軌跡的線段。存在一個缺陷:在空間上比較靠近的不同軌跡的線段將被存儲在不同的結(jié)點上。構(gòu)建TB-tree是從左到右的原則。也就是說。最左邊的結(jié)點是最先插入的結(jié)點，最右邊的結(jié)點是最后插入的結(jié)點。

Scalable and Efficient Trajectory Index(SETI)[6]將空間區(qū)域分割成靜態(tài)且不重疊的分區(qū)，在每個分區(qū)下對移動對象的軌跡線段利用R樹進行索引。其考慮是，相對于無限連續(xù)變化的時間維而言，移動對象軌跡受空間范圍所限，那么可以把受限的空間區(qū)域利用某種規(guī)則靜態(tài)劃分以分而治之。良好的劃分函數(shù)應(yīng)盡量把同一移動對象不同軌跡線段聚類在同一個分區(qū)中。若一條軌跡線段穿過多個分區(qū)，那么必須將此線段裁剪并分別存儲在不同分區(qū)R樹中，這樣會導(dǎo)致查詢結(jié)果的重復(fù)，在查詢處理后必須進行重復(fù)結(jié)果的剔出。相應(yīng)地，時態(tài)查詢則被轉(zhuǎn)換為對折線段集合的空間窗口查詢，利用幾何計算方法可以得到空間窗口內(nèi)的折線段集合，其對應(yīng)的移動對象集合即是時態(tài)查詢結(jié)果。

2 移動對象當(dāng)前位置軌跡索引

在現(xiàn)實應(yīng)用中許多要求能夠有效地對移動對象當(dāng)前位置進行管理和查詢。相對來說，檢索移動對象當(dāng)前位置更具有挑戰(zhàn)性，其關(guān)鍵在于如何提高傳統(tǒng)空間索引的頻繁更新動態(tài)性能以滿足動態(tài)環(huán)境下的應(yīng)用要求。標準R樹更新算法采用刪除-重插機制來實現(xiàn)移動對象位置更新，頻繁更新會導(dǎo)致R樹性能急劇下降。為了支持R樹的頻繁更新操作，近年來提出的方法包括LUR樹(Lazy Update R-tree)、自底向上更新策略(Bottomup Update)、哈希方法(Hash)等。LUR[7]提出了一種延遲更新(Lazy Update)策略，即若移動對象位置未超出當(dāng)前節(jié)點MBR，算法僅僅更新移動對象所在的數(shù)據(jù)頁面并維持索引頁面不變;對于移出MBR之外的移動對象，根據(jù)其超出MBR程度大小，判斷是否將MBR進行有限擴展以包含移動對象新位置;或者利用標準R樹更新算法進行更新以盡量減少位置更新所帶來的索引樹更新操作。Bottom-up Updates的自底向上法擴展了LUR-tree思想。自底向上法比較適合處理移動對象的連續(xù)更新。例如:擴展MBR以包含新的值和移動當(dāng)前對象到兄弟結(jié)點。

Song 等人利用空間劃分的思想來索引移動對象當(dāng)前位置，首先靜態(tài)地把空間劃分為可以相互重疊的區(qū)域，然后根據(jù)當(dāng)前位置將移動對象哈希映射到不同區(qū)域中去。只有當(dāng)移動對象位置超出了當(dāng)前區(qū)域才會更新此對象的索引記錄，數(shù)據(jù)庫中保存了移動對象位置近似視圖。

3 當(dāng)前和將來軌跡查詢索引

在移動計算、位置服務(wù)等新興應(yīng)用中，需要對移動對象當(dāng)前及未來位置預(yù)測以提供相關(guān)服務(wù)，針對移動對象當(dāng)前和未來軌跡的索引方法是目前研究的熱點。為了能夠預(yù)測移動對象未來軌跡，需要存儲一些額外的信息(如移動對象當(dāng)前速度和目的地等)。然后根據(jù)移動對象當(dāng)前的運動特性對未來軌跡進行預(yù)測，目前通常使用線性方程來描述移動對象的運動特性。在D維空間下，移動對象運動特性可以使用參考時間tref時位置xref = ( x1，x2，…，xd )以及速度矢量v=(v1，v2，…，vd )來描述。移動對象在任何時間點t (t≥tref )的位置可利用公式xt = xref +v (t- tref )計算得出。主要的索引方法有:FT-Quadtree、PMR-Quadtree、STRIPE索引、TPR-tree、TPR*-tree等。

FT-Quadtree[8]使用的是Quad-tree索引結(jié)構(gòu)，最大的特點是使用了軌跡共享技術(shù)來最大限度地減少數(shù)據(jù)的存儲數(shù)量，提高索引的更新效率。在這種樹中的葉子節(jié)點結(jié)構(gòu)表示為(oid，軌跡的數(shù)量，起始坐標，結(jié)束坐標，起始時間，結(jié)束時間，其他信息)。對于在同一時間內(nèi)的節(jié)點而言，如果它們的坐標位置相同或者接近，那么就可以采取共享策略把若干個節(jié)點的內(nèi)容放入一個公共的節(jié)點內(nèi)，這樣就可以明顯地減少存儲的空間。

使用PMR-quadtree[9]作為索引將來軌跡的基本空間存取方法，關(guān)鍵的一點是當(dāng)移動對象發(fā)生更新時，整個索引結(jié)構(gòu)被破壞，然后根據(jù)新的信息重建索引結(jié)構(gòu)。為了避免過多的更新操作，索引每ΔT時間單元重建。在理論上，無限的時間維可以分割為大小為ΔT的相等的時間片。對于每一時間片，會構(gòu)建一個新的基于運動方程的PMR-tree。然而，由于存儲設(shè)備的有限性，只有當(dāng)前的PMR-tree會被存儲。

TPR-tree[10]使用時間參數(shù)化包圍框來包含移動對象，其索引結(jié)構(gòu)與R樹類似。但TPR-tree采用謹慎的BR策略，在某些時刻(如構(gòu)建時刻)包圍框是最小的，但在其后的時間內(nèi)往往不是。從一維角度考慮，MBR最(大)小邊界速度為其范圍內(nèi)所有點的最(大)小速度，從而保證所有點始終包含在同一個MBR中。TPR-tree索引節(jié)點記錄不僅存儲了移動對象(子樹)MBR，而且包含了移動對象(子樹)MBR速度矢量。由于節(jié)點MBR呈現(xiàn)出一種隨時間變化的動態(tài)性，隨著時間延伸包圍框會越來越大，導(dǎo)致空間區(qū)域的大量重疊從而使得性能下降。因此，必須在適當(dāng)時候?qū)PR-tree進行重構(gòu)以提高查詢性能。

TPR*-tree[11]修改了TPR-tree的動態(tài)操作算法。通過維護一個代價下降優(yōu)先隊列保證插入路徑選擇的全局最優(yōu)，保持TPR-tree MBR的緊致性以提高查詢性能。對于上溢節(jié)點的分裂算法，TPR*-tree只是在必要的時候才對節(jié)點分裂并重插。以二維空間移動對象為例，節(jié)點首先在所有可能的8個方向(4×d)上進行排序，并從中選擇一種最好的分裂方式，實際上此時節(jié)點并不分裂，而是把節(jié)點中30 %的記錄刪除后重插。如果在重插過程中發(fā)生上溢，那么就直接進行節(jié)點分裂以避免傳遞操作。TPR*-tree是目前最好的參數(shù)化空間訪問方法。

4 結(jié)束語

該文總結(jié)了移動對象軌跡索引的各種技術(shù)，并對它們進行了比較詳細的分類，對每種方法均找出了多個比較典型的模型進行介紹。近年來對移動對象歷史軌跡、當(dāng)前位置與未來趨勢預(yù)測的索引方法研究較多，在如何同時解決上述三種查詢的索引方法上研究仍然欠缺。多種索引結(jié)構(gòu)的結(jié)合是時空數(shù)據(jù)庫系統(tǒng)實際設(shè)計的主要趨勢，選擇哪幾種索引結(jié)構(gòu)以及如何把它們有機地結(jié)合起來將是系統(tǒng)設(shè)計所面臨的主要難題。

參考文獻:

[1] Xu X， Han J， Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases. In Proc. of the Intl. Symp. on Spatial Data Handling， SDH， pages 1040–1049， July 1990.

[2] Basch J， Guibas L J， Hershberger J. Data structures for mobile data. In Proc. of the ACM-SIAM symposium on Discrete algorithms， SODA， pages 747–756， 1997.

[3] Xu X， Han J， Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases. In Proc. of the Intl. Symp. on Spatial Data Handling， SDH， pages 1040–1049， July 1990.

[4] Nascimento M A， Silva J R O. Towards historical R-trees. In Proc. of the ACM Symp. on Applied Computing， SAC， pages 235–240， Feb 1998.

[5] Pfoser D， Jensen C S， Theodoridis Y. Novel Approaches in Query Processing for Moving Object Trajectories. In Proc. of the Intl. Conf. on Very Large Data Bases， VLDB， pages 395–406， Sept. 2000.

[6] Chakka V P， Everspaugh A， Patel J M. Indexing Large Trajectory Data Sets with SETI. In Proc. of the Conf. on Innovative Data Systems Research， CIDR， Asilomar， CA， Jan. 2003.

[7] Kwon D， Lee S， Lee S. Indexing the Current Positions of Moving Objects Using the Lazy Update R-t ree[C]// In :Proc. of MDM，2002.

[8] Ding R， Meng X F， Bai Y. Efficient Index Maintenance for Moving Objects with Future Trajectories[C]// Kyoto: The 8th International Conference on Database Systems for Advanced Applications(DASFAA)， 2003. 183.

[9] Tayeb J， Ulusoy O， Wolfson O. A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal，41(3):185–200， 1998.

[10] Saltenis S， J ensen C S， Leutenegger S T， et al. Indexing the Positions of Continuously Moving Objects [C]// In :Proc. of ACM SIGMOD， 2000.

[11] Tao Y， Papadias D， Sun J. The TPR*-Tree : An Optimized Spatio-Temporal Access Method for Predictive Queries[C]// In :Proc.of VLDB， 2003.