龔 俊，柯勝男，朱 慶，張葉廷.江西師范大學軟件學院，江西南昌00；.西南交通大學地球科學與環(huán)境工程學院，四川成都600；.武漢大學測繪遙感信息工程國家重點實驗室，湖北武漢40079

一種集成R樹、哈希表和B＊樹的高效軌跡數(shù)據(jù)索引方法

龔 俊1，柯勝男1，朱 慶2，張葉廷3
1.江西師范大學軟件學院，江西南昌330022；2.西南交通大學地球科學與環(huán)境工程學院，四川成都610031；3.武漢大學測繪遙感信息工程國家重點實驗室，湖北武漢430079

為兼顧時空索引方法的空間利用率、時間效率和查詢種類，提出了一種新的軌跡數(shù)據(jù)索引方法——HBSTR樹。其基本思想是：軌跡采樣點以軌跡節(jié)點的形式成組集中管理，哈希表用于維護移動目標的最新軌跡節(jié)點，軌跡節(jié)點滿后作為葉節(jié)點插入時空R樹，另外采用B＊樹對軌跡節(jié)點構建一維索引，既有利于提升索引創(chuàng)建效率，又同時滿足時空條件搜索和特定目標軌跡搜索等多種查詢類型。為提升時空查詢效率，提出了新的時空R樹評價指標和節(jié)點選擇子算法改進時空R樹插入算法，同時提出了一種時空R樹的數(shù)據(jù)庫存儲方案。試驗結果表明，HBSTR樹在創(chuàng)建效率、查詢效率和支持查詢類型等方面綜合性能優(yōu)于現(xiàn)有方法，支持大規(guī)模實時軌跡數(shù)據(jù)庫的動態(tài)更新和高效訪問。

軌跡；時空索引；R樹；B＊樹；存儲

1　引 言

全球各國重視和推動廣域室內(nèi)外高精度定位導航基礎設施建設，定位精度和可靠性將在城市環(huán)境內(nèi)得以顯著提升，自由的市場環(huán)境將使移動定位服務應用發(fā)生井噴式發(fā)展。同時，Web 2.0時代，社會大眾既是信息使用者也是提供者，隨著網(wǎng)絡隱私安全問題的技術及制度破解，專業(yè)數(shù)據(jù)庫服務器將不間斷收集具有潛在價值的巨量軌跡數(shù)據(jù)。迅猛發(fā)展的移動計算、無線傳輸技術和廣泛部署的室內(nèi)外定位設備對時空數(shù)據(jù)管理能力也提出全新需求，多源異構、時空異變、巨量增長、語義復雜成為時空數(shù)據(jù)庫的標志性特征，對現(xiàn)有數(shù)據(jù)庫索引方法提出嚴峻挑戰(zhàn)［1-2］。移動對象位置頻繁更新且規(guī)?？涨埃率顾饕Y構劇烈變化［3-4］。軌跡數(shù)據(jù)索引還要支持復雜的社會應用，如行為模式分析、智能交通決策等［5-7］。因此，軌跡數(shù)據(jù)索引方法除了關注大數(shù)據(jù)對查詢效率的影響，還要解決實時更新的代價問題，并要支持豐富的軌跡語義。

現(xiàn)有支持軌跡數(shù)據(jù)的時空索引方法主要分為3種類型：①基于版本的索引方法，即每個時間版本維護一套空間索引結構，目的是為節(jié)省存儲共享版本間未變節(jié)點，代表方法包括HR-Tree和MV3R-tree等，這類方法采用先時間后空間的策略，優(yōu)點是時刻查詢效率高，然而軌跡更新頻繁，要為每個更新時刻創(chuàng)建版本，使得維護成本極高，即使采用節(jié)點共享策略，仍將耗費大量存儲空間，且時空區(qū)間查詢效率低下；②空間劃分方法，即采用格網(wǎng)或四叉樹將采樣點散列劃分到對應空間內(nèi)，進而為空間中的對象采樣點構建時間索引，代表方法包括SETI和CSE等，其關鍵點是對地理空間進行一維編碼，即將二維問題轉(zhuǎn)換為一維問題，再將一維地理編碼+時間構建為一維復合索引（如B＊樹），這類方法采用先空間后時間的策略，優(yōu)點是采用地理哈希思想，空間區(qū)域劃分固定，構建索引和查詢效率較高，缺點是僅適合點的場合，非點對象落于空間劃分邊界上將導致重復索引，同時要求預設空間范圍，索引結構不均衡易致效率下降；③擴展時間維的多維索引方法，即在傳統(tǒng)空間索引結構（如R樹）中增加時間維，代表方法包括STR樹和TB樹等，這類方法采用空間和時間等同地位策略，然而TB樹及變種更重視時間序列特性和顯式軌跡描述，這類方法屬于R樹變種，可隨數(shù)據(jù)分布動態(tài)調(diào)整索引結構，時空查詢效率較好，缺點是索引創(chuàng)建效率易惡化［8-12］。

