時(shí)空數(shù)據(jù)庫(kù)中的移動(dòng)對(duì)象索引研究

摘 要：主要探討了近年移動(dòng)對(duì)象索引結(jié)構(gòu)的研究成果，對(duì)不同的研究方法給出了比較，并且給出了移動(dòng)對(duì)象索引結(jié)構(gòu)的問題和發(fā)展方向。

關(guān)鍵詞：時(shí)空數(shù)據(jù)庫(kù)； 移動(dòng)對(duì)象索引； 空間數(shù)據(jù)庫(kù)

中圖法分類號(hào)：TP311.132 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1001-3695(2006)10-0166-03

Research on Mobile Objects Index in SpatioTemporal Database

LV Junlong1，LIU Zhaohong1，LI Yan1，GE Junwei1，HaeYoung BAE2

(1.Research Institute of GIS， Chongqing University of Posts Telecommunication， Chongqing 400065， China;2.Dept. of Computer Science Engineering， INHA University， Inchon， Korea)

Abstract:This paper researches the most kinds of mobile objects index structures and gives a compare with them. In the end the main difficulty and research direction in the mobile index structure was proposed.

Key words： SpatioTemporal Database; Mobile Objects Index; Spatial Database

數(shù)據(jù)庫(kù)技術(shù)發(fā)展到今天，關(guān)系數(shù)據(jù)庫(kù)是最成熟的，包括最常使用的Access， SQL Server， Oracle 等，但是它們均不能對(duì)空間的和時(shí)間的數(shù)據(jù)庫(kù)進(jìn)行管理。要管理時(shí)間和空間數(shù)據(jù)，必須考慮以下的兩個(gè)因素：①數(shù)據(jù)存放問題，時(shí)空數(shù)據(jù)庫(kù)存放的不僅是當(dāng)前的對(duì)象屬性，還有歷史的屬性，這樣就需要大量的磁盤空間；②實(shí)時(shí)性問題，時(shí)空數(shù)據(jù)庫(kù)的數(shù)據(jù)量要遠(yuǎn)遠(yuǎn)大于一般的關(guān)系數(shù)據(jù)庫(kù)，特別是在空間謂詞查詢的求值開銷。在這種情況下若沒有索引，按照存儲(chǔ)順序掃描的方法來查詢，花費(fèi)的時(shí)間是讓人無法忍受的，而且查詢所得的結(jié)果往往是過時(shí)的。在這種需求下，移動(dòng)對(duì)象的索引技術(shù)成為研究的熱點(diǎn)，相當(dāng)多的移動(dòng)對(duì)象索引方法被提了出來。本文綜合了當(dāng)前研究的主要空間索引方法，并且給出了移動(dòng)對(duì)象空間索引所面臨的難題。

1 索引移動(dòng)對(duì)象的方法歸類

表1給出了當(dāng)前移動(dòng)對(duì)象索引研究的主要類別。

表1 索引移動(dòng)對(duì)象歸類表

2 軌跡索引

2．1 有限制的軌跡索引

限制軌跡索引可以分為網(wǎng)絡(luò)限制索引和構(gòu)造（Infrastructure）限制索引。前者主要針對(duì)的是道路上面的移動(dòng)對(duì)象，如汽車、火車等；后者針對(duì)的是陸地上的各種移動(dòng)對(duì)象在實(shí)際運(yùn)動(dòng)中要受到的各種限制，如湖泊、停車場(chǎng)等情況下的索引結(jié)構(gòu)。

2．1．1 網(wǎng)絡(luò)限制索引

在陸地上運(yùn)動(dòng)的物體有相當(dāng)大的一部分是有固定運(yùn)動(dòng)軌跡的，這主要包括汽車、火車等各種車輛，它們的運(yùn)動(dòng)主要是沿著固定的道路，人們查詢它們的位置常常關(guān)心的不是其絕對(duì)物理位置，如經(jīng)緯度坐標(biāo)，而是更關(guān)心它們的相對(duì)位置，如距離哪個(gè)車站比較近，大概在哪個(gè)大樓附近，在哪個(gè)公路的多少公里處等。對(duì)于索引可以把二維的平面坐標(biāo)簡(jiǎn)化為一維的坐標(biāo)，比較常見的轉(zhuǎn)換方法有Z曲線和Hilbert曲線。它的優(yōu)點(diǎn)是索引方便，可以利用已有的索引結(jié)構(gòu)，如B樹、哈希結(jié)構(gòu)等，同時(shí)也可以對(duì)空間對(duì)象進(jìn)行排序。但是這樣也存在一定的問題，無論現(xiàn)在使用最多的Z曲線還是Hilbert曲線，它們均不可能完全反映空間的相鄰狀況，也就是說在實(shí)際空間中相鄰物體的物理存儲(chǔ)位置是不相鄰的，這樣對(duì)于空間鄰居查詢帶來很大的開銷。

