易顯天，徐 展，郭承軍，劉 丹，張 可

（電子科技大學電子科學技術(shù)研究院，成都611731）

1 概述

移動對象數(shù)據(jù)庫是近年發(fā)展起來的數(shù)據(jù)庫研究分支，也是基于位置相關(guān)服務一項重要的技術(shù)，目前國內(nèi)外有大量的空間索引技術(shù)涌現(xiàn)，但總體來說該領(lǐng)域的研究與發(fā)展仍然處于未成熟階段［1－2］。

目前移動對象索引研究可以大概分為2類：（1）基于空間劃分的索引結(jié)構(gòu)［3－4］，如 B＋樹和網(wǎng)格。（2）基于數(shù)據(jù)的劃分的索引結(jié)構(gòu)［5－7］，如 R－Tree和其相關(guān)的演化結(jié)構(gòu)。基于空間劃分的索引結(jié)構(gòu)中有一類是一維索引結(jié)構(gòu)，相較于二維索引，一維索引發(fā)展得更為成熟，適用范圍更廣，對空間數(shù)據(jù)進行降維處理，可以重復利用一維索引技術(shù)及其相關(guān)技術(shù)。常見的降維方法是利用空間填充曲線，將二維空間的信息映射到一維空間上［8－10］。

目前的索引結(jié)構(gòu)大都不能提供高效的近鄰查詢，或者需要復雜結(jié)構(gòu)和算法，以至于結(jié)構(gòu)實現(xiàn)困難。本文提出一種基于Patricia樹的索引結(jié)構(gòu)MPT（Morton Patricia Tree），融 合 Morton 碼、Patricia樹結(jié)構(gòu)和算法，使得MPT擁有高效響應的近鄰查詢能力，且 Morton碼比Geohash［11］編碼對二維空間劃分有更好的精度控制。同時提出基于MPT的近鄰算法。通過對二維空間的進行預訂規(guī)則下不同粒度劃分，把分塊后的二維空間區(qū)域轉(zhuǎn)換為一維編碼，使得MPT具備快速響應范圍查詢能力。

2 Patricia樹和二維空間編碼方案

2．1 Patricia樹

Patricia樹是一種一維樹形索引結(jié)構(gòu)，可以用來存儲字符串。結(jié)構(gòu)中只有葉子結(jié)點保存字符串信息，中間結(jié)點代表其子孫結(jié)點中的字符串的某公共前綴，但并不存儲字符串而是保存的不同字符串之間的區(qū)分信息。索引結(jié)構(gòu)中父親結(jié)點的代表的字符串是其子結(jié)點代表字符串的前綴，兄弟結(jié)點所代表的字符串具有公共前綴，Patricia可以使用基于二進制位的方式構(gòu)建，適用于以Morton碼為觀察對象的查詢操作。

2．2 編碼原理

二進制Morton編碼的基本思想是不斷交替在經(jīng)緯度2個方向?qū)Φ厍虮砻孢M行二分。一直循環(huán)劃分到任意精度。具體為：當沿著經(jīng)度方向進行二分時，左側(cè)區(qū)域編碼為0，右側(cè)區(qū)域的編碼為1；當沿緯度方向進行二分時，下側(cè)區(qū)域編碼為0，上側(cè)區(qū)域編碼為1。

經(jīng)緯度在數(shù)次二分之后，把指定位置對應的二進制數(shù)從范圍由大到小按序排列，可得到對應位置經(jīng)緯度的編碼，例如緯度產(chǎn)生編碼：1011100011，經(jīng)度產(chǎn)生編碼，1101001011。將經(jīng)度代表的編碼放在偶數(shù)位，將緯度代表的編碼放在奇數(shù)位，重新組合經(jīng)緯度的編碼可得到新的編碼：111001110100100011 11。這也就是最終使用到的Morton編碼。

而Geohash編碼則需要繼續(xù)對上述編碼過程中得到的二進制碼進行Base32編碼轉(zhuǎn)換。5位二進制碼產(chǎn)生一位Geohash編碼。當GeoHash字符串長度為奇數(shù)時，此碼值代表一個長寬不相等的矩形。另外，由于Geohash一個字符代表5bit，這意味著位置精度的控制是以每5bit增減，存在著較大精度的浪費。使用二進制Morton碼，可獲得更細粒度的精度。Geohash和Morton編碼精度對比如圖1所示，從圖中可以看出，Morton編碼可以達到的面積劃分粒度要比Geohash細，其中，pow（2，x）表示2的x次方，精度可以達到A／Pow（2，x）（A為全部面積）。

