R樹索引的查詢研究

王植

（西安航空職業技術學院 陜西 西安 710089）

如今軌跡數據管理[1]在現實中的應用十分廣泛，在軍事、經濟、金融、交通、公安等都有著廣泛的應用，軌跡數據管理的作用顯得越來越突出。在上世紀末以及本世紀初的短短幾十年里，全球定位技術和無線通信技術迅速發展，這使管理移動對象軌跡信息成為可能，同時也使得移動對象軌跡的其他研究諸如查詢和管理得到人們廣泛而深入的研究。一些傳統的軌跡數據管理仍僅致力于有效處理非時空屬性的移動對象，但移動對象的移動是不間斷動態的，即移動對象[2]的位置是隨著時間的變化而連續變化的，那么在變化過程中更新數據庫時就與非時空屬性的情況不一樣。因此，在移動對象軌跡數據管理中，軌跡模型[3]的建立以及移動對象的信息更新都需要重新考慮。而軌跡數據管理的查詢是軌跡數據管理的重要部分，它的設計對整個軌跡數據管理有著至關重要的作用。近幾年又出現了時空棱鏡的相關研究，這對于時空移動對象的不確定范圍查詢有著重大的意義。

1 軌跡數據及不確定范圍查詢模型

在不確定范圍查詢中，從數據方面分類，主要包括不確定數據查詢和確定數據查詢以及連續軌跡數據查詢和離散軌跡數據查詢，本文在路網空間軌跡數據較為精準且采樣頻率較低的前提下，主要研究確定的離散軌跡數據。由于采用離散軌跡數據，因此軌跡在離散點之間存在很大的不確定性，而軌跡數據的不確定模型對于查詢算法的設計有著很大的影響。早期諸多研究采用的是氣瓶來表示兩點間的不確定時空空間，但這種方法增加了很多開銷。在近幾年的研究中開始采取時空棱鏡來表示不確定時空空間，它更加精確、更加接近于現實情況，從而大大減小了算法的開銷。一個時空棱鏡[4]指一個向上的指向錐和一個向下的指向錐的交叉時空空間，它能夠表示在兩個連續時空點間的運動物體的所有可能的軌跡，確定可達的時空空間，如圖1所示。

圖1 時空棱鏡Fig.1 Space prism

圖1 中左示例即為時空棱鏡的一種較為普遍的情況，右示例為由多個時空棱鏡所組成的生命線項鏈，生命線項鏈使時空棱鏡的研究更加接近于現實情況，而且在路網空間的研究中也有著很重要的作用。

軌跡數據的不確定模型能夠較準確地確定移動對象的移動范圍，而軌跡的不確定范圍查詢指移動對象在某一時空點發生重大事件后，以所得有限條件所做的范圍查詢。由于軌跡數據條件限制，其查詢結果具有很大的不確定性，是一個時空范圍。時空棱鏡模型是在軌跡樣本點之間對移動對象位置的不確定性建模，因此可以在以路口為基本采樣點的路網上延伸時空棱鏡做不確定范圍查詢。

2 軌跡數據管理中不確定范圍查詢算法的思想

2.1 軌跡模型的構造

一個軌跡樣本盡管已經對原有軌跡進行了采樣處理，大大減小了開銷，但是當包含大量的軌跡點時，如果不進行分類，也會使實驗處理增加困難。軌跡樣本作為軌跡數據存儲后，軌跡數據管理就會根據所要進行的操作對軌跡數據進行處理，如果軌跡數據很繁雜，比如有不同移動對象的軌跡數據，不同時間段的軌跡數據，如果再以遍歷方式查詢的話，將會大大增加系統開銷，因此，提出標簽這一概念，在原有軌跡模型上加入標簽，這樣不僅可以直接區分不同的軌跡樣本，而且在進行查詢的時候，也可以大大減小開銷。