隨著應用的綜合性要求日益突出，全時段的移動對象數(shù)據(jù)模型及其索引方法被深入研究，混合索引方法成為一種發(fā)展趨勢［13-15］。本文提出一種軌跡索引方法，它是一種聯(lián)合哈希表和B樹的時空R樹方法（Hash &B＊-tree combined spatio-temporal R-tree，HBSTR-tree）。

2　算法思路和索引結構

索引設計既要了解數(shù)據(jù)特點，還要明確查詢需求，索引方法通常受到創(chuàng)建效率、存儲利用率、查詢效率、查詢種類、緩存機制等需求的影響［16］。本文旨在為實時增量軌跡數(shù)據(jù)庫提供索引支持，采用集成R樹、哈希表和B＊樹的混合索引方法HBSTR-tree，圖1是HBSTR-tree的原理和框架示意圖。3種子索引結構的作用分別為：

（1）R樹是主體索引結構，用于實現(xiàn)時空范圍查詢；

（2）哈希表是輔助結構，維護移動對象的最新軌跡節(jié)點，用于成組插入采樣點；

（3）B＊樹是次要索引結構，軌跡節(jié)點的一維索引，用于實現(xiàn)目標對象的軌跡查詢。

采樣點包含對象標識符、時間戳和空間位置等數(shù)據(jù)項，由于傳感器遮擋或者不穩(wěn)定等因素，采樣點空間位置數(shù)據(jù)可能出現(xiàn)粗差，一般采用某些數(shù)據(jù)清洗方法過濾粗差數(shù)據(jù)［17］。單個移動對象的采樣點數(shù)目數(shù)以萬計，分散管理采樣點不利于查找軌跡，對存儲利用率和創(chuàng)建效率均會產(chǎn)生負面影響。本文將連續(xù)采樣點成組集中存儲于軌跡節(jié)點，軌跡節(jié)點僅存儲單個對象的連續(xù)采樣點?，F(xiàn)實應用中相鄰采樣點有可能間隔很長時間，如果相鄰采樣點的時間間隔超過設定閾值Tthres，則重新采用新節(jié)點存儲后續(xù)采樣點。

哈希表用于管理所有對象的最新軌跡節(jié)點，便于通過對象標識符查找對象的最新軌跡節(jié)點，當一個軌跡節(jié)點滿時，插入R樹，創(chuàng)建新的軌跡節(jié)點接收新采樣點。這樣，以節(jié)點形式成組插入時空R樹的方式，可大幅度提升索引創(chuàng)建效率。

HBSTR-tree中，R樹是N+1維（N是空間維數(shù)，1指時間維）的時空R樹，R樹節(jié)點最小包圍盒MBR（minimal bounding rectangle）是其孩子集合的時空坐標軸最小范圍，時間參考采用1970年以來的絕對秒數(shù)作為基準。上文軌跡節(jié)點作為R樹的葉節(jié)點，采用一種新的節(jié)點插入算法（第3節(jié)介紹）將其索引項插入葉節(jié)點層的上一層中，利用節(jié)點選擇和節(jié)點分裂子算法優(yōu)化時空R樹結構。時空R樹支持多種查詢類型，如搜索某時空范圍內(nèi)的對象集合、對象軌跡，或者某時刻某空間范圍內(nèi)的對象集合、對象位置，或者某時刻某空間點的最近鄰對象等。時空R樹搜索目標對象在某時間段內(nèi)的軌跡并不高效。為解決該問題，本文方法采用軌跡節(jié)點的對象標識符OID和起始時間tTimeStart組成一維關鍵碼（OID+ tTimeStart）構建軌跡節(jié)點的B＊樹索引，借助B＊樹的一維查詢能力，高效定位某對象在某時刻的軌跡節(jié)點，利用B＊樹兄弟節(jié)點間的雙向指針進行軌跡追溯。軌跡節(jié)點通常包含近百個連續(xù)采樣點，相對于直接采樣點的一維索引結構，本文方法節(jié)省存儲空間90%以上。

圖1　HBSTR樹的原理和框架Fig.1 Principle and framework of HBSTR-tree

3　算法流程和步驟

本文針對軌跡查詢需求改進時空R樹算法，本節(jié)將予以詳細介紹。由于哈希表和B＊樹是經(jīng)典算法，不再贅述。

3.1 時空R樹評價指標

鑒于多方面綜合考慮，既要鼓勵MBR在空間上形成規(guī)則塊狀，也要保證時間區(qū)分度，參考文獻［18］，本文提出時空評價值的定義作為時空R樹評價指標。

時空評價值（N維空間+1維時間）EVAL：節(jié)點在N個空間坐標軸的區(qū)間（S1，S2，…，SN）平均值的N次方與時間坐標軸的區(qū)間（T）的乘積

選擇該評價指標的原因來源于平均值不等式（以三維為例）對任意X、Y、Z＞0，總有當且僅當X=Y=Z時，等式成立。

假設XYZ的值一定時，當X=Y=Z時，X、、Z的平均值3次方最小，即三維矩形體積一定時，當為立方體時最小。因此，將