圖1 Morton碼與Geohash碼精度對比

2．3 編碼特點

通過Morton編碼方案可知其編碼具有以下特點：

（1）唯一性，根據(jù)編碼過程中區(qū)域劃分規(guī)則，地球表面在劃分過程中的每個單元格都有唯一的編碼與其對應。

（2）每一個編碼并不是表示一個二維點坐標，而是表示一個二維矩形區(qū)域。區(qū)域的大小由編碼長度控制。故編碼的前綴可以表示更大范圍。

（3）每個編碼同時表示經(jīng)度和緯度2個坐標。

3 MPT索引結(jié)構(gòu)

3．1 MPT索引

使用Morton碼將二維位置信息轉(zhuǎn)化為一維編碼，以2個編碼相同前綴的長短來表示2個二維位置的近遠，Morton碼不僅保留了移動對象二維位置的鄰近關(guān)系，另一方面也能很好地反映不同大小的二維空間區(qū)域之間的從屬關(guān)系。Patricia樹父子結(jié)點分別代表的字符串具有前綴對應關(guān)系，這也恰好適于Morton碼前綴匹配操作?；谏鲜隹紤]，將移動對象二維位置信息轉(zhuǎn)換為二進制Morton碼并通過MPT插入算法構(gòu)建索引結(jié)構(gòu)。并改良索引結(jié)構(gòu)和相關(guān)算法使MPT具有高效響應空間查詢的能力。

3．2 Bitwise操作

MPT的整個結(jié)構(gòu)是以二進制的位操作為原理構(gòu)建的，這樣同時也能節(jié)省空間和加快操作效率。因為在計算機中對位的操作更快，所以樹將字符串進行“二進制”化再插入到索引結(jié)構(gòu)中。

MPT子結(jié)點保存的是插入MPT的二進制Morton碼串，非葉子結(jié)點保存的是Morton碼串前綴對應的“狀態(tài)”，這些狀態(tài)是Morton碼串在插入過程中根據(jù)不同Morton碼串基于位的比較而得到的，只有2個碼串出現(xiàn)二進制位的不同時，才會出現(xiàn)一個新的結(jié)點，來保存這個“分歧”狀態(tài)，而那2個碼串也因為這個“分歧”的二進制位的0或1而由這個結(jié)點的2個不同的子結(jié)點方向各自向下繼續(xù)比較。也就是說對整個樹的操作也就類似于對二叉樹的操作。在索引結(jié)構(gòu)中的搜索路徑的選擇是根據(jù)對應位的0或1來決定的。分析同樣具有前綴搜索能力的trie樹的結(jié)構(gòu)，可以發(fā)現(xiàn)trie樹結(jié)點保留字符串中相同的字符，每條檢索路徑都是字符串的前綴。如果改變結(jié)點本身強調(diào)的內(nèi)容，將字符串之間的不同點的信息保留在分支結(jié)構(gòu)中，那么就可以把所有相同的字串匹配省略，減少了所需存儲信息的數(shù)量。

3．3 MPT結(jié)點結(jié)構(gòu)

在實驗過程中發(fā)現(xiàn)，結(jié)點的容量有些許的增加，就會帶來整個索引結(jié)構(gòu)體積的大量增加，故在保證索引結(jié)構(gòu)操作效率的情況下，使結(jié)點中保存的信息盡量少，以減少空間占用。MPT索引結(jié)構(gòu)如圖2所示。

圖2 MPT索引結(jié)構(gòu)