定義1（軌跡樣本關系）如果該軌跡是一段連續完整的軌跡，則Ti可以用分段函數等方式表示。如果這段軌跡并非一段連續完整的軌跡，則關系R稱之為軌跡樣本關系，且R是一個有限元組。

定義2（路口區域）軌跡的樣本點為路口時，路口區域可表示為：

其中id表示路口編號，t表示經過此路口區域的時間，x表示此路口的橫坐標，y表示此路口的豎坐標，v表示通過此路口的速度。 那么軌跡樣本關系可以表示為（ai， idi，j， ti，j，xi，j， yi，j， vi，j），在進行不確定范圍查詢時，可以根據軌跡樣本關系得出其所經路口順序。

為實現本文中的查詢算法，使用軌跡生成器生成了某一城市中的具體軌跡信息，包括各路段以及各路口的坐標信息等。在存儲路口信息的時候則是首先讀取其橫豎坐標并存儲，建立的路口模型如圖2所示。

圖2 路口模型Fig.2 Crossing model

在此基礎上讀取所給文件中的相應信息。一般文件信息中包括路口的很多信息，但本文主要存儲路口對于查詢比較重要的信息，主要包括路口的id以及路口的橫坐標以及豎坐標。根據路口的id以及路段文件，可疑判斷出哪些路口之間有路段，哪些路口之間是不可達的，對于可達的兩個路口根據其橫豎坐標可以計算出其長度，為計算最短距離做準備。

由于本文主要側重于研究不確定范圍的查詢，因此對于路網上的路段不作深入研究，本文假設路網的路段皆為直線段，并在兩個路口之間。路段可以包括很多信息，路段上移動車輛的平均速度，以及連接的路口，路段長度等。

定義3（路段區域）路段區域定義為如下形式：

其中id表示路段的編號，node1、node2表示路段所連接的2個路口，length表示路段的長度，v表示經過此路段時的速度。

本算法的路段模型如圖3所示。

圖3 路段模型Fig.3 Section model

圖3 給出了路段的簡化模型，包括路段編號、路段連接的路口、路口坐標、速度等。根據這些信息，可以計算出在后續查詢中所要使用的信息，包括路段長度、路段平均時間等。

在所給數據集中，每個路段的這些信息應該被提取出來，為其建立R樹索引[5]，并建立相應的數組存儲一些信息。數據集中根據所給路段模型可完成對信息的提取。路段長度可由路段所連接的兩個路口的位置并根據距離公式計算得出。在軌跡模型建立完成之后，即可為軌跡數據建立索引。建立索引完成后，即可根據本文設計的查詢算法完成相關的查詢內容。

2.2 軌跡數據的索引

在諸多索引結構中，R樹索引是近年來采用最為普遍的一種，適用于建立路網空間的索引。本文的研究即采用R樹索引，并將基于R樹做進一步的改進。

在R樹葉子結點中，選擇一個合適的葉子結點并將路段的不確定矩形框插入之。對于R樹合適的評價標準是插入下一個路段的不確定矩形框后，MBR面積增加最少。如果這個葉子結點還能容納不確定矩形框，則直接插入；否則，將該葉子結點分裂成兩個葉子結點，且這兩個葉子結點包含要輸入的矩形框和原來含有的矩形框。分裂時，使得這兩個葉子結點對應的矩形區域之和最小。分裂之后，從葉子結點向根結點進行調整。如此直至將路段的矩形框都插入到R樹中。路段的R樹結構如圖4所示。

圖4 路段的R樹結構Fig.4 Section of the R tree structure

對路網空間路段的不確定矩形框建立一棵R樹，并通過對其搜索區域的范圍查詢來實現對路段的查找。通過路段的不確定矩形框建立R樹[6]，可以在很大程度上提高查詢速度。

在軌跡生成的大量信息中，根據建立的軌跡模型，應該篩選軌跡信息。其中路口的信息主要包括路網路口的編號以及橫豎坐標。其基本算法思想為讀取相應時空數據文件中的有效信息并存儲，在進一步的運算中，可以根據路口編號得到其橫豎坐標以及速度信息等。在計算路段的距離時，可以建立動態二維數組，根據所連接的兩路口計算并存儲路段的長度。同時可以存儲路段的平均速度等信息，本文主要采用數組完成。