引入MBR評價標準EVAL，有助于控制節(jié)點的空間范圍，即其值越小，MBR的空間形態(tài)越趨近規(guī)則塊狀體，此外，T越小，EVAL也相應越小，引入T有助于控制節(jié)點的時間范圍，控制EVAL值有助于優(yōu)化時空R樹節(jié)點的區(qū)分度。

3.2 HBSTR樹生成算法

為滿足外存索引要求，R樹中的每個節(jié)點對應一個外存數(shù)據(jù)頁，根據(jù)操作系統(tǒng)和數(shù)據(jù)庫的基本參數(shù)設置數(shù)據(jù)頁尺寸（如2K或3K），而數(shù)據(jù)頁尺寸也決定了節(jié)點中孩子數(shù)目，由于葉節(jié)點和非葉節(jié)點結構不同，葉節(jié)點中的軌跡元組數(shù)目和非葉節(jié)點中孩子節(jié)點數(shù)目不相等。同時，依據(jù)R樹的特點，為保證節(jié)點的層號終生不變，將葉節(jié)點層號設為0，其他層依次向上加1，如葉節(jié)點的父節(jié)點層號為1，因為R樹層數(shù)增加時，發(fā)生在根節(jié)點分裂時，此時生成新的根節(jié)點，其層號為原根節(jié)點層號加1。

下面給出HBSTR樹生成算法的步驟描述。節(jié)點分裂子算法采用傳統(tǒng)方法，節(jié)點選擇子算法與傳統(tǒng)方法有所不同，本文重點給出它的詳細步驟，節(jié)點選擇和節(jié)點分裂中均采用上文所述的時空范圍評價指標。

首先簡單介紹算法描述中涉及的元素。待插入采樣點Tuple｛OID，Time，Pos，ROWID，etc｝，其中，OID是采樣點所屬的對象標識符；Time是采樣點獲取時刻；Pos是采樣點地理位置；ROWID是采樣點記錄的外存指針。HBSTR索引結構，包括哈希表Hash（OID映射至軌跡節(jié)點TNode）、B＊樹Btree（索引鍵值是對象標識符OID+軌跡節(jié)點開始時間tStartTime）和時空軌跡R樹Rtree。算法中TNode是對應于OID的軌跡節(jié)點，用于存儲某移動對象的連續(xù)軌跡點，達到規(guī)定上限后插入時空軌跡R樹成為葉節(jié)點，其結構為｛OID，tStartTime，tEndTime，MBR，etc｝，其中，OID是對象標識符；tStartTime是開始時間；tEndTime是終止時間；MBR是空間范圍。

算法1描述：HBSTR樹的動態(tài)插入算法。

算法輸入：待插入采樣點元組Tuple，HBSTR已有索引結構，連續(xù)軌跡結束時間閾值Tthres，節(jié)點緩存清除時間閾值Tcnode。

算法輸出：更新后的索引結構如下：

（1）通過Hash查找OID對應的軌跡節(jié)點TNode。如果Time相對TNode結束時間tEndTime超出時間閾值Tthres，進入步驟（2）；否則，將Tuple插入TNode，并更新TNode，如果TNode已滿，進入步驟（2），否則退出算法。

（2）利用節(jié)點選擇子算法1.1為TNode選擇適合插入的第1層節(jié)點Father，插入TNode，如果導致Father上溢，則采用節(jié)點分裂子算法將Father一分為二，如果導致Father的父節(jié)點上溢，采用節(jié)點分裂算法遞歸處理，直至根節(jié)點。

（3）將TNode的OID和tStartTime的組合鍵加入Btree增加索引項。

（4）生成新的軌跡節(jié)點，將Tuple插入其中，并替代Hash中OID對應的TNode。

（5）獲取Rtree的主存Cache中的節(jié)點數(shù)目NodesNum，如果NodesNum超出閾值，則從根節(jié)點開始從緩存中清除Tcnode未訪問的節(jié)點。

（6）算法終止。

本文時空R樹節(jié)點選擇子算法與傳統(tǒng)方法有所區(qū)別，其思想是，在R樹中搜索完全包含待插節(jié)點時空范圍的最下層節(jié)點集合，從集合中選擇一個節(jié)點，此時該節(jié)點的子孫節(jié)點均不可能包含待插節(jié)點，則以該節(jié)點為根節(jié)點從上而下尋找最適合插入待插節(jié)點的第一層節(jié)點。本算法的優(yōu)點在于可以避免節(jié)點重疊對選擇結果的不良影響，采用非遞歸思想設計算法，保證良好的時間效率。節(jié)點選擇子算法是本算法的核心，采用偽碼方式描述算法流程，見下文。

算法：節(jié)點選擇子算法（選出適合插入TNode的第1層節(jié)點，注意，葉節(jié)點處于第0層）

算法輸入：待插入的軌跡節(jié)點TNode，時空R樹根節(jié)點Root

算法輸出：適合插入TNode的第1層節(jié)點

1.NodeSet.Clear（）：清空節(jié)點集合