非葉子結(jié)點結(jié)構(gòu)為（Ptr［2］，pos，mask），其中，Ptr是指向子結(jié)點的指針，每個結(jié)點固定包含2個指針；Pos是結(jié)點對應字符在整個字符串中的位置；mask是一個用于位操作的8位二進制碼，用來獲取比較的字符的最高不同位。葉子結(jié)點的結(jié)構(gòu)為（Ptr，MojInfo），其中，Ptr是指向 Morton碼串的指針；MojInfo是一個結(jié)構(gòu)體數(shù)組。每個數(shù)據(jù)項結(jié)構(gòu)為（ID，x，y），其中，ID 為移動對象的標識號；x，y為移動對象的二維位置。為了節(jié)省空間，本文使用指針變量的最低有效位來表示這個指針是指向內(nèi)部結(jié)點還是指向葉子結(jié)點。大致結(jié)構(gòu)如圖2所示。為了示意，畫出了一個“滿”MPT，但是實際如果沒有出現(xiàn)對應的字符串對比。則不會出現(xiàn)因“分歧”而產(chǎn)生的對應的結(jié)點。

3．4 查詢算法

MPT查詢操作先將需要查找的字符串進行“二進制”化，然后根據(jù)搜索過程中遇到結(jié)點的順序?qū)ο嚓P(guān)的二進制位進行比較，即在MPT樹中進行二分查找，直到查找到對應字符串并進行移動對象信息對比，相同則返回True，不同或查找失敗則返回False。偽代碼如下：

輸入 MPT結(jié)構(gòu)指針T，指向字符串指針u，移動對象ID，移動對象二維位置信息x，y

輸出 True／False

3．5 算法插入

整個MPT構(gòu)建過程主要依賴插入算法，由于結(jié)構(gòu)特點，對于同樣的Morton碼集的輸入，對應產(chǎn)生MPT也是完全相同的，因此MPT在操作過程中不需要實現(xiàn)復雜的平衡算法。并且整個MPT結(jié)構(gòu)的高度由輸入的字符串的最大長度來決定，而不是由輸入字符串的數(shù)目來決定。插入操作先處理時空樹的情況，然后使用類似于上面描述的搜索方法來查到到合適的插入位置，計算相關(guān)的pos和mask參數(shù)，然后生成對應新的結(jié)點，最終將結(jié)點插入。具體算法的偽代碼如下：

輸入 MPT結(jié)構(gòu)指針T，指向字符串指針u，移動對象ID，移動對象二維位置信息x，y

輸出 True／False

4 高級查詢

4．1 近鄰查詢

根據(jù)Morton編碼特點可以知道如果2個點的距離越近，那么2個點位置對應的編碼的共同前綴則越長，這樣可以通過前綴的比較來進行二維空間的近鄰搜索，為了消除在搜索過程中的遺漏，除了使用定位的編碼匹配外，還使用周圍8個區(qū)域的編碼進行搜索匹配。在近鄰搜索算法中每一次循環(huán)都在前一次搜索范圍外增加一層以目前Morton碼長所表示的范圍的搜索區(qū)域。這樣可以有效利用上一步的搜索結(jié)果。偽代碼如下：

輸入 緯度lat，經(jīng)度lon，MPT 結(jié)構(gòu)指針MPptr，近鄰搜索目標數(shù)num，編碼匹配范圍extent

輸出 num個近鄰對象的ID：result

4．2 區(qū)域查詢

對查詢區(qū)域進行如圖3所示的劃分，可將查詢區(qū)域分解成多個查詢方塊，為了能夠更好地覆蓋整個查詢區(qū)域，需要對查詢區(qū)域劃分為大小不同的方塊。實驗過程中發(fā)現(xiàn)，將查詢區(qū)域劃分的方塊越小，則對查詢區(qū)域有更精確的覆蓋，查詢精度更高，但是在劃分粒度超過一定范圍以后，得到精度上的提升較小，反而由于劃分粒度過小，得到的查詢方塊數(shù)量急劇增多，使得查詢性能大大下降，于是選擇恰當?shù)膭澐至６葘Σ樵儏^(qū)域進行劃分。Morton碼長最長不超過32bit，同一個查詢區(qū)域在Morton碼匹配過程中，Morton碼長度種類不超過5種，且在面積全匹配的情況下，盡量使用更短的Morton碼來表示一個區(qū)域。二維空間劃分方式如圖3所示。

圖3 二維空間劃分