2.3 MBR的改進

前面提到了MBR的改進，所要查詢的路段其范圍比原MBR增加的長度為最大可能移動距離。如圖5所示。

圖5 MBR的改進Fig.5 Improvement of MBR

圖中有 A、B、C、D、E、F 6個路口， 路口之間存在連線表示兩路口之間存在路口，是可達的。如圖所示，6個路口之間共存在 6 個路段：AD、BD、BC、CE、DE、EF， 以路段為單位建立R樹索引并建立MBR，如圖所示，以各路段的路口為斷點并平行于坐標軸建立MBR，如果所要做的查詢不確定范圍在BD路段，則根據速度以及時間間隔計算出的最大可能移動距離為BD路段建立改進后的MBR，如圖5所示。為軌跡數據建立MBR的算法思想基本如下：

由軌跡數據集計算出各路口以及路段的信息，并根據已知軌跡信息建立路段模型；

建立路段的R樹索引，建立各路段的MBR[7]；

根據所要查詢的路網中路段的最大速度以及時間間隔計算出最大可能移動距離l；

根據l建立不確定范圍路段的MBR。

而在具體實現建立不確定范圍所在路段的MBR時，需根據兩路口的坐標大小以及最大可能移動距離確定插入的MBR位置。

2.4 查詢算法的改進與實現

路網空間不確定范圍查詢的總體處理流程包括基于路口的查詢流程以及基于可移動對象的查詢流程，在對這兩種查詢流程的簡單評估后，選擇基于路口的查詢流程繼續深入研究。

根據前文所示，流程如圖6所示。根據流程圖所示，在得到路網空間傳感器的數據集后，建立各路口以及各路段的R樹索引，建立索引完成后，根據所要查詢的不確定范圍所在的路口或者路段的最大移動速度以及查詢時刻與犯罪時刻的時間間隔計以及時空棱鏡的相關知識計算出最大可能移動距離，以改進的MBR建立該路段的R樹索引。

圖6 基于路口以及改進MBR的一般查詢流程Fig.6 Based on the intersection and improved MBR general query process

與不確定范圍查詢對象所在路段的MBR重疊的路口或者路段列入可疑結果集，并作進一步的判斷，若可疑路口與不確定范圍所在路段連接的路口的最短距離小于最大可能移動距離，則該路口為可疑路口。最后根據速度、時間進行線性插值，得到移動對象的位置范圍。

按照上述流程，路網空間中基于路口的不確定范圍查詢基本完成。需要注意的是，在進行查詢一次后，如果需要重新進行查詢，則需要將原R樹索引中查詢路段的改進MBR刪除，并建立新查詢路段的改進MBR。

根據上述流程，可以得出不確定范圍查詢的算法。算法首先根據所得結果集得出路口以及路段集，并建立R樹索引，在此基礎上對所要查詢的路段E1的MBR做了修改，為其建立改進的MBR，并根據所查詢路段MBR與其他路段MBR的重疊情況初步得到路口結果集，縮小了路口node的查詢范圍。在所得node集上作進一步判斷，計算與E1所在路口node1的最短距離S1，并將S1與最大可能移動距離l相比，根據比較結果，如果S1小于1，則該路口為可疑路口，加入到結果集中。最后根據速度以及所在路段、路口、時間，利用線性插值法，計算最大可能移動范圍的坐標。

3 實驗評估

本文主要驗證軌跡數據管理不確定范圍查詢處理中的查詢效率和查詢準確率。實驗結果的分析主要根據CPU計算時間以及返回的結果集。實驗硬件環境是：處理器為Core Intel（R）CPU i3-2310M@2.10 GHz 2.10 GHz， 內存為 2GB RAM。實驗的軟件環境：Windows 7操作系統和Visual Studio 2008集成開發環境。

