R樹索引的查詢研究

王植

（西安航空職業(yè)技術(shù)學(xué)院 陜西 西安 710089）

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

1 軌跡數(shù)據(jù)及不確定范圍查詢模型

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

圖1 時(shí)空棱鏡Fig.1 Space prism

圖1 中左示例即為時(shí)空棱鏡的一種較為普遍的情況，右示例為由多個(gè)時(shí)空棱鏡所組成的生命線項(xiàng)鏈，生命線項(xiàng)鏈?zhǔn)箷r(shí)空棱鏡的研究更加接近于現(xiàn)實(shí)情況，而且在路網(wǎng)空間的研究中也有著很重要的作用。

軌跡數(shù)據(jù)的不確定模型能夠較準(zhǔn)確地確定移動(dòng)對(duì)象的移動(dòng)范圍，而軌跡的不確定范圍查詢指移動(dòng)對(duì)象在某一時(shí)空點(diǎn)發(fā)生重大事件后，以所得有限條件所做的范圍查詢。由于軌跡數(shù)據(jù)條件限制，其查詢結(jié)果具有很大的不確定性，是一個(gè)時(shí)空范圍。時(shí)空棱鏡模型是在軌跡樣本點(diǎn)之間對(duì)移動(dòng)對(duì)象位置的不確定性建模，因此可以在以路口為基本采樣點(diǎn)的路網(wǎng)上延伸時(shí)空棱鏡做不確定范圍查詢。

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

2.1 軌跡模型的構(gòu)造

一個(gè)軌跡樣本盡管已經(jīng)對(duì)原有軌跡進(jìn)行了采樣處理，大大減小了開銷，但是當(dāng)包含大量的軌跡點(diǎn)時(shí)，如果不進(jìn)行分類，也會(huì)使實(shí)驗(yàn)處理增加困難。軌跡樣本作為軌跡數(shù)據(jù)存儲(chǔ)后，軌跡數(shù)據(jù)管理就會(huì)根據(jù)所要進(jìn)行的操作對(duì)軌跡數(shù)據(jù)進(jìn)行處理，如果軌跡數(shù)據(jù)很繁雜，比如有不同移動(dòng)對(duì)象的軌跡數(shù)據(jù)，不同時(shí)間段的軌跡數(shù)據(jù)，如果再以遍歷方式查詢的話，將會(huì)大大增加系統(tǒng)開銷，因此，提出標(biāo)簽這一概念，在原有軌跡模型上加入標(biāo)簽，這樣不僅可以直接區(qū)分不同的軌跡樣本，而且在進(jìn)行查詢的時(shí)候，也可以大大減小開銷。

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

定義2（路口區(qū)域）軌跡的樣本點(diǎn)為路口時(shí)，路口區(qū)域可表示為：

其中id表示路口編號(hào)，t表示經(jīng)過此路口區(qū)域的時(shí)間，x表示此路口的橫坐標(biāo)，y表示此路口的豎坐標(biāo)，v表示通過此路口的速度。 那么軌跡樣本關(guān)系可以表示為（ai， idi，j， ti，j，xi，j， yi，j， vi，j），在進(jìn)行不確定范圍查詢時(shí)，可以根據(jù)軌跡樣本關(guān)系得出其所經(jīng)路口順序。

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

圖2 路口模型Fig.2 Crossing model

在此基礎(chǔ)上讀取所給文件中的相應(yīng)信息。一般文件信息中包括路口的很多信息，但本文主要存儲(chǔ)路口對(duì)于查詢比較重要的信息，主要包括路口的id以及路口的橫坐標(biāo)以及豎坐標(biāo)。根據(jù)路口的id以及路段文件，可疑判斷出哪些路口之間有路段，哪些路口之間是不可達(dá)的，對(duì)于可達(dá)的兩個(gè)路口根據(jù)其橫豎坐標(biāo)可以計(jì)算出其長(zhǎng)度，為計(jì)算最短距離做準(zhǔn)備。

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

定義3（路段區(qū)域）路段區(qū)域定義為如下形式：

其中id表示路段的編號(hào)，node1、node2表示路段所連接的2個(gè)路口，length表示路段的長(zhǎng)度，v表示經(jīng)過此路段時(shí)的速度。

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