2.MinLevelID←Root.LevelID+1：變量MinLevelID用于記錄已搜索的符合條件最底層節(jié)點的層號，賦初值為樹深即大于任意節(jié)點的層號

3.Father←Root：變量Father賦初值為根節(jié)點

4.SeqArray［Father.LevelID］←0；：數(shù)組SeqArray第Father.LevelID個值賦值為0，該數(shù)組用于記錄當前節(jié)點Node在父節(jié)點和祖先節(jié)點中的序號

5.While Father！=NULL Do

6.Node←Father.IthChild（SeqArray［Father.LevelID］）：Father第i個孩子作為當前節(jié)點

7.IfNode.Contain（TNode）=True Then：Node包含

TNode時

8.IfNode.LevelID=MinLevelIDThen：Node層號等于MinLevelID時

9.NodeSet.Add（Node）：將Node加入NodeSet

10.Else IfNode.LevelID〈MinLevelIDThen：Node層號小于MinLevelID時

11.NodeSet.Clear（）：清空NodeSet

12.NodeSet.Add（Node）：將Node加入NodeSet

13.MinLevelID←Node.LevelID：MinLevelID賦值為Node層號

14.End If

15.IfNode.LevelID〉1Then：Node層號大于1時，將進入下層節(jié)點

16.Father←Node：Father賦值為Node

17.SeqArray［Father.LevelID］←0：給序號數(shù)組中的對應元素賦值為0

18.Continue Loop：重新開始新一輪循環(huán)

19.End If

20.End If

21.IfNode.LevelID=1Or Node.Contain（TNode）= False Then：假如Node已經(jīng)處于第1層，即葉節(jié)點的父節(jié)點層或者Node不包含Leaf

22.SeqArray［Father.LevelID］←SeqArray［Father. LevelID］+1：序號加1，繼續(xù)判斷下一個孩子節(jié)點

23.WhileSeqArray［Father.LevelID］=Father.Num-ChildrenDo：如果所有孩子節(jié)點已遍歷完畢

24.Father←Father.ParentNode：回退至上層節(jié)點

25.If Father=NULL Then：如果根節(jié)點所有孩子遍歷完畢

26.Break Loop：退出循環(huán)

27.End If

28.SeqArray［Father.LevelID］←SeqArray［Father. LevelID］+1：某節(jié)點已遍歷，開始遍歷其右兄弟節(jié)點

29.End While

30.End If

31.End While

32.If NodeSet.IsEmpty（）=True Then：如果NodeSet為空，表示樹中不存在包含TNode的節(jié)點

33.NewRoot←Root：將根節(jié)點Root賦給變量NewRoot

34.Else IfMinLevelID=1Then：如果第一層中存在滿足條件的節(jié)點

35.NewRoot←LargestNode（NodeSet）：選擇其中時空范圍最大的節(jié)點作為NewRoot

36.Else

37.從NodeSet全部節(jié)點的所有孩子節(jié)點集合Set中選擇包含TNode后時空范圍變化最小的節(jié)點作為N ewRoot

38.End If

39.以NewRoot為根節(jié)點，采用傳統(tǒng)節(jié)點選擇算法從上而下搜索第1層節(jié)點作為輸出結果

3.3 時空索引緩存機制

實時應用中，軌跡索引創(chuàng)建過程通常是按照數(shù)據(jù)元組的有效時間順序?qū)嵤?，一般來說當前時間是查詢焦點。最近被訪問的數(shù)據(jù)近期被再訪問的幾率較大，如果緩存中持有這些數(shù)據(jù)，可減少外存訪問次數(shù)。時空數(shù)據(jù)庫的元組記錄數(shù)目數(shù)以億計，中等規(guī)模數(shù)據(jù)庫的時空索引數(shù)據(jù)量就超過GB字節(jié)，不允許在內(nèi)存中構建全部索引然后持久化至數(shù)據(jù)庫中。同時，樹型結構通常在堆內(nèi)存中動態(tài)分配節(jié)點空間，全部維持在緩存中極易導致系統(tǒng)性能不穩(wěn)定。

為此，本文設計一個基于LRU算法（近期最少使用算法）的時空索引緩存方法，其原理是，設定一個時間閾值T，每間隔一定時間清理時空索引樹緩存，從緩存中釋放從當前時間算起已有T時間沒有被訪問的節(jié)點數(shù)據(jù)，后面需要可再根據(jù)父節(jié)點中的子節(jié)點ROWID訪問外存，圖2描述了本索引緩存機制。為此，節(jié)點結構定義一個變量TLRU用于記錄節(jié)點最近被訪問時間，節(jié)點一經(jīng)訪問，其TLRU即被更新為當前時刻。由于樹狀索引的操作通常以根節(jié)點為入口，滿足條件則向下進入子節(jié)點，不滿足則剪枝不再深入，訪問子節(jié)點的同時，必定也訪問父節(jié)點，保證父節(jié)點的TLRU不早于子節(jié)點。因此，如果父節(jié)點過時，以其為根節(jié)點的子樹中所有節(jié)點均過時，可從索引緩存中釋放子樹。本文采用C++智能指針管理R樹索引中的緩存節(jié)點指針，釋放父節(jié)點時其子節(jié)點的引用計數(shù)自動減一，自上而下安全釋放所有子孫節(jié)點。