這方面的研究主要有文獻(xiàn)[11]，其主要思想是將多維的道路轉(zhuǎn)換為一維的來存儲(chǔ)，這樣就可以利用現(xiàn)有的數(shù)據(jù)庫(kù)管理系統(tǒng)，實(shí)現(xiàn)起來比較容易，如圖1所示。

2．1．2 構(gòu)造限制索引

由于在現(xiàn)實(shí)世界中對(duì)象的移動(dòng)要受到各種各樣的限制，如大的湖泊、巨大的建筑物，這樣我們就可以把對(duì)象不可能到達(dá)的范圍去掉來減少查詢的范圍，提高查詢的效率。對(duì)于這種情況索引的結(jié)構(gòu)可以不作改變，但對(duì)其一般的查詢算法要進(jìn)行相應(yīng)的改進(jìn)。在文獻(xiàn)[12]中提出了一個(gè)三步查詢方法：①對(duì)原始的查詢窗口進(jìn)行分割處理，把一個(gè)大的窗口分成幾個(gè)小的窗口集合，分割的依據(jù)是查詢窗口中的構(gòu)造物。②對(duì)第①步產(chǎn)生的小窗口集合進(jìn)行查詢，將查找的結(jié)果作為下一步的查詢對(duì)象。③在所有的結(jié)果中找出要查詢的對(duì)象。

在圖2中外側(cè)矩形為查詢窗口，內(nèi)部的黑色矩形為障礙物，為了減小查詢的矩形范圍，把外側(cè)的大矩形分為若干個(gè)小矩形，如圖內(nèi)的白色小矩形。按照上面提到的三步查詢方法，先分割查詢窗口，就是上面提到的白色小矩形，然后在每個(gè)白色小矩形中進(jìn)行查詢，返回一系列的查詢結(jié)果，最后在查詢結(jié)果集合中查找滿足條件的對(duì)象。

2．2 沒有限制（Unconstrained）的軌跡索引

2．2．1 索引過去和現(xiàn)在的軌跡

在這方面的研究主要有SETI索引[2]、SEBtree(Start/End time stamp Btree)[8]、XBR trees(Structures obeying the Embedding Space Hierarchy)[5](XBR tree 是基于Quad 樹的結(jié)構(gòu))、TBtree(TrajectoryBundle tree)[7]和STRtree(SpatioTemporal Rtree)[6]。

如圖3所示，TBtree是一種基于R樹的索引結(jié)構(gòu)。在其葉子節(jié)點(diǎn)中存放對(duì)象的軌跡簇，節(jié)點(diǎn)的結(jié)構(gòu)為（ID號(hào)，軌跡號(hào)，MBB，方向）。由于最小邊界矩形把同一個(gè)軌跡分成了很多字段，同一字段的物體對(duì)象存放在相同的葉子節(jié)點(diǎn)中，為了有效地索引同一個(gè)對(duì)象的軌跡，把同一個(gè)軌跡的節(jié)點(diǎn)用雙向鏈表鏈接起來。這種方法有一個(gè)缺點(diǎn)就是在空間位置相鄰但是不在同一個(gè)軌跡的物體不能存放在同一個(gè)節(jié)點(diǎn)中；這種方法的優(yōu)點(diǎn)是保持了對(duì)象的軌跡特性，對(duì)于查詢同一物體的軌跡非常方便。