圖3 路段模型Fig.3 Section model

圖3 給出了路段的簡(jiǎn)化模型，包括路段編號(hào)、路段連接的路口、路口坐標(biāo)、速度等。根據(jù)這些信息，可以計(jì)算出在后續(xù)查詢中所要使用的信息，包括路段長(zhǎng)度、路段平均時(shí)間等。

在所給數(shù)據(jù)集中，每個(gè)路段的這些信息應(yīng)該被提取出來，為其建立R樹索引[5]，并建立相應(yīng)的數(shù)組存儲(chǔ)一些信息。數(shù)據(jù)集中根據(jù)所給路段模型可完成對(duì)信息的提取。路段長(zhǎng)度可由路段所連接的兩個(gè)路口的位置并根據(jù)距離公式計(jì)算得出。在軌跡模型建立完成之后，即可為軌跡數(shù)據(jù)建立索引。建立索引完成后，即可根據(jù)本文設(shè)計(jì)的查詢算法完成相關(guān)的查詢內(nèi)容。

2.2 軌跡數(shù)據(jù)的索引

在諸多索引結(jié)構(gòu)中，R樹索引是近年來采用最為普遍的一種，適用于建立路網(wǎng)空間的索引。本文的研究即采用R樹索引，并將基于R樹做進(jìn)一步的改進(jìn)。

在R樹葉子結(jié)點(diǎn)中，選擇一個(gè)合適的葉子結(jié)點(diǎn)并將路段的不確定矩形框插入之。對(duì)于R樹合適的評(píng)價(jià)標(biāo)準(zhǔn)是插入下一個(gè)路段的不確定矩形框后，MBR面積增加最少。如果這個(gè)葉子結(jié)點(diǎn)還能容納不確定矩形框，則直接插入；否則，將該葉子結(jié)點(diǎn)分裂成兩個(gè)葉子結(jié)點(diǎn)，且這兩個(gè)葉子結(jié)點(diǎn)包含要輸入的矩形框和原來含有的矩形框。分裂時(shí)，使得這兩個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的矩形區(qū)域之和最小。分裂之后，從葉子結(jié)點(diǎn)向根結(jié)點(diǎn)進(jìn)行調(diào)整。如此直至將路段的矩形框都插入到R樹中。路段的R樹結(jié)構(gòu)如圖4所示。

圖4 路段的R樹結(jié)構(gòu)Fig.4 Section of the R tree structure

對(duì)路網(wǎng)空間路段的不確定矩形框建立一棵R樹，并通過對(duì)其搜索區(qū)域的范圍查詢來實(shí)現(xiàn)對(duì)路段的查找。通過路段的不確定矩形框建立R樹[6]，可以在很大程度上提高查詢速度。

在軌跡生成的大量信息中，根據(jù)建立的軌跡模型，應(yīng)該篩選軌跡信息。其中路口的信息主要包括路網(wǎng)路口的編號(hào)以及橫豎坐標(biāo)。其基本算法思想為讀取相應(yīng)時(shí)空數(shù)據(jù)文件中的有效信息并存儲(chǔ)，在進(jìn)一步的運(yùn)算中，可以根據(jù)路口編號(hào)得到其橫豎坐標(biāo)以及速度信息等。在計(jì)算路段的距離時(shí)，可以建立動(dòng)態(tài)二維數(shù)組，根據(jù)所連接的兩路口計(jì)算并存儲(chǔ)路段的長(zhǎng)度。同時(shí)可以存儲(chǔ)路段的平均速度等信息，本文主要采用數(shù)組完成。

2.3 MBR的改進(jìn)

前面提到了MBR的改進(jìn)，所要查詢的路段其范圍比原MBR增加的長(zhǎng)度為最大可能移動(dòng)距離。如圖5所示。

圖5 MBR的改進(jìn)Fig.5 Improvement of MBR

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

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

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

根據(jù)所要查詢的路網(wǎng)中路段的最大速度以及時(shí)間間隔計(jì)算出最大可能移動(dòng)距離l；

根據(jù)l建立不確定范圍路段的MBR。

而在具體實(shí)現(xiàn)建立不確定范圍所在路段的MBR時(shí)，需根據(jù)兩路口的坐標(biāo)大小以及最大可能移動(dòng)距離確定插入的MBR位置。