圖2　時空R樹索引緩存機制Fig.2 Cache mechanism for spatio-temporal R-tree

4　時空R樹索引存儲設計方案

呈指數(shù)增加的移動應用用戶使得移動對象數(shù)據(jù)管理方法需要云存儲支持［19］。本文選擇采用NoSQL數(shù)據(jù)庫MongoDB作為實現(xiàn)HBSTR樹的存儲介質(zhì)。MongoDB的組織結構是數(shù)據(jù)庫-數(shù)據(jù)集-文檔-元素，數(shù)據(jù)集類似于關系數(shù)據(jù)庫中的表，文檔類似于記錄，元素類似于字段。MongoDB數(shù)據(jù)集內(nèi)的文檔即記錄不要求結構嚴格相同，適合存儲結構不固定的數(shù)據(jù)內(nèi)容集。

本節(jié)將重點介紹時空R樹的數(shù)據(jù)庫存儲方案。時空R樹索引結構存儲于獨立數(shù)據(jù)集中，為便于識別，時空索引數(shù)據(jù)集的名稱是對應時空數(shù)據(jù)集的名稱后綴加.STI＿Index，如數(shù)據(jù)集DataSet的時空R樹索引數(shù)據(jù)集為DataSet.STI＿Index。時空R樹索引元信息包括數(shù)據(jù)庫名稱、數(shù)據(jù)集名稱、索引數(shù)據(jù)集名稱、空間維度、時空R樹扇出參數(shù)、節(jié)點數(shù)目以及根節(jié)點的ROWID號。根節(jié)點的ROWID號是根節(jié)點文檔的唯一標識符，通過它從數(shù)據(jù)庫中讀取根節(jié)點數(shù)據(jù)，進而讀取R樹中任何節(jié)點的數(shù)據(jù)。MongoDB的每條文檔都有一個ROWID，如果用戶不指定，系統(tǒng)自動根據(jù)服務器、進程和當前時間等信息創(chuàng)建類型為12個字節(jié)的數(shù)組，它是MongoDB實現(xiàn)分布式存儲的重要基礎。為了方便查找時空索引元信息，元信息被集中存儲于用戶指定ROWID（如“999999999999”）的一條文檔中。除元信息外，單個時空R樹節(jié)點也被作為文檔存入數(shù)據(jù)集，節(jié)點分為葉節(jié)點和非葉節(jié)點，葉節(jié)點存儲元組集合信息，非葉節(jié)點存儲孩子節(jié)點集合信息，二者結構不同，為存儲方便，本文將節(jié)點數(shù)據(jù)和元信息組織為二進制塊即BinData類型元素存入文檔。葉節(jié)點另外記錄對象標識符和連續(xù)軌跡采樣點，非葉節(jié)點則記錄孩子節(jié)點信息，如孩子節(jié)點的時空范圍等。R樹中的父節(jié)點保存孩子節(jié)點的外存地址（ROWID）和MBR等作為指針項，訪問父節(jié)點即可知道其孩子節(jié)點是否滿足粗查要求。本文詳細存儲方案可參照文獻［20］。

5　試驗方法與結果分析

本節(jié)從索引創(chuàng)建和時空查詢處理等方面綜合測試HBSTR樹，由于TB＊樹是當前綜合性能最優(yōu)的軌跡索引，本文選擇TB＊樹與HBSTR樹進行分析對比。為了試驗對比的公正性和科學性，TB＊樹中的葉節(jié)點僅在充滿后插入樹中。

5.1 試驗環(huán)境設置

HBSTR樹的數(shù)據(jù)頁尺寸設置為3kB，時空R樹葉節(jié)點和非葉節(jié)點的最大扇出參數(shù)分別為80和40，非葉節(jié)點的最小扇出參數(shù)是最大扇出參數(shù)的40%，即為16。除葉節(jié)點的雙向鏈表指針外，TB＊樹具有相同于時空R樹的結構，因此TB＊樹的扇出參數(shù)可設為相同?？臻g坐標采用雙精度浮點型數(shù)據(jù)類型，時間坐標采用64位整型數(shù)據(jù)類型。試驗運行軟硬件是：64位Window 7操作系統(tǒng)，64位MongoDB數(shù)據(jù)庫，Intel Core I7-3770M3.40GHz中央處理器，8GB主存和1TB外存（7200rpm，64MB高速緩存）。

本文采用Brinkhoff的時空數(shù)據(jù)生成器生成不同規(guī)模的數(shù)據(jù)樣本，該生成器被廣泛用于時空數(shù)據(jù)庫的性能測試［21］。表1是試驗采用的4份不同規(guī)模數(shù)據(jù)集的描述，這些數(shù)據(jù)集基于德國Oldenburg市的真實路網(wǎng)數(shù)據(jù)生成，它們具有相同時空區(qū)間，空間范圍［xmin，ymin，xmax，ymax］均為［281，3935，23 854，30 851］，而移動對象數(shù)目和軌跡點數(shù)目存在差異。

