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

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

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

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

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

軌跡；時(shí)空索引；R樹；B＊樹；存儲(chǔ)

1　引 言

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

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

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

2　算法思路和索引結(jié)構(gòu)

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

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

（2）哈希表是輔助結(jié)構(gòu)，維護(hù)移動(dòng)對(duì)象的最新軌跡節(jié)點(diǎn)，用于成組插入采樣點(diǎn)；

（3）B＊樹是次要索引結(jié)構(gòu)，軌跡節(jié)點(diǎn)的一維索引，用于實(shí)現(xiàn)目標(biāo)對(duì)象的軌跡查詢。

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

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

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

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

3　算法流程和步驟

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

3.1 時(shí)空R樹評(píng)價(jià)指標(biāo)

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

時(shí)空評(píng)價(jià)值（N維空間+1維時(shí)間）EVAL：節(jié)點(diǎn)在N個(gè)空間坐標(biāo)軸的區(qū)間（S1，S2，…，SN）平均值的N次方與時(shí)間坐標(biāo)軸的區(qū)間（T）的乘積

選擇該評(píng)價(jià)指標(biāo)的原因來源于平均值不等式（以三維為例）對(duì)任意X、Y、Z＞0，總有當(dāng)且僅當(dāng)X=Y=Z時(shí)，等式成立。

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

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

3.2 HBSTR樹生成算法

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

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

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

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

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

算法輸出：更新后的索引結(jié)構(gòu)如下：

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

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

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

（4）生成新的軌跡節(jié)點(diǎn)，將Tuple插入其中，并替代Hash中OID對(duì)應(yīng)的TNode。

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

（6）算法終止。

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

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

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

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

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

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

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

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

5.While Father！=NULL Do

6.Node←Father.IthChild（SeqArray［Father.LevelID］）：Father第i個(gè)孩子作為當(dāng)前節(jié)點(diǎn)

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

TNode時(shí)

8.IfNode.LevelID=MinLevelIDThen：Node層號(hào)等于MinLevelID時(shí)

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

10.Else IfNode.LevelID〈MinLevelIDThen：Node層號(hào)小于MinLevelID時(shí)

11.NodeSet.Clear（）：清空NodeSet

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

13.MinLevelID←Node.LevelID：MinLevelID賦值為Node層號(hào)

14.End If

15.IfNode.LevelID〉1Then：Node層號(hào)大于1時(shí)，將進(jìn)入下層節(jié)點(diǎn)

16.Father←Node：Father賦值為Node

17.SeqArray［Father.LevelID］←0：給序號(hào)數(shù)組中的對(duì)應(yīng)元素賦值為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é)點(diǎn)的父節(jié)點(diǎn)層或者Node不包含Leaf

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

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

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

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

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

27.End If

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

29.End While

30.End If

31.End While

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

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

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

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

36.Else

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

38.End If

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

3.3 時(shí)空索引緩存機(jī)制

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

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

圖2　時(shí)空R樹索引緩存機(jī)制Fig.2 Cache mechanism for spatio-temporal R-tree

4　時(shí)空R樹索引存儲(chǔ)設(shè)計(jì)方案

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

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

5　試驗(yàn)方法與結(jié)果分析

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

5.1 試驗(yàn)環(huán)境設(shè)置

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

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

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

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

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

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

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

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

5.3 時(shí)空范圍查詢處理

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

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

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

圖3　時(shí)空范圍查詢效率對(duì)比Fig.3 Performance comparison in spatio-temporal range queries

5.4 目標(biāo)對(duì)象軌跡查詢

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

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

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

6　結(jié) 論

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

［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.（葉李.移動(dòng)對(duì)象數(shù)據(jù)庫查詢及處理技術(shù)研究［D］.成都：電子科技大學(xué)，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.（尹章才，李霖.基于快照-增量的時(shí)空索引機(jī)制研究［J］.測(cè)繪學(xué)報(bào)，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.（廖巍.面向位置服務(wù)的移動(dòng)對(duì)象索引與查詢處理技術(shù)研究［D］.長(zhǎng)沙：國防科學(xué)技術(shù)大學(xué)，2007.）

［4］ HAO Zhongxiao.New Theories of Spatio-temporal Database［M］.Beijing：Science Press，2011.（郝忠孝.時(shí)空數(shù)據(jù)庫新理論［M］.北京：科學(xué)出版社，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］.測(cè)繪學(xué)報(bào)，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)的移動(dòng)對(duì)象的位置索引與鄰近查詢方法［J］.測(cè)繪學(xué)報(bào)，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.（馬林兵，張新長(zhǎng).面向全時(shí)段查詢的移動(dòng)對(duì)象時(shí)空數(shù)據(jù)模型研究［J］.測(cè)繪學(xué)報(bào)，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的點(diǎn)目標(biāo)全時(shí)段移動(dòng)索引設(shè)計(jì)［J］.測(cè)繪學(xué)報(bào)，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樹集成的激光點(diǎn)云數(shù)據(jù)管理方法［J］.測(cè)繪學(xué)報(bào)，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.（龔俊，朱慶，張葉廷，等.顧及多細(xì)節(jié)層次的三維R樹索引擴(kuò)展方法［J］.測(cè)繪學(xué)報(bào)，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.

（責(zé)任編輯：陳品馨）

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

國家自然科學(xué)基金（41261086）；國家863計(jì)劃（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］.測(cè)繪學(xué)報(bào)，2015，44（5）：570-577.）

10.11947/j.AGCS.2015.20130520

2013-12-17

龔俊（1978—），男，博士，教授，研究方向?yàn)闀r(shí)空數(shù)據(jù)庫。

修回日期：2014-10-27