2.4 查詢算法的改進(jìn)與實(shí)現(xiàn)

路網(wǎng)空間不確定范圍查詢的總體處理流程包括基于路口的查詢流程以及基于可移動(dòng)對(duì)象的查詢流程，在對(duì)這兩種查詢流程的簡(jiǎn)單評(píng)估后，選擇基于路口的查詢流程繼續(xù)深入研究。

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

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

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

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

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

3 實(shí)驗(yàn)評(píng)估

本文主要驗(yàn)證軌跡數(shù)據(jù)管理不確定范圍查詢處理中的查詢效率和查詢準(zhǔn)確率。實(shí)驗(yàn)結(jié)果的分析主要根據(jù)CPU計(jì)算時(shí)間以及返回的結(jié)果集。實(shí)驗(yàn)硬件環(huán)境是：處理器為Core Intel（R）CPU i3-2310M@2.10 GHz 2.10 GHz， 內(nèi)存為 2GB RAM。實(shí)驗(yàn)的軟件環(huán)境：Windows 7操作系統(tǒng)和Visual Studio 2008集成開發(fā)環(huán)境。

實(shí)驗(yàn)數(shù)據(jù)由生成路網(wǎng)空間交通信息的generator模擬傳感器而生成的數(shù)據(jù)，包括路口信息以及路段信息。其中路口信息包括路口坐標(biāo)、路口id以及路口監(jiān)測(cè)速度v。路段信息主要包括路段所連接的路口以及路段id。

實(shí)驗(yàn)過程中，針對(duì)使用改進(jìn)后的MBR以及未改進(jìn)的MBR進(jìn)行對(duì)比并分析結(jié)果。

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

圖7 查詢效率的對(duì)比Fig.7 Query efficiency comparison

圖中橫坐標(biāo)為路口數(shù)據(jù)集大小，縱坐標(biāo)為時(shí)間，單位為秒。數(shù)據(jù)集為generator生成的路網(wǎng)空間數(shù)據(jù)，時(shí)間為建立R樹索引以及輸入查詢路口到查詢結(jié)束的時(shí)間。數(shù)據(jù)分為40、80、120、160個(gè)路口4種情況，查詢時(shí)間為10次查詢時(shí)間的平均值。

在此基礎(chǔ)上，對(duì)比兩種查詢的準(zhǔn)確率，數(shù)據(jù)為在路網(wǎng)約束的條件在所設(shè)計(jì)的空間移動(dòng)對(duì)象。

圖8 查準(zhǔn)率的對(duì)比Fig.8 Precision comparison

圖中橫坐標(biāo)為路口數(shù)據(jù)集大小，縱坐標(biāo)為查詢準(zhǔn)確率百分比。查準(zhǔn)率的計(jì)算方式為根據(jù)路網(wǎng)中在某一時(shí)刻經(jīng)過某路段的移動(dòng)對(duì)象經(jīng)過一段時(shí)間所在的位置確實(shí)在查詢結(jié)果范圍中的比例得出，路口數(shù)據(jù)與查詢效率中的數(shù)據(jù)一致，并預(yù)設(shè)車輛在3個(gè)查詢路段，最后計(jì)算3個(gè)路段準(zhǔn)確率的平均值得出。

根據(jù)實(shí)驗(yàn)結(jié)果分析可以得知，在基于R樹索引的一般查詢，當(dāng)數(shù)據(jù)較大時(shí)，其查詢時(shí)間會(huì)大幅增長(zhǎng)。而使用改進(jìn)MBR的查詢，不僅在查詢時(shí)間上大幅降低，而且在查詢準(zhǔn)確率上較原有情況也略有提高。

4 結(jié)束語

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

在建立軌跡模型的過程中，改進(jìn)了軌跡模型，加入了其他的軌跡信息，方便查詢實(shí)現(xiàn)。在查詢階段，使用了改進(jìn)的MBR，并分為兩步查詢，減少了查詢對(duì)象并減少了系統(tǒng)開銷。

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

[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].現(xiàn)代電子技術(shù)，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]肖金城，王恩泉，胡特彧.三維地理信息應(yīng)急指揮系統(tǒng)設(shè)計(jì)[J].測(cè)繪科學(xué)，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.