在整個編碼過程中，是將一個二維平面進行劃分，但地球表面是一個球體曲面，需將地球表面通過墨卡托（Mercator）投影來得到這樣一個二維平面，在投影的過程中，不同緯度上的地球表面在投影過程中會發(fā)生不同程度的形變。那么得到的不同緯度上的劃分后的方塊也會發(fā)生不同程度的形變。這樣在用編碼所表示方框匹配以中心點＋距離來表示區(qū)域查詢的時候，會帶來匹配面積上的誤差，且緯度越高，則誤差越大。通過在查詢面積匹配過程中在匹配面積前乘以一個調(diào)節(jié)因子cos（latitude＊π／180）來消除這種查詢誤差，實驗結(jié)果證明效果良好。

5 性能評估

索引結(jié)構(gòu)采用C＋＋實現(xiàn)，實驗平臺為：Windows XP系統(tǒng)、英特爾酷睿雙核3．2GHz處理器、2．96GB內(nèi)存。使用 Brinkhoff［12］的移動對象生成器生成動態(tài)移動對象數(shù)據(jù)，如圖4所示。數(shù)據(jù)包含了一定數(shù)量的移動對象在一段時間內(nèi)位置更新的相關(guān)信息，數(shù)據(jù)內(nèi)容包括移動對象ID、此次位置更新時間、位置X坐標（經(jīng)度）、位置Y坐標（緯度）等。

圖4 地理數(shù)據(jù)生成的地圖

5．1 時間效率

將MPT與B＋樹、Hash表、Trie樹進行查詢效率的比較。將生成的移動對象的位置的經(jīng)緯度數(shù)據(jù)轉(zhuǎn)換成32位二進制Morton碼，構(gòu)建索引結(jié)構(gòu)，進行查詢效率的比較。和B＋樹不同，MPT的普通操作，例如查詢、插入、刪除需要O（K）的時間（K表示字符串長度），而B＋樹中這些操作需要O（logn）的時間（n為字符串數(shù)），一般情況下O（k）＞O（logn），但是在B＋樹中對于字符串的比較最差情況需要O（K）的時間復雜度，當字符串的長度較長，則會明顯增加B＋樹中普通操作所花費的時間，這也是為什么B＋樹的效率相對不高的原因。而在MPT中，搜索過程中所有的比較操作所消耗的時間都是常數(shù)時間。哈希表的插入、查找、刪除的時間為O（1），但這是以計算哈希值的過程為常數(shù)時間當作前提的，當考慮了哈希值的計算時間，則需要O（k）的操作時間，加上如果在操作過程中發(fā)生哈希值的碰撞，則需要消耗更多的時間。而MPT則最壞時間為O（K）。而實驗結(jié)果也證實了這一點。MPT比哈希表的效率更高。MPT相對于Trie的優(yōu)勢則體現(xiàn)在2種結(jié)構(gòu)的特點，具體原因如3．2節(jié)所述。實驗結(jié)果如圖5所示。由于插入操作和刪除操作的大部分時間消耗都是用于查詢，因此得到的結(jié)果與查詢效率對比實驗類似，故此不再贅述。

圖5 查詢效率對比

圖6顯示了基于MPT的近鄰搜索算法與基于R－Tree的近鄰搜索算法效率的對比結(jié)果，因為MPT的搜索是根據(jù)二進制位的比較，而基于R－Tree的搜索算法是需要MBR（Minimum Bounding Rectangle）的比較，相比之下后者需要花費更多時間，并且R－Tree存在MBR互相重疊的問題，尤其處理大數(shù)據(jù)量時，基于R－Tree的近鄰查詢算法性能急劇惡化，而MPT因其結(jié)構(gòu)的特性并沒有上述問題。實驗結(jié)果表明，基于MPT的近鄰查詢算法效率更高。

圖6 近鄰搜索效率對比

5．2 空間占用

Morton碼的長度越長，則表示的位置越精確，但是使用MPT在近鄰搜索的過程中，使用過長的Morton碼對MPT近鄰搜索的過程并沒有幫助，反而因為過長的碼長而導致MPT中的結(jié)點數(shù)過多，所以會產(chǎn)生更多空間的占用。

表1表示經(jīng)緯度某一方向經(jīng)過一定次數(shù)的劃分后對應的Morton碼在這一方向上表示的范圍?？梢钥吹疆攧澐执螖?shù)為15時，Morton碼在這一方向上的精度為1 223m，就是約為1km左右，這時候?qū)拇a長為30，這樣的碼長是比較適合作為在交通道路網(wǎng)絡中近鄰搜索的起始碼長的。