表1　試驗樣本數(shù)據(jù)集描述Tab.1 Description of experimental datasets

5.2 索引創(chuàng)建的時間性能和存儲效率

對TB＊樹和HBSTR樹的創(chuàng)建效率進行對比試驗，二者均采用經(jīng)典R樹的平方級分裂策略。表2是索引創(chuàng)建的試驗結果，其中包括時間開銷和存儲代價。以O5000K數(shù)據(jù)樣本為例，創(chuàng)建TB＊樹花費439s，而HBSTR樹花費454s，上述時間開銷均涵蓋樣本數(shù)據(jù)訪問和索引數(shù)據(jù)持久化的開銷。

假設插入操作為原子操作，TB＊樹和HBSTR樹的創(chuàng)建算法的時間復雜度均為O（N/ M），其中，N是軌跡點數(shù)目，M是葉節(jié)點的最大扇出參數(shù)。R樹插入操作是費時過程，其中包括節(jié)點選擇和節(jié)點分裂兩個環(huán)節(jié)。HBSTR樹中的節(jié)點選擇操作比TB＊樹復雜，時間復雜度為O（logMN）。除HBSTR樹的時空R樹評價因子外，節(jié)點分裂過程和經(jīng)典R樹相同，因此時間復雜度為O（A2），其中A是非葉節(jié)點的最大扇出參數(shù)。創(chuàng)建HBSTR樹的節(jié)點選擇和節(jié)點分裂操作次數(shù)略微高于TB＊樹，因此HBSTR樹的時間開銷更大。需要指出的是，節(jié)點選擇操作次數(shù)等于葉節(jié)點數(shù)目，節(jié)點分裂操作次數(shù)等于非葉節(jié)點數(shù)目。

表2　索引創(chuàng)建試驗結果（以O5000K數(shù)據(jù)樣本為例）Tab.2 Experimental results of index generation（dataset O5000K）

評價索引性能中一項容易被忽略的因素是索引結構數(shù)據(jù)量。HBSTR樹有一個內(nèi)存子索引（Hash）和兩個外存子索引（R樹和B＊樹），因此其存儲代價為R樹和B＊樹二者之和。以O5000K數(shù)據(jù)樣本為例，HBSTR樹的數(shù)據(jù)量是221MB，其中兩個子索引分別為216MB和5MB。由于非葉節(jié)點的最小扇出參數(shù)為16，R樹節(jié)點中的絕大多數(shù)超過94%是葉節(jié)點。鑒于HBSTR樹的原理，HBSTR樹中時空R樹大部分葉節(jié)點的存儲空間能夠被完全利用。子索引B＊樹僅索引時空R樹葉節(jié)點，其索引鍵是葉節(jié)點的OID/timestamp，因此，其存儲代價遠小于R樹。為顯式保存軌跡，TB＊樹另外維護葉節(jié)點間的雙向鏈表結構，需要額外的存儲空間。相對于675MB的原始數(shù)據(jù)樣本，TB＊樹和HBSTR樹均得以明顯壓縮。

5.3 時空范圍查詢處理

查詢時空范圍內(nèi)的軌跡點是軌跡數(shù)據(jù)庫中最常見的操作，本節(jié)對TB＊樹和HBSTR樹進行時空范圍查詢處理性能對比和分析。本節(jié)采用3組范圍查詢條件（Q1—Q3）進行試驗測試，每組包含100個隨機查詢窗口條件，3組查詢條件分別是有效時空范圍的軸向區(qū)間的1%、2%和4%，并將3組查詢條件均實施于不同規(guī)模的合成數(shù)據(jù)集（O5000K-O40000K）。

將100次窗口查詢處理數(shù)據(jù)平均值作為試驗結果，圖3是不同數(shù)據(jù)規(guī)模的范圍查詢效率對比。在Q1—Q3等3組查詢條件上，HBSTR樹相對于TB＊樹具有明顯的查詢優(yōu)勢。TB＊樹和HBSTR樹有相同的葉節(jié)點集合，因此，查詢命中的葉節(jié)點集合是相同的。

查詢范圍越大，葉節(jié)點命中幾率越大，占全部被訪問節(jié)點的百分比更高。同時，葉節(jié)點顯著多于非葉節(jié)點，因此，當查詢條件范圍變大時，訪問節(jié)點數(shù)目差異進一步增加，但是相對差距縮小。

圖3　時空范圍查詢效率對比Fig.3 Performance comparison in spatio-temporal range queries

5.4 目標對象軌跡查詢

另一個常見操作是查詢某時間區(qū)間內(nèi)指定目標的移動軌跡。分別從4個數(shù)據(jù)集合中隨機選擇100個移動對象，同時，隨機選擇移動對象生命周期的10%作為軌跡試驗的查詢條件。表3是上述4組數(shù)據(jù)集的試驗結果，軌跡查詢操作中節(jié)點訪問數(shù)目的平均值作為試驗結果。