在文獻(xiàn)[19]中提出了一種與TBtree相似索引結(jié)構(gòu)，它的最大特點(diǎn)是拋棄了R樹家族一直使用的MBB，即最小邊界矩形。它使用了八邊形的最小邊界方法，這樣做的優(yōu)點(diǎn)是提高查詢的準(zhǔn)確性，八邊形的形狀隨著在其中的對(duì)象位置作適當(dāng)?shù)恼{(diào)整，最大限度地減小包含的面積、減少了重疊，查詢的次數(shù)也就隨之減少。在文獻(xiàn)[19]中還提出了一個(gè)三步的過濾查詢步驟，即過濾(Filtering)、求精（Refinement）、跟蹤（Tracing）。

2．2．2 索引現(xiàn)在將來的軌跡

FTQuadtree(Future Trajectory Quadtree)[1]是最近提出的一種索引結(jié)構(gòu)，它可以索引將來的軌跡。它使用的是Quadtree索引結(jié)構(gòu)，最大的特點(diǎn)是使用了軌跡共享技術(shù)來最大限度地減少數(shù)據(jù)的存儲(chǔ)數(shù)量，提高索引的更新效率。

在這種樹中的葉子節(jié)點(diǎn)結(jié)構(gòu)表示為（oid，軌跡的數(shù)量，起始坐標(biāo)，結(jié)束坐標(biāo)，起始時(shí)間，結(jié)束時(shí)間，其他信息）。對(duì)于在同一時(shí)間內(nèi)的節(jié)點(diǎn)而言，如果它們的坐標(biāo)位置相同或者接近，那么就可以采取共享策略，把若干個(gè)節(jié)點(diǎn)的內(nèi)容放入一個(gè)公共的節(jié)點(diǎn)內(nèi)，這樣就可以明顯地減少存儲(chǔ)的空間。

如圖4所示，左邊是原始的Quadtree，最下面的節(jié)點(diǎn)內(nèi)有五個(gè)相同軌跡段，從X1~X5的軌跡在同一時(shí)間內(nèi)基本相同；右邊的是FTQuadtree，是對(duì)左邊結(jié)構(gòu)的改進(jìn)，采用共享軌跡技術(shù)使節(jié)點(diǎn)數(shù)大大減少。這樣做的優(yōu)點(diǎn)是減

少了存儲(chǔ)的開銷，簡(jiǎn)化了索引的結(jié)構(gòu)，同時(shí)也減少了節(jié)點(diǎn)的更新操作等開銷。

3 坐標(biāo)索引

用坐標(biāo)索引方法索引物體的位置不考慮它們的軌跡，把空間運(yùn)動(dòng)的物體簡(jiǎn)化為點(diǎn)，忽略其空間形狀。在這方面的研究比較早，其中主要有R樹系列和Quadtree系列，由于基于Quadtree的方法比較少，我們主要討論基于Rtree的方法。

3．1 索引過去和現(xiàn)在

RTtree[13]和3D Rtree[15]，3D Rtree，HRtree[20]，HR+tree[3]， MV3Rtree[4]是索引過去對(duì)象位置的索引結(jié)構(gòu)。RTtree是在Rtree的基礎(chǔ)上加入了兩個(gè)時(shí)間項(xiàng)，表示最小邊界矩形的有效時(shí)間。3D Rtree的主要思想是把時(shí)間加入到空間維中，查詢時(shí)不對(duì)時(shí)間和空間進(jìn)行區(qū)分，它的優(yōu)點(diǎn)有兩個(gè)：①索引機(jī)制基于統(tǒng)一的結(jié)構(gòu)，只有一個(gè)空間數(shù)據(jù)結(jié)構(gòu)需要執(zhí)行和維護(hù)；②對(duì)時(shí)空操作的效率較高（如比較耗費(fèi)時(shí)間的空間連接操作）。HRtree[20]的基本結(jié)構(gòu)是建立在Rtree基礎(chǔ)上的，它在每一個(gè)時(shí)間點(diǎn)建立一個(gè)Rtree，過一段時(shí)間如果節(jié)點(diǎn)內(nèi)的對(duì)象位置發(fā)生變化則生成一個(gè)新的節(jié)點(diǎn)，沒有變化則使用原來的節(jié)點(diǎn)，然后在新節(jié)點(diǎn)基礎(chǔ)上建立一個(gè)當(dāng)前時(shí)間Rtree。如果經(jīng)過一段時(shí)間，某個(gè)節(jié)點(diǎn)內(nèi)的物體一直均未移動(dòng)，那么它將被好幾個(gè)Rtree所共享。

3．2 索引現(xiàn)在和未來

TPR（Time Parameterized Rtree）樹[14]是最近提出的一種可以索引物體未來位置的方法。它的葉子節(jié)點(diǎn)形式如下（一維）：（oid，x（tref），vx），其中，oid代表物體的代號(hào)，x是在時(shí)間tref的坐標(biāo)，vx是在時(shí)間tref的速度。它使用公式x(t)=x(tref)+v(t-tref)來計(jì)算物體未來的位置。與Rtree的最小邊界矩形（MBR）相似，TPRtree采用了一個(gè)“保守”邊界矩形（Conservative Bounding Rectangles），它的下限是由矩形所包含的物體最小速度來決定，上限由矩形包含的物體最大速度來決定。由于隨著時(shí)間的推移，邊界矩形會(huì)越來越大，它采取了如下策略：如果其中一個(gè)物體更新，那么這個(gè)物體所在節(jié)點(diǎn)到根的路徑上，所有邊界矩形均要更新。

TPRtree 雖然支持對(duì)未來的查詢，但它是一種非常粗略的預(yù)測(cè)方式，對(duì)運(yùn)動(dòng)規(guī)律相對(duì)固定的物體預(yù)測(cè)有一定的參考價(jià)值，對(duì)于沒有運(yùn)動(dòng)規(guī)律或者運(yùn)動(dòng)規(guī)律經(jīng)常改變的物體的預(yù)測(cè)參考價(jià)值不大。

由于TPRtree使用了動(dòng)態(tài)的VBR（速度邊界矩形），其更新刪除的代價(jià)很大。為了提高其算法效率，在TPRtree基礎(chǔ)上有人提出了TPR*tree[16]，它的基本結(jié)構(gòu)與TPRtree大致相同，僅僅是對(duì)索引算法作了改進(jìn)。

為了克服TPRtree查詢未來太粗糙的缺點(diǎn)，在文獻(xiàn)[18]中提出了一種速度限制索引結(jié)構(gòu)（VCI），它的主要思想是在每個(gè)節(jié)點(diǎn)中加入一個(gè)最大速度項(xiàng)，記錄在節(jié)點(diǎn)中所有對(duì)象的最大速度，如人的最大行走速度、汽車的最大時(shí)速。在這樣一個(gè)約束條件下，一定的時(shí)間內(nèi)就可以計(jì)算出節(jié)點(diǎn)MBR的最大值，從而可以對(duì)查詢的窗口進(jìn)行限制。

4 存在的問題和發(fā)展趨勢(shì)

本文總結(jié)了索引移動(dòng)對(duì)象的各種技術(shù)，并對(duì)它們進(jìn)行了比較詳細(xì)的歸類，對(duì)每種方法均找出了一個(gè)或多個(gè)比較典型的模型進(jìn)行介紹。近幾年這方面的研究是一個(gè)熱點(diǎn)，不同的觀點(diǎn)不斷地被提出來，但是到現(xiàn)在為止由于還幾乎沒有被商用化，現(xiàn)在提出的各種方法大部分還限制于理論階段。

對(duì)于時(shí)空數(shù)據(jù)庫(kù)而言，每種索引結(jié)構(gòu)均有其優(yōu)點(diǎn)和缺點(diǎn)，它們只是對(duì)某種特殊的情況和查詢有比較好的性能。對(duì)于靜態(tài)的空間索引和查詢，Rtree[17]已經(jīng)做到商用化，并且有比較好的性能。但是對(duì)于動(dòng)態(tài)移動(dòng)對(duì)象的索引，我們必須結(jié)合多種索引結(jié)構(gòu)才能實(shí)現(xiàn)相對(duì)比較全面的查詢和索引功能。多種索引結(jié)構(gòu)的結(jié)合是時(shí)空數(shù)據(jù)庫(kù)系統(tǒng)實(shí)際設(shè)計(jì)的主要趨勢(shì)，選擇哪幾種索引結(jié)構(gòu)以及如何把它們有機(jī)地結(jié)合起來將是系統(tǒng)設(shè)計(jì)所面臨的主要難題。

參考文獻(xiàn)：

［1］Rui Ding，Xiaofeng Meng，Yun Bai. Efficient Index Maintenance for Moving Objects with Future Trajectories[C]. Kyoto：The 8th International Conference on Database Systems for Advanced Applications (DASFAA)， 2003.183.

［2］V Prasad Chakka Adam， C Everspaugh Jignesh， M Patel. Indexing Large Trajectory Data Sets with SETI[C]. Asilomar：The 1st Biennial Conference on Innovative Data Systems Research(CIDR)， 2003. 164175.

［3］Y Tao， D Papadias. Efficient Historical Rtrees[C]. Washington， DC：Proceedings of the 13th International Conference on Scientific and Statistical Database Management， 2001.223-232.

［4］Y Tao， D Papadias. MV3Rtree: A SpatioTemporal Access Method for Timestamp and Interval Queries[C]. San Francisco：Proceedings of the 27th International Conference on Very Large Databases， 2001.431-440.

［5］Katerina Raptopoulou， Michael Vassilakopoulos， Yannis Manolopoulos. Towards Quadtreebased Moving Objects Databases[C]. ADBIS，SpringerVerlag GmbH，2004.230-245.

［6］D Pfoser， C S Jensen， Y Theodoridis. Novel Approaches in Query Processing for Moving Object Trajectories[C]. San Francisco：Proc. of the Intl. Conf. on Very Large Data Bases(VLDB)，2000. 395-406.

［7］Dieter Pfoser，Christian S Jensen，Yannis Theodoridis.Novel Approaches to the Indexing of Moving Object Trajectories[C]. Cairo：Proceedings of the 26th International Conference on Very Large Databases， 2000. 395-406.

［8］Z Song， N Roussopoulos. SEBtree:An Approach to Index Continuously Moving Objects[C]. Proc.of the 4th Conference on Mobile Data Management，2003.340-344.

［9］Christian S Jensen， Dan Lin Beng， Chin Ooi. Query and Update Efficient Btree Based Indexing of Moving Objects[C]. Toronto：Proceedings of the 30th VLDB Conference， 2004.

［10］M Cai， P Revesz. Parametric Rtree: An Index Structure for Moving Objects[C]. Proc. of the Intl. Conf. on Management of Data，2000.

［11］Dieter Pfoser， Christian S Jensen. Indexing of Network Constrained Moving Objects[C].New Orleans: Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems，2003.25-32.

［12］Dieter Pfoser， Christian S Jensen.Querying the Trajectories of Online Mobile Objects[C].Santa Barbara:International Workshop on Data Engineering for Wireless and Mobile Access Archive， Proceedings of the 2nd ACM International Workshop on Data Engineering for Wireless and Mobile Access Table of Contents， 2001.66-73.

［13］X Xu， J Han， W Lu. RTtree: An Improved Rtree Indexing Structure for Temporal Spatial Databases[C].Proc. of the Intl. Symp. on Spatial Data Handling，1990.10401049.

［14］S Saltenis， C S Jensen，S T Leutenegger，et al. Indexing the Positions of Continuously Moving Objects[C].Proc. of the ACM Intl. Conf. on Management of Data， SIGMOD， 2000.331-342.

［15］Y Theodoridis， M Vazirgiannis， T Sellis. SpatioTemporal Indexing for Large Multimedia Applications[C]. Proc. of the IEEE Conference on Multimedia Computing and Systems， ICMCS， 1996.441.

［16］Yufei Tao，Dimitris Papadias， Jimeng Sun.The TPR*tree: An Optimized SpatioTemporal Access Method for Predictive Queries[C]. Berlin: Proceedings of the 29th VLDB Conference， 2003. 790-801.

［17］A Guttman. Rtrees:A Dynamic Index Structure for Spatial Searching[C].Proc. of the ACM Intl. Conf. on Management of Data， SIGMOD， 1984.47-57.

［18］Sunil Prabhakar，Yuni Xia，Dmitri V Kalashnikev，et al. Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects[J]. IEEE Transactions on Computers， 2002， 51(10):1124-1140.

［19］Hongjun Zhu， Jianwen Su， Oscar H Ibarra. Trajectory Queries and Octagons in Moving Object Databases[C].McLean:Proceedings of the ACM Conference on Information and Knowledge Management(CIKM)， 2002.413-421.

［20］Mario A， Nascimento， Jefferson R O Silva. Towards Historical Rtrees[C]. Atlanta Proceedings of the ACM Symposium on Applied Computing，1998.235-240.

作者簡(jiǎn)介：

呂俊龍（1977-），男，河北邢臺(tái)人，碩士研究生，主要研究方向?yàn)榭臻g數(shù)據(jù)庫(kù)；劉兆宏（1975-），男，四川人，講師，碩士，主要研究方向?yàn)榭臻g數(shù)據(jù)庫(kù)；李燕（1983-），女，吉林人，學(xué)士，主要研究方向?yàn)榭臻g數(shù)據(jù)庫(kù)；葛君偉（1962-），男，江西人，教授，碩士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)管理；裴海英（1948-），男，韓國(guó)人，教授，博導(dǎo)，主要研究方向?yàn)榈乩硇畔⑾到y(tǒng)、空間數(shù)據(jù)庫(kù)等。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文