表1 Morton碼精度與劃分次數(shù)對應表

圖7顯示了使用不同碼長的Morton碼所構(gòu)建的MPT索引所占的內(nèi)存大小，可以發(fā)現(xiàn)在碼長為30左右的時候，當插入MPT移動對象數(shù)據(jù)量到達一定的時候，索引所占的空間增長明顯減緩，這是因為索引結(jié)構(gòu)中大量減少了重復信息的存儲的緣故?；谶@樣的存儲優(yōu)勢，MPT索引結(jié)構(gòu)可以在應對大量移動對象信息的情形下使用。

圖7 MPT空間占用情況

6 結(jié)束語

本文在Morton和Patricia樹的基礎(chǔ)上提出一種一維索引結(jié)構(gòu)MPT，通過改良Patricia樹結(jié)構(gòu)，使得在索引結(jié)構(gòu)操作上有著更好的性能，并且合理利用Morton碼編碼方式，使索引結(jié)構(gòu)擁有比Geohash更加細粒度地區(qū)域劃分精度的控制，同時提出基于MPT的近鄰算法，其性能優(yōu)于基于R－Tree的近鄰搜索算法。通過將二維空間合理劃分，并將劃分的區(qū)域編碼，使索引結(jié)構(gòu)具有高效響應區(qū)域查詢的能力。因為考慮到近鄰查詢和區(qū)域查詢都是實時性較強，所以暫時并沒有考慮時間因素，下一步將把時間、位置信息編碼成一維信息，使得索引結(jié)構(gòu)能夠得到更廣泛的應用。

［1］廖 巍，熊 偉，景 寧．移動對象索引技術(shù)研究進展［J］．計算機科學，2006，33（8）：166－169．

［2］孟小峰，周龍驤，王 珊．數(shù)據(jù)庫技術(shù)發(fā)展趨勢［J］．軟件學報，2004，15（12）：1822－1836．

［3］Jensen C S，Lin Dan，Ooi B C．Query and Update Efficient B＋－tree Based Indexing of Moving Objects［C］／／Proceedings of the 30th International Conference on Very Large Data Bases．［S．1．］：VLDB Endowment，2004：768－779．

［4］Su Chen，Ooi B C，Tan K L，et al．ST2B－tree：A Selftunable Spatio－temporal B＋－tree Index for Moving Objects［C］／／Proceedings of ACM SIGMOD International Conference on Management of Data．New York，USA：ACM Press，2008：29－42．

［5］劉 玥，郝忠孝．基于Buddy＊－Hash的移動對象時空查詢方法［J］．計算機工程，2010，36（4）：47－49．

［6］Tao Yufei，Papadias D，Sun Jimeng．The TPR＊－tree：An Optimized Spatio－temporal Access Method for Predictive Queries［C］／／Proceedings of the 29th International Conference on Very Large Data Bases．［S．1．］：VLDB Endowment，2003：790－801．

［7］Simonas S C S J，Leutenegger S T，Lopez M A．Indexing the Positions of Continuously Moving Objects［C］／／Proceedings of SIGMOD’00．New York，USA：ACM Press，1999：331－342．

［8］徐紅波，郝忠孝．基于Hilbert曲線的近似k－最近鄰查詢算法［J］．計算機工程，2008，34（12）：47－49．

［9］劉潤濤，陳琳琳，田廣悅，等．Z曲線網(wǎng)格劃分的最近鄰查詢［J］．計算機工程與應用，2013，49（22）：123－126．

［10］徐紅波，郝忠孝．基于空間填充曲線網(wǎng)格劃分的最近鄰查詢算法［J］．計算機科學，2010，37（1）：184－188．

［11］Liu Jiajun，Li Haoran，Yong Gao et al．A Geohashbased Index for Spatial Data Management in Distributed Memory ［C］／／Proceedings of the 22nd International Conference on Geoinformatics．Washington D．C．，USA：IEEE Press，2014：1－4．

［12］Brinkhoff T．Generating Network－based Moving Objects［C］／／Proceedings of the 22nd International Conference on Scientific and Statistical Database Management．Washington D．C．，USA：IEEE Press，2000：253－255．