HBSTR樹中，B＊樹子索引直接定位滿足查詢條件的首葉節(jié)點，然后向后掃描和逐一輸出滿足條件的葉節(jié)點，以致避免多余節(jié)點訪問。相反，TB＊樹從根節(jié)點搜索整個樹結構。在首個目標葉節(jié)點命中后，葉節(jié)點間的雙向鏈表被用于搜索滿足條件的葉節(jié)點。顯然，上述查詢過程并不穩(wěn)定可靠，有時可能會遍歷全樹。由于一個對象的10%連續(xù)軌跡點存在于1～2個葉節(jié)點，HBSTR樹僅需訪問1～2個葉節(jié)點，另外需要訪問B＊樹子索引，其節(jié)點訪問也要考慮在內(nèi)。假如B＊樹節(jié)點中最大關鍵碼數(shù)目是100，O5000K、O10000K、O20000K和O40000K的B＊樹層數(shù)均為3。在一次查詢操作中，B＊樹每層僅一個節(jié)點被訪問。

表3　軌跡查詢處理的節(jié)點訪問數(shù)目Tab.3 Node accesses in trajectory queries

6　結 論

本文提出的軌跡索引方法充分利用R樹、B＊樹和哈希表等索引的優(yōu)點，支持時空范圍查詢和目標對象軌跡查詢等多種查詢方式，在索引創(chuàng)建效率上和TB＊樹相近，在時空查詢效率上明顯優(yōu)于TB＊樹，滿足大規(guī)模軌跡數(shù)據(jù)庫的實時更新管理要求，適應時空查詢處理的多樣化需求。同時提出了一種數(shù)據(jù)庫存儲管理方案，可以支持云存儲業(yè)務需求。大規(guī)模實時軌跡數(shù)據(jù)管理是智能交通和社交網(wǎng)絡等焦點應用的支撐技術，后續(xù)工作還要針對復雜地學應用增加時空過程模擬與分析能力。

［1］ YE Li.Research on Data Queries and Processing Techniques in Moving Objects Databases［D］.Chengdu：University of Electronic Science and Technology of China，2011.（葉李.移動對象數(shù)據(jù)庫查詢及處理技術研究［D］.成都：電子科技大學，2011.）

［2］ YIN Zhangcai，LI Lin.Research of Spatiotemporal Indexing Mechanism Based on Snapshot-increment［J］.Acta Geodaetica et Cartographica Sinica，2005，34（3）：257-261，282.（尹章才，李霖.基于快照-增量的時空索引機制研究［J］.測繪學報，2005，34（3）：257-261，282.）

［3］ LIAO Wei.Indexing and Query Processing on Moving Objects in Location-based Services［D］.Changsha：National University of Defense Technology，2007.（廖巍.面向位置服務的移動對象索引與查詢處理技術研究［D］.長沙：國防科學技術大學，2007.）

［4］ HAO Zhongxiao.New Theories of Spatio-temporal Database［M］.Beijing：Science Press，2011.（郝忠孝.時空數(shù)據(jù)庫新理論［M］.北京：科學出版社，2011.）

［5］ LI Qingquan，HUANG Lian.A Map Matching Algorithm for GPS Tracking Data［J］.Acta Geodaetica et Cartographica Sinica，2010，39（2）：207-212.（李清泉，黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法［J］.測繪學報，2010，39（2）：207-212.）

［6］ XU Lin，LI Qingquan，YANG Bisheng.A Moving Object Index Structure and Near Neighbor Query Method Based on Road Network［J］.Acta Geodaetica et Cartographica Sinica，2010，39（3）：316-321，327.（許林，李清泉，楊必勝.一種基于道路網(wǎng)的移動對象的位置索引與鄰近查詢方法［J］.測繪學報，2010，39（3）：316-321，327.）

［7］ PARENT C，SPACCAPIETRA S，RENSO C.Semantic Trajectories Modeling and Analysis［J］.ACM Computing Surveys，2013，45（4）：42：1-42：32.

［8］ ZHENG Y，ZHOU X.Computing with Spatial Trajectories［M］.New York：Springer-Verlag，2011.

［9］ FRENTZOS E.Trajectory Data Management in Moving Object Databases［D］.Piraeus：University of Piraeus，2008.

［10］ MOKBEL M，GHANEM T，AREF W.Spatio-temporal Access Methods［J］.IEEE Data Engineering Bulletin，2003，26：40-49.

［11］ NGUYEN-DINH L，AREF W，MOKBEL M.Spatio-temporal Access Methods：Part2（2003-2010）［J］.IEEE Data Engineering Bulletin，2010，33：46-55.

［12］ CHAKKA V，EVERSPAUGH A，PATEL J.Indexing Large Trajectory Data Sets with SETI［C］∥Proceedings of the 2003CIDR Conference.Asilomar：［s.n.］，2003.