實驗數據由生成路網空間交通信息的generator模擬傳感器而生成的數據，包括路口信息以及路段信息。其中路口信息包括路口坐標、路口id以及路口監測速度v。路段信息主要包括路段所連接的路口以及路段id。

實驗過程中，針對使用改進后的MBR以及未改進的MBR進行對比并分析結果。

首先對比基于R樹索引的一般查詢以及基于改進MBR的查詢，在不同大小的數據集的情況下的查詢效率。

圖7 查詢效率的對比Fig.7 Query efficiency comparison

圖中橫坐標為路口數據集大小，縱坐標為時間，單位為秒。數據集為generator生成的路網空間數據，時間為建立R樹索引以及輸入查詢路口到查詢結束的時間。數據分為40、80、120、160個路口4種情況，查詢時間為10次查詢時間的平均值。

在此基礎上，對比兩種查詢的準確率，數據為在路網約束的條件在所設計的空間移動對象。

圖8 查準率的對比Fig.8 Precision comparison

圖中橫坐標為路口數據集大小，縱坐標為查詢準確率百分比。查準率的計算方式為根據路網中在某一時刻經過某路段的移動對象經過一段時間所在的位置確實在查詢結果范圍中的比例得出，路口數據與查詢效率中的數據一致，并預設車輛在3個查詢路段，最后計算3個路段準確率的平均值得出。

根據實驗結果分析可以得知，在基于R樹索引的一般查詢，當數據較大時，其查詢時間會大幅增長。而使用改進MBR的查詢，不僅在查詢時間上大幅降低，而且在查詢準確率上較原有情況也略有提高。

4 結束語

文中側重于軌跡數據管理中的查詢算法的分析與實現，并詳細研究了不確定范圍的查詢實現。主要分為以下四部分：軌跡數據的讀取與計算、R樹索引的建立、MBR的改進、基于時空棱鏡的二步查詢。

在建立軌跡模型的過程中，改進了軌跡模型，加入了其他的軌跡信息，方便查詢實現。在查詢階段，使用了改進的MBR，并分為兩步查詢，減少了查詢對象并減少了系統開銷。

由于考慮到設備條件限制，研究重要側重于路口以及路段的平均情況，在以后的工作中，可以在本文基礎上對移動對象進行查詢，并且對移動車輛建立TPR*樹索引，這樣可以大大提高查準率。

[1]Goce Trajcevski，Alok Choudhary，Ouri Wolfson，et al.Uncertain range queries for necklaces[J].In Mobile Data Management（MDM），2010：199-208．

[2]Kuijpers B.Dealing with Uncertainty in Trajectory Databases[C]//In 2010 17th International Symposium on Temporal Representation and Reasoning，2010：7-8.

[3]Kuijpers B，Moelans B，Othman W，et al.Analyzing trajectories using uncertainty and background information[J].In Lecture Notes in Computer Science，2009:135-152.

[4]Kuijpers B，Othman W.Trajectory databases:Data models，uncertainty and complete query languages[J].In Journal of Computer and System Sciences，2010，76（7）：538-560.

[5]ZHANG Wen-jie.Indexing and Querying Techniques for the Past，the Present and the Future Information of Moving Objects[M].In Master theses of Harbin Institute of Technology，2006.

[6]劉文閎，熊偉，吳燁，等.空間索引并行批量加載算法研究[J].現代電子技術，2011，34（22）：90-94.LIU Wen-hong，XIONG Wei，WU Ye，et al.Research on parallel bulk-loading algorithm for spatial index[J].Modern Electronics Technique，2011，34（22）：90-94.

[7]肖金城，王恩泉，胡特彧.三維地理信息應急指揮系統設計[J].測繪科學，2011（2）：181-183.XIAO Jin-cheng，WANG En-quan，HU Te-yu.Design of 3D geographic information emergency commanding system[J].Science of Surveying and Mapping，2011（2）：181-183.