［13］ MA Linbing，ZHANG Xinchang.Research on Full-period Query Oriented Moving Objects Spatio-temporal Data Model［J］.Acta Geodaetica et Cartographica Sinica，2008，37（2）：207-211，222.（馬林兵，張新長.面向全時段查詢的移動對象時空數(shù)據(jù)模型研究［J］.測繪學報，2008，37（2）：207-211，222.）

［14］ GUO Jing，LIU Guangjun，GUO Lei，et al.A Wholetime Index Design Based on 3D+-TPR-tree for Moving Point Targets［J］.Acta Geodaetica et Cartographica Sinica，2006，35（3）：267-272.（郭晶，劉廣軍，郭磊，等.基于3D+-TPR-tree的點目標全時段移動索引設計［J］.測繪學報，2006，35（3）：267-272.）

［15］ GONG Jun，KE Shengnan，ZHU Qing，et al.An Efficient Management Method for Point Cloud Data Based on Octree and 3DR-tree［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：597-604.（龔俊，柯勝男，朱慶，等.一種八叉樹和三維R樹集成的激光點云數(shù)據(jù)管理方法［J］.測繪學報，2012，41（4）：597-604.）

［16］ PFOSER D，JENSEN C，THEODORIDIS Y.Novel Approaches to the Indexing of Moving Object Trajectories［C］∥Proceedings of the International Conference on Very Large Data Bases.Cairo：［s.n.］，2000.

［17］ AGGARWAL C.Managing and Mining Sensor Data［M］. New York：Springer Publishing，2013.

［18］ GONG Jun，ZHU Qing，ZHANG Yeting，et al.An Efficient 3DR-tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249-255.（龔俊，朱慶，張葉廷，等.顧及多細節(jié)層次的三維R樹索引擴展方法［J］.測繪學報，2011，40（2）：249-255.）

［19］ LEE D，LIANG S.Geopot：A Cloud-based Geolocation Data Service for Mobile Applications［J］.International Journal of Geographical Information Science，2011，25（8）：1283-1301.

［20］ KE S，GONG J，LI S，et al.A Hybrid Spatio-temporal Data Indexing Method for Trajectory Databases［J］.Sensors，2014，14（7）：12990-13005.

［21］ BRINKHOFF T.A Framework for Generating Network-based Moving Objects［J］.GeoInformatica，2002，6（2）：153-180.

（責任編輯：陳品馨）

E-maiI：gongjunbox@163.com

An Efficient Trajectory Data Index Integrating R-tree，Hash and B＊-tree

GONG Jun1，KE Shengnan1，ZHU Qing2，ZHANG Yeting3
1.SchooI of Software，Jiangxi NormaI University，Nanchang 330022，China；2.FacuIty of Geosciences and EnvironmentaI Engineering，Southwest Jiaotong University，Chengdu 610031，China；3.State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing，Wuhan University，Wuhan 430079，China

To take into account aII of efficiency and query capabiIity，this paper presents a new trajectory data index named HBSTR-tree.In HBSTR-tree，trajectory sampIe points are coIIectiveIy stored into trajectory nodes sequentiaIIy.Hash tabIe is adopted to index the most recent trajectory nodes of mobiIe targets，and trajectory nodes wiII not be inserted into spatio-temporaI R-tree untiI fuII，which can enhance generation performance in this way.Meantime，one-dimensionaI index of trajectory nodes in the form of B＊-tree is buiIt.Therefore，HBSTR-tree can satisfy both spatio-temporaI query and target trajectory query.In order to improve search efficiency，a new criterion for spatio-temporaI R-tree and one new node-seIection sub-aIgorithm are put forward，which further optimize insertion aIgorithm of spatio-temporaI R-tree.Furthermore，a database storage scheme for spatio-temporaI R-tree is aIso brought up.ExperimentaI resuIts prove that HBSTR-tree outperforms current methods in severaI aspects such as generation efficiency，query performance and supported query types，and then supports reaI-time updates and efficient accesses of huge trajectory database.

trajectory；spatio-temporaI index；R-tree；B＊-tree；storage

The NationaI NaturaI Science Foundation of China（No.41261086）；The NationaI Hightech Research and DeveIopment Program of China（863 Program）（No.2012AA121401）

GONG Jun（1978—），maIe，PhD，professor，majors in spatio-temporaI database.

P208

A

1001-1595（2015）05-0570-08

國家自然科學基金（41261086）；國家863計劃（2012AA121401）

GONG Jun，KE Shengnan，ZHU Qing，et al.An Efficient Trajectory Data Index Integrating R-tree，Hash and B＊-tree［J］. Acta Geodaetica et Cartographica Sinica，2015，44（5）：570-577.（龔俊，柯勝男，朱慶，等.一種集成R樹、哈希表和B＊樹的高效軌跡數(shù)據(jù)索引方法［J］.測繪學報，2015，44（5）：570-577.）

10.11947/j.AGCS.2015.20130520

2013-12-17

龔俊（1978—），男，博士，教授，研究方向為時空數(shù)據(jù)庫。

修回日期：2014-10-27