張郁彬，張深深，孟旭東

(1.寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；2.南京郵電大學(xué) 江蘇省電信網(wǎng)絡(luò)融合實(shí)驗(yàn)室，江蘇 南京 210003；3.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

0 引 言

近年來WIFI、4G、5G等無線通信技術(shù)得到了快速發(fā)展，智能手機(jī)、PDA等專業(yè)手持、車載設(shè)備也漸漸普及。與此同時(shí)，基于衛(wèi)星的無線定位系統(tǒng)也在迅速發(fā)展升級，如美國的GPS系統(tǒng)、歐洲的伽利略系統(tǒng)以及國內(nèi)自主設(shè)計(jì)的北斗系統(tǒng)等都在不斷提高著定位精度。移動通信的發(fā)展、智能終端的普及以及定位精度的提高使得一些與位置相關(guān)的服務(wù)成為可能[1]。

基于位置[2-3]的應(yīng)用都需要管理海量的移動對象位置信息，如何有效地對這些位置數(shù)據(jù)進(jìn)行管理成為急需解決的問題。傳統(tǒng)的外存索引無法處理如此海量的位置信息數(shù)據(jù)，是目前大多數(shù)移動對象索引結(jié)構(gòu)急需解決的理論技術(shù)難題。目前移動對象索引策略分為兩大類：一類是磁盤索引，一類是內(nèi)存索引。前者將索引存儲在磁盤上，無法支持頻繁、巨量的更新和查詢。后一種策略將索引放在內(nèi)存中，以加快處理速度，降低查詢響應(yīng)時(shí)間，但目前這種索引受到內(nèi)存容量的限制。

因此針對城市路網(wǎng)上移動對象在道路分布上的不均衡，設(shè)計(jì)了內(nèi)外存遷移的索引結(jié)構(gòu)(hot-spots dynamic migration index，HDMI)。該索引結(jié)構(gòu)根據(jù)道路車輛密度的動態(tài)變化自適應(yīng)地實(shí)現(xiàn)內(nèi)外存索引遷移，以適應(yīng)負(fù)載增長，降低索引維護(hù)代價(jià)。

1 相關(guān)工作

索引技術(shù)[4]能支持對移動對象數(shù)據(jù)的高效檢索和管理，通過多年的實(shí)驗(yàn)和研究，國內(nèi)外相關(guān)人員在移動對象索引結(jié)構(gòu)研究領(lǐng)域取得了一定成果。大致可以將移動對象索引分為兩類，一類是根據(jù)數(shù)據(jù)的對象分布對索引節(jié)點(diǎn)進(jìn)行劃分，以R-tree及其變體R*-tree、擴(kuò)展樹構(gòu)建的索引結(jié)構(gòu)為代表。MV3R-tree用R-tree及其變體來對歷史軌跡進(jìn)行索引。TPR-tree[5]可以索引移動對象的當(dāng)前和未來位置，其每個(gè)節(jié)點(diǎn)用一個(gè)時(shí)間相關(guān)的速度矢量對空間矩形進(jìn)行界定，如果移動對象長時(shí)間不運(yùn)動，則會降低索引很大的性能。REXP-tree[6]用來索引移動對象的現(xiàn)在和將來位置，其索引節(jié)點(diǎn)中明確標(biāo)識運(yùn)動矢量失效時(shí)間，失效后按照一定策略進(jìn)行刪除，保證索引的緊湊和有效。TPR-tree的變體還有TPR*-tree[7]、HTPR-tree[8]等，TPR*-tree采用了不同的索引節(jié)點(diǎn)維護(hù)算法，從而更為緊湊。另一類索引根據(jù)空間劃分對索引節(jié)點(diǎn)進(jìn)行組織，大多是以格柵及其變體為基礎(chǔ)構(gòu)建的索引結(jié)構(gòu)。ST2B-tree是一種格柵和B-tree相結(jié)合的索引結(jié)構(gòu)，它將空間中移動對象根據(jù)密度分布、采用不同粒度的格柵進(jìn)行管理，以適應(yīng)負(fù)載變化迅速的情況。DSTR-tree[9]是一種網(wǎng)絡(luò)受限移動對象的動態(tài)概略化軌跡索引。該索引結(jié)構(gòu)將索引空間劃分成等距格柵，通過格柵單元對每一條移動對象軌跡進(jìn)行概略化，由于概略化軌跡的粒度大大粗于原始軌跡，從而顯著地降低索引更新代價(jià)。以上索引結(jié)構(gòu)大多是在移動對象自由運(yùn)動的情況下構(gòu)建的，針對被限制在城市路網(wǎng)中的移動對象的研究則不多。

目前，國內(nèi)外研究學(xué)者提出了一些基于受限網(wǎng)絡(luò)的移動對象索引結(jié)構(gòu)，例如Frentzos等提出的雙層索引結(jié)構(gòu)FNR-tree[10]，其在一定程度上彌補(bǔ)了基于路網(wǎng)的移動對象索引技術(shù)的不足。FNR-tree的上層索引結(jié)構(gòu)2DR-tree用來索引路段信息，下層索引結(jié)構(gòu)1DR-tree用來管理移動對象的軌跡，2DR-tree中每個(gè)葉子節(jié)點(diǎn)都對應(yīng)著一個(gè)下層1DR-tree。但FNR-tree存在幾點(diǎn)不足：

(1)FNR-tree難以高效地支持移動對象歷史軌跡查詢和時(shí)間道路查詢。

(2)FNR-tree沿用了R-tree的自頂向下搜索策略，在精確查詢時(shí)，可能要從頂部同時(shí)向多個(gè)葉子方向遍歷，造成大量重復(fù)、冗余的查找路徑，降低了索引結(jié)構(gòu)的性能。

(3)FNR-tree將移動對象出現(xiàn)在路網(wǎng)每個(gè)位置的機(jī)率視為均等。但是現(xiàn)實(shí)路網(wǎng)中，不同道路的交通繁忙程度是不同的。

針對FNR-tree的不足，Almeida等提出了索引結(jié)構(gòu)MON-tree[11]，其對道路網(wǎng)絡(luò)的索引不再基于直線邊，而是基于折線道路，降低了移動對象跨越不同邊時(shí)的代價(jià)。MON-tree的缺陷在于對交通網(wǎng)絡(luò)的索引基于道路，會造成節(jié)點(diǎn)的重合。

NDTR-tree[12]是丁治明教授提出的基于路網(wǎng)的移動對象索引結(jié)構(gòu)，其為UTR-tree的改進(jìn)索引結(jié)構(gòu)[13]，是目前最具有代表性的路網(wǎng)移動對象索引結(jié)構(gòu)。NDTR-tree是雙層的R-tree索引結(jié)構(gòu)，上層索引為一個(gè)R-tree，對路網(wǎng)的原子路段建立索引；下層為一組獨(dú)立的R-tree，每個(gè)R-tree與一條道路相對應(yīng)，下層R-tree用于對在該條道路上提交的移動對象軌跡片段進(jìn)行索引。NDTR-tree存在如下不足：

(1)不支持對移動對象軌跡的高效查詢，因?yàn)樾枰闅v整個(gè)下層R-tree群，造成極大的開銷。

(2)索引維護(hù)的代價(jià)較高，每當(dāng)移動對象發(fā)生位置更新請求時(shí)，索引進(jìn)行一次維護(hù)，需要一次插入和刪除操作。

(3)在實(shí)際路網(wǎng)中，道路相交部分較多，采用結(jié)構(gòu)組織索引，由于算法在節(jié)點(diǎn)插入時(shí)只考慮邊際面積增加的情況，會產(chǎn)生很多索引空間的重疊，不利于查詢。

上述集中式磁盤時(shí)空索引[11]在移動對象數(shù)目巨大、更新頻繁的情況下難以保證查詢的實(shí)時(shí)響應(yīng)和精度；基于城市路網(wǎng)的移動對象索引技術(shù)大多沒有考慮移動對象在路網(wǎng)上分布不均衡的情況，當(dāng)路網(wǎng)道路中車輛變化差異很大時(shí)，很容易降低整個(gè)索引結(jié)構(gòu)的性能。

2 基于相對位置的移動對象模型

本節(jié)將介紹HDMI采用的城市路網(wǎng)和移動對象模型和主要概念，并給出形式化定義。

定義1：路網(wǎng)Network=(Edge,Node)，其中Edge為路段的集合，每一條路段對應(yīng)一條封閉的線段；Node為道路節(jié)點(diǎn)的集合，每個(gè)節(jié)點(diǎn)對應(yīng)地圖上的一個(gè)經(jīng)緯度(x,y)。

定義2：道路節(jié)點(diǎn)Node=(nodeId,x,y)，其中nodeId為道路節(jié)點(diǎn)的標(biāo)識，x和y為節(jié)點(diǎn)在地圖空間平面上的經(jīng)緯度。

定義3：道路Road=(roadId,Edge,Node,len)，其中roadId為該條道路的標(biāo)識，Edge為此道路中所有路段組成的集合，Node為此道路上所有節(jié)點(diǎn)組成的集合，len為此道路的長度。

定義4：路段Edge=(edgeId,roadId,nodes,nodee,len,weight,positionedge)，其中路段Edge就是從路段起點(diǎn)到終點(diǎn)不含有任何道路交點(diǎn)的道路片段，edgeId為該路段在道路中的標(biāo)識，roadId為該路段所在道路的標(biāo)識，nodes和nodee分別表示路段的起點(diǎn)和終點(diǎn)在二維空間的經(jīng)緯度，len為此路段的長度，weigth為該路段占其所屬道路的比例，計(jì)算方法為weigth=Edge.len/Road.len(Road為路段Edge所屬的道路)，positionedge(0～1)為該路段的起點(diǎn)在道路的相對位置。

文獻(xiàn)[14]提到的移動對象數(shù)據(jù)模型是文中移動對象模型的基礎(chǔ)，該模型將移動對象的位置更新信息(x,y,t)，通過式(1)轉(zhuǎn)化成可以用R-tree存儲的二維信息(position,t)。該模型通過將二維空間降低到一維空間來滿足構(gòu)建R-tree的條件，主要概念及形式化定義如下：

已知移動對象更新位置坐標(biāo)(x,y)到路段起點(diǎn)nodes的距離為s，該路段長度為len，那么position是移動對象當(dāng)前位置整條道路的比例，計(jì)算方法如下：

position=positions+weight×(s/len)

(1)

其中，positions為移動對象在道路中的初始位置；weight為所屬路段占其當(dāng)前道路的比例。

定義5：移動對象位置更新信息Move=(moveId,t,x,y)，其中moveId為移動對象的標(biāo)識，t為移動對象位置更新時(shí)刻，x和y為移動對象所處經(jīng)度和緯度。

定義6：移動對象運(yùn)行矢量Moving=(moveId,t,roadId,position)，其中moveId為移動對象的標(biāo)識，t為提交該運(yùn)行矢量的時(shí)刻，roadId為該移動對象所處道路的唯一標(biāo)識，position∈(0，1)是該移動對象所處道路的相對比例位置。roadId和position通過定義5中的Move和路段信息Edge計(jì)算得出。

定義7：移動對象鏈表軌跡單元MU=(U,uid)，多個(gè)連續(xù)的移動對象軌跡單元組成了移動對象軌跡。軌跡單元U是兩個(gè)運(yùn)行矢量之間的線段，U表示為U(Movings，Movinge)或者U(Movingn)，Movings和Movinge分別表示運(yùn)行矢量的起點(diǎn)和終點(diǎn)，活動運(yùn)行矢量用Movingn表示，其對應(yīng)一條射線，uid則用來記錄軌跡單元在下層R-tree中的位置。

3 HDMI的數(shù)據(jù)結(jié)構(gòu)

城市路網(wǎng)上的移動對象管理呈現(xiàn)三個(gè)特征：(1)移動對象在路網(wǎng)上分布不平衡，導(dǎo)致不同路段上移動對象位置更新和查詢覆蓋的不平衡；(2)隨著時(shí)間的變換，熱點(diǎn)區(qū)域也在不斷變化；(3)相比于規(guī)模不斷增長的移動對象，可用的計(jì)算機(jī)內(nèi)存總是有限的。基于這種認(rèn)識，文中提出了移動對象索引結(jié)構(gòu)HDMI，該結(jié)構(gòu)根據(jù)道路車輛密度的動態(tài)變化自適應(yīng)地實(shí)現(xiàn)內(nèi)外存索引遷移，大幅度降低I/O操作，提高查詢效率。

3.1 熱點(diǎn)區(qū)域

在實(shí)際路網(wǎng)中，不同道路上的移動對象分布的不均勻?qū)е孪鄳?yīng)道路上的位置更新頻率差異很大；針對不同道路軌跡的查詢頻率差異明顯。如果將這些被頻繁訪問的道路和移動對象存儲在內(nèi)存中，則能大幅度提升移動對象索引結(jié)構(gòu)的性能。正是基于此，HDMI索引結(jié)構(gòu)針對動態(tài)變化的熱點(diǎn)區(qū)域引入基于內(nèi)存的索引結(jié)構(gòu)，以減少索引結(jié)構(gòu)的磁盤訪問次數(shù)，最大限度地提升索引結(jié)構(gòu)的性能。

定義8：假設(shè)一條道路的長度為Road.len，該條道路上的車輛數(shù)量為Num，如果道路內(nèi)車輛的密度(單位道路內(nèi)的車輛數(shù))超過閾值，則該路段為熱點(diǎn)道路，熱點(diǎn)道路組成的區(qū)域稱為熱點(diǎn)區(qū)域。

(2)

隨著移動對象在路網(wǎng)分布的不斷變化，組成熱點(diǎn)區(qū)域的熱點(diǎn)道路也在動態(tài)變化，內(nèi)外存索引根據(jù)熱點(diǎn)區(qū)域的變化進(jìn)行遷移更新，保證新增的熱點(diǎn)區(qū)域和移動對象能被內(nèi)存索引管理，將由于車輛密度降低導(dǎo)致變?yōu)榉菬狳c(diǎn)的區(qū)域和移動對象遷移到外存，以此來保證繁忙道路索引常駐系統(tǒng)內(nèi)存中，以響應(yīng)該區(qū)域內(nèi)頻繁的移動對象位置更新。

3.2 上層城市路網(wǎng)索引

HDMI的上層索引結(jié)構(gòu)是針對城市路網(wǎng)構(gòu)建的R*-tree索引，用于索引城市路網(wǎng)中的路段，針對熱點(diǎn)區(qū)域構(gòu)建基于內(nèi)存的R*-tree索引，非熱點(diǎn)區(qū)域構(gòu)建磁盤R*-tree索引文件放入基于外存的磁盤文件。其葉子節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為(MBR,nodeId,Edge)，其中MBR表示包含該路段的最小邊界矩形，nodeId為該葉子節(jié)點(diǎn)在索引中的標(biāo)識，Edge為該路段信息；中間節(jié)點(diǎn)為(MBR’,nodeId’,tree)，其中MBR’表示包含下層節(jié)點(diǎn)的MBR，tree表示指向下層節(jié)點(diǎn)的指針，nodeId’表示該中間節(jié)點(diǎn)在索引中的標(biāo)識。最小矩形框包含著城市路網(wǎng)的每個(gè)路段，所有最小邊界矩形一步一步迭代后，形成最大的MBR，最終城市路網(wǎng)被兩個(gè)最大的MBR包含，分別包含熱點(diǎn)區(qū)域和非熱點(diǎn)區(qū)域。

3.3 下層移動對象軌跡索引

HDMI下層索引是對應(yīng)于道路的R-tree索引群，熱點(diǎn)區(qū)域的道路對應(yīng)內(nèi)存R-tree群，非熱點(diǎn)區(qū)域道路對應(yīng)外存R-tree群，它們基于位置和時(shí)間(position×t)平面。通過下層索引管理移動對象軌跡單元，動態(tài)地維護(hù)移動對象位置更新信息。下層葉子節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為(MBR,id,Movingstart,Movingend,moveId)，其中MBR為包含該軌跡的最小邊界矩形，Movingstart表示軌跡單元的開始運(yùn)行矢量，Movingend表示軌跡單元的結(jié)束運(yùn)行矢量，若為活動軌跡單元，則Movingend為空，id表示該葉子節(jié)點(diǎn)在索引中的標(biāo)識，moveId表示移動對象的唯一標(biāo)識。

中間節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為(MBR’,id’,tree)，其中MBR’為包含下層節(jié)點(diǎn)的MBR，id’表示中間節(jié)點(diǎn)在索引中的標(biāo)識，tree指向下層節(jié)點(diǎn)。下層結(jié)構(gòu)如圖1所示，下層R-tree群管理基于position-t平面的移動對象軌跡片段，例如移動對象Move1只在道路Road1上運(yùn)動，那么它的所有軌跡單元被道路Road1的R-tree1(MBR1)管理。圖中的方框表示移動對象Move2的活動軌跡單元，其從道路Road2運(yùn)動到道路Road1，那么它的軌跡單元將被兩個(gè)道路樹R-tree1(MBR1)和R-tree2(MBR2)管理。

圖1 HDMI下層索引結(jié)構(gòu)以及移動對象軌跡

HDMI上下層索引之間的R-tree的數(shù)量關(guān)系是2:n，2代表上層索引由2個(gè)R*-tree索引構(gòu)成，n代表下層索引由對應(yīng)n條道路的R-tree群構(gòu)成。每個(gè)上層索引葉子節(jié)點(diǎn)都指向下層索引群中的某個(gè)樹，當(dāng)然不同葉子節(jié)點(diǎn)也可能指向同一條道路。比如新模范馬路包含四個(gè)路段，則上層葉子節(jié)點(diǎn)中有四個(gè)記錄均指向下層索引中屬于新模范馬路的R-tree(記錄中Edge信息指向下層道路索引)。

4 基于HDMI索引結(jié)構(gòu)的操作算法

4.1 上層索引結(jié)構(gòu)的更新算法

算法1：HDMI上層索引的更新算法。

輸入：批量更新的移動對象更新信息Movei=1n；

輸出：自適應(yīng)的上層路網(wǎng)索引。

1 memoryRoad←the Road in the memory

2 for each Movei=1n=(moveId,t,x,y)

3 (roadId,Num++)←search the roadId of moveifrom the R*-tree;

4 end

5 foreach Roadi= (roadId,Edge,Node,len,Num)

7 if(density≥P) then

8 if(roadId not in the memoryRoad) then

9 insert theRoadiinto memoryR*-tree;

10 insert theroadId into ArraySet memoryRoad;

11 else

12 if(roadId in the memoryRoad) then

13 insert theRoadiinto diskR*-tree;

14 remove theroadId from the memoryRoad;

15 end

算法1的主要步驟如下：

(1)根據(jù)每個(gè)移動對象位置更新信息查詢上層R*-tree索引，計(jì)算每條道路中移動對象的個(gè)數(shù)(第2～4行),計(jì)算每條道路的車輛密度(第6行)；

(2)道路車輛密度大于等于閾值P，并且該道路不在內(nèi)存中，則將該道路更新到內(nèi)存索引中，并將這條道路的roadId插入到存儲熱點(diǎn)道路的數(shù)組memoryRoad中(第8～10行)；

(3)道路車輛密度小于規(guī)定的閾值P并且該道路在內(nèi)存中，則將該道路更新到外存索引，并將這條道路的roadId從存儲熱點(diǎn)道路的數(shù)組memoryRoad移除(第12～14行)。

時(shí)間復(fù)雜度參數(shù)設(shè)置：該上層R*-tree索引有N個(gè)索引記錄，M為R*-tree一個(gè)節(jié)點(diǎn)中的最大條目數(shù)，熱點(diǎn)區(qū)域與整個(gè)地圖的比例是1：λ，λ∈1+∞根據(jù)車輛密度動態(tài)變化。算法1中HDMI上層路網(wǎng)索引的更新需要內(nèi)外存索引的遷移來完成，有p條熱點(diǎn)道路由于移動對象密度的變化變成非熱點(diǎn)道路，該過程的時(shí)間復(fù)雜度為O(p×logMλ-1N/λ)。

4.2 下層R-tree群索引的建立和維護(hù)算法

下層動態(tài)索引的建立和維護(hù)的整個(gè)過程如算法2所示，其主要步驟為：

(1)根據(jù)移動對象位置更新信息Move查找上層索引，確定移動對象所在道路roadId和相對位置position(第2行)。

(2)根據(jù)roadId和position生成移動對象運(yùn)行矢量Moving(moveId,t,roadId,position)(第3行)。

(3)下層索引是基于position×t平面的R-tree(第4行)，完成了下層R-tree索引構(gòu)建所需的數(shù)據(jù)結(jié)構(gòu)rectangle(position1,position2,t1,t2)，運(yùn)用基于x×y平面構(gòu)建的R-tree的思想對其進(jìn)行重構(gòu)。通過searchRoadHash()查詢到道路roadId所對應(yīng)的R-tree。

(4)通過TrajectoryMap表查詢moveId所對應(yīng)的雙向鏈表MU(第5行)；由Moving和uid生成新的移動軌跡單元MUnew(第6行)，并將新生成的軌跡單元插入到searchTrajectoryMap中(第7行)。

(5)如果鏈表為空，并且移動對象所處道路為熱點(diǎn)區(qū)域道路，將Moving插入到熱點(diǎn)區(qū)域道路對應(yīng)的道路的內(nèi)存R-tree中(第9～10行)；如果移動對象所處道路為非熱點(diǎn)區(qū)域道路，將Moving插入到非熱點(diǎn)區(qū)域道路對應(yīng)的道路的外存R-tree中(第12行)。

(6)如果鏈表不為空，刪除該移動對象上一時(shí)刻在R-tree對應(yīng)的數(shù)據(jù)(第14～15行)，并根據(jù)移動對象是否處在熱點(diǎn)區(qū)域分別插入到內(nèi)外存R-tree索引中(第16～20行)。

算法2：HDMI下層索引的建立和維護(hù)算法。

輸入：批量更新的移動對象更新信息Movei=1n，熱點(diǎn)區(qū)域道路表memoryRoad；

輸出：更新后的HDMI。

1 foreach Movei=1n=(moveId,t,x,y)

2 (roadId,position)←traverse the upper R*-tree to find the roadId and position;

3 Moving←(roadId,x,y,t,position);

4 Rtree←searchRoadHash(roadId);

5 MU←searchTrajectoryMap(moveId);

6 MUnew←(Moving,Rtree.uid);

7 insert the MUnewinto the TrajectoryMap;

8 if(MU==null) then

9 if(roadId in the memoryRoad) then

10 insert the Moving intomemory_RoadId_R-tree;

11 else

12 insert the Moving into disk_RoadId_R-tree;

13 else

14 U(Movingn,uid)←MU.last, last_R-tree←search(uid);

15 delete U(Movingn) from last_R-tree;

16 if(roadId in the memoryRoad) then

17 insert the Moving intomemory_RoadId_R-tree;

18 else

19 insert the Moving intodisk_RoadId_R-tree;

20 end

HDMI下層R-tree索引有N個(gè)索引記錄，M為R-tree一個(gè)節(jié)點(diǎn)中的最大條目數(shù)。有n個(gè)移動對象進(jìn)行位置更新，其中有m個(gè)位于熱點(diǎn)區(qū)域的道路，由于熱點(diǎn)道路中移動對象的更新在內(nèi)存完成，不考慮更新代價(jià)，所以算法2的時(shí)間復(fù)雜度為O(n-m×logMN)。

4.3 時(shí)空窗口查詢

時(shí)空窗口查詢是指查詢一段時(shí)間(t1,t2)內(nèi)經(jīng)過地圖上指定二維空間(x1,x2,y1,y2)的移動對象，時(shí)空窗口查詢也表示為(△x,△y,△t)的形式。如查詢2008-02-02 15:15:04到2008-02-02 17:40:02間，經(jīng)過南京市三牌樓區(qū)域的車輛。具體查詢過程為:

(2)遍歷每個(gè)交點(diǎn)(Edgei,xi,yi)，計(jì)算交點(diǎn)在道路的唯一標(biāo)識roadIdi和相對位置position(第3行)；

(3)針對每個(gè)(roadIdi,positioni)，根據(jù)Road_Hash表定位下層所對應(yīng)的內(nèi)外存R-tree(第4行)；

(4)求出(position,△t)范圍內(nèi)移動對象節(jié)點(diǎn)MUi(第5行)，遍歷MUi得到其中的moveId(第6～9行)。

算法3：時(shí)空窗口查詢。

輸入：查詢區(qū)域，時(shí)間范圍(t1,t2)，道路索引Road_Hash；

輸出：移動對象標(biāo)識集合result。

3 roadIdi,positioni←根據(jù)(Edgei,xi,yi)求得交點(diǎn)的位置和道路標(biāo)識;

4 roadR-tree←searchRoadHash(roadIdi);

5 MUi←查詢r(jià)oadR-tree中(positioni,△t)的節(jié)點(diǎn);

7 moveId←從MU取得移動對象的標(biāo)識；

8 result←添加moveId到結(jié)果集;

9 end

10 end

通過上層R*-tree索引查詢到區(qū)域與路段有n個(gè)交點(diǎn)，其中有m個(gè)位于熱點(diǎn)道路，相關(guān)該階段的時(shí)間復(fù)雜度為O(n×logMλ-1N/λ)，參數(shù)請參照算法1；通過下層R-tree群索引查詢到符合條件移動對象，該階段的時(shí)間復(fù)雜度為O((n-m)×logMN)，所以算法2的時(shí)間復(fù)雜度分析為O((n-m)×logMλ-1N/λ+(n-m)logMN)。

5 實(shí)驗(yàn)與性能分析

5.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用的城市路網(wǎng)數(shù)據(jù)集是從網(wǎng)站http://www.openstreetmap.org/下載的北京真實(shí)OpenStreetMap(OSM)地圖，如表1所示，其中包含北京城區(qū)內(nèi)57 036條道路和317 551個(gè)交點(diǎn)。

表1 北京城市路網(wǎng)數(shù)據(jù)

移動對象數(shù)據(jù)集是北京市2008-02-02 12:00:00到2008-02-08 19:00:00時(shí)間段內(nèi)10 000臺出租車行駛軌跡。在這個(gè)數(shù)據(jù)集中一共有15 000 000個(gè)點(diǎn)，軌跡行駛的距離有9 000 000 km。

5.2 索引建立和維護(hù)代價(jià)比較分析

索引建立和維護(hù)時(shí)的I/O代價(jià)是評判一個(gè)索引結(jié)構(gòu)性能的重要指標(biāo)，所以分別計(jì)算在1 000、2 000、3 000、5 000和10 000個(gè)北京出租車數(shù)量的情況下NDTR-tree和HDMI建立和維護(hù)索引過程中I/O的次數(shù)，結(jié)果如圖2所示。

圖2 I/O次數(shù)比較

從圖2可以看到，隨著移動對象數(shù)量的不斷遞增，NDTR-tree磁盤節(jié)點(diǎn)的存取I/O次數(shù)迅速增加，HDMI索引結(jié)構(gòu)隨著移動對象數(shù)據(jù)的增加磁盤節(jié)點(diǎn)存取次數(shù)變化相對平穩(wěn)，所以HDMI索引的更新性能優(yōu)于NDTR-tree。

以下三個(gè)方面導(dǎo)致HDMI索引與NDTR-tree更新性能存在如此大的差異：

(1)針對熱點(diǎn)區(qū)域行駛的移動對象，NDTR-tree每次更新都要訪問磁盤的路網(wǎng)R*-tree和移動對象R-tree，這就會引起很高的索引更新I/O，同時(shí)導(dǎo)致查詢響應(yīng)速度緩慢，影響了系統(tǒng)的整體性能。而HDMI將熱點(diǎn)區(qū)域的R*-tree放入內(nèi)存，在更新和查詢時(shí)可以直接從內(nèi)存中取得，可以快速響應(yīng)該區(qū)域車輛的更新操作，很好解決了大批量移動對象在繁忙道路定位的瓶頸，減少了大量的I/O操作。

(2)隨著移動對象的逐漸增加，NDTR-tree的下層移動對象索引結(jié)構(gòu)效率會迅速降低。因?yàn)?，其下層R-tree針對每個(gè)移動對象的位置更新都需要進(jìn)行索引的更新，同時(shí)很多長時(shí)間不運(yùn)動的移動對象占據(jù)了索引數(shù)據(jù)項(xiàng)。而HDMI采用了哈希表和雙向鏈表保存移動對象軌跡信息，當(dāng)需要跟蹤移動對象時(shí)僅需遍歷鏈表尾節(jié)點(diǎn)來獲取其歷史軌跡信息，不用再遍歷該移動對象所在的R-tree，提高了查詢效率，減少了I/O開銷。

(3)HDMI將需要插入、更新和刪除的移動對象保存在緩沖區(qū)中，當(dāng)緩沖區(qū)中移動對象數(shù)目超過規(guī)定閾值時(shí)或按照一定的時(shí)間間隔，將緩沖區(qū)中的移動對象批量更新到索引結(jié)構(gòu)中，減少了索引結(jié)構(gòu)頻繁的I/O操作。

5.3 時(shí)空窗口查詢性能分析

(1)熱點(diǎn)區(qū)域變化。

在移動對象數(shù)量分別為1 000、2 000、3 000、5 000、10 000，占據(jù)地圖15%查詢窗口的情況下并且分別以地圖的5%、10%、15%、20%作為熱點(diǎn)區(qū)域進(jìn)行范圍查詢實(shí)驗(yàn)，對比查詢時(shí)所耗費(fèi)時(shí)間。當(dāng)索引結(jié)構(gòu)HDMI自適應(yīng)到熱點(diǎn)區(qū)域占路網(wǎng)5%、10%、15%、20%的時(shí)候，暫停索引的更新，同時(shí)保證查詢窗口經(jīng)過熱點(diǎn)區(qū)域。圖3為HDMI索引結(jié)構(gòu)的時(shí)空范圍查詢基于不同的熱點(diǎn)區(qū)域時(shí)間開銷。

圖3 時(shí)空窗口查詢

兩次實(shí)驗(yàn)證明HDMI索引的窗口查詢性能在引入熱點(diǎn)區(qū)域后得到了很大提升，不過受熱點(diǎn)區(qū)域的影響較大，熱點(diǎn)區(qū)域越大查詢性能越高，因?yàn)闊狳c(diǎn)區(qū)域索引結(jié)構(gòu)是內(nèi)存索引，比外存索引查詢速度快很多。但熱點(diǎn)區(qū)域太大會占用大量內(nèi)存，并且內(nèi)外存索引遷移更新時(shí)有一定的代價(jià)，所以選擇合適范圍的熱點(diǎn)區(qū)域?qū)τ谙到y(tǒng)的整體性能至關(guān)重要。

(2)查詢窗口變化。

在移動對象數(shù)量分別為1 000、2 000、3 000、5 000、10 000并且分別以地圖的10%、15%、20%、30%的面積作為查詢窗口進(jìn)行范圍查詢實(shí)驗(yàn)，對比查詢時(shí)所耗費(fèi)時(shí)間。當(dāng)索引結(jié)構(gòu)HDMI自適應(yīng)到熱點(diǎn)區(qū)域占路網(wǎng)10%的時(shí)候，暫停索引的更新，同時(shí)根據(jù)熱點(diǎn)區(qū)域的范圍保證查詢窗口經(jīng)過熱點(diǎn)區(qū)域。圖4顯示了NDTR-tree、HDMI索引結(jié)構(gòu)基于不同的查詢窗口的時(shí)空窗口查詢的時(shí)間開銷代價(jià)。

從圖4中可以看出，NDTR-tree和HDMI的窗口查詢性能基本不受移動對象數(shù)量的影響，主要還是取決于上層路網(wǎng)索引結(jié)構(gòu)。R*-tree的覆蓋度和重疊度較低，所以查詢效率相比R-tree高。由于HDMI采用了R*-tree作為上層路網(wǎng)索引結(jié)構(gòu)，而NDTR-tree的上層路網(wǎng)索引釆用傳統(tǒng)的R-tree，因此HDMI在窗口査詢性能方面比NDTR-tree高出許多。

圖4 時(shí)空窗口查詢

6 結(jié)束語

針對NDTR-tree等索引結(jié)構(gòu)在索引維護(hù)和軌跡查詢方面的不足，提出了一種城市路網(wǎng)上動態(tài)遷移的索引結(jié)構(gòu)HDMI。內(nèi)存索引管理熱點(diǎn)區(qū)域及其中的移動對象，非熱點(diǎn)區(qū)域及其中的移動對象則由外存索引管理，內(nèi)外存索引根據(jù)熱點(diǎn)區(qū)域的變化進(jìn)行遷移更新，實(shí)現(xiàn)了快速查詢。同時(shí)，HDMI實(shí)現(xiàn)了基于緩存的更新，減少了系統(tǒng)I/O訪問次數(shù)和時(shí)間。實(shí)驗(yàn)結(jié)果證明HDMI在索引維護(hù)和查詢性能上優(yōu)于NDTR-tree，但HDMI只能索引城市路網(wǎng)上移動對象的歷史和當(dāng)前軌跡，對未來軌跡的索引將是今后研究的重點(diǎn)。

[1] 丁治明,孟小峰,白 蕓,等.基于關(guān)系數(shù)據(jù)庫的位置相關(guān)查詢處理[J].計(jì)算機(jī)研究與發(fā)展,2004,41(3):492-499.

[2] 孟小峰,丁治明.移動數(shù)據(jù)管理:概念與技術(shù)[M].北京:清華大學(xué)出版社,2009.

[3] GUTING R H,BOHLEN M H,ERWIG M,et al.A foundation for representing and querying moving objects[J].ACM Transactions on Database Systems,2000,25(1):1-42.

[4] WOLFSON O,XU B,CHAMBERLAIN S,et al.Moving object databases:issues and solutions[C]//Proceedings of the 10th SSDBM.[s.l.]:[s.n.],1998:111-122.

[5] SALTENIS S,JENSEN C S,LEUTENEGGER S T,et al.Indexing the positions of continuously moving objects[C]//Proceedings of the ACM SIGMOD international conference on management of data.New York,NY,USA:ACM,2000:331-342.

[6] SALTENIS S,JENSEN C S.Indexing of moving object s for location-based services[C]//Proceedings of the 18th ICDE.[s.l.]:[s.n.],2002:463-472.

[7] TAO Y,PAPSDIAS D,SUN J.The TPR-tree:an optimized spatio-temporal access method for predictive queries[C]//Proceedings of the 29th international conference on very large data bases.Berlin,Germany:VLDB Endowment,2003:790-801.

[8] TUNG H D T,JUNG Y J,LEE E J,et al.Moving point indexing for future location query[C]//Proceedings of the ER workshops.[s.l.]:[s.n.],2004:79-90.

[9] 丁治明.一種適合于頻繁位置更新的網(wǎng)絡(luò)受限移動對象軌跡索引[J].計(jì)算機(jī)學(xué)報(bào),2012,35(7):1448-1461.

[10] FRENTOS E.Indexing objects moving on fixed networks[C]//Proceedings of the international symposium on advances in spatial and temporal databases.[s.l.]:[s.n.],2003:289-305.

[11] ALMEIDA V T,GüTING R H.Indexing the trajectories of moving objects in networks[J].GeoInformatica,2005,9(1):33-60.

[12] 丁治明,李肖南,余 波.網(wǎng)絡(luò)受限移動對象過去、現(xiàn)在及將來位置的索引[J].軟件學(xué)報(bào),2009,20(12):3193-3204.

[13] 丁治明,余 波,李 曼,等.網(wǎng)絡(luò)受限移動對象不確定性軌跡的索引[J].計(jì)算機(jī)科學(xué),2008,35(3):79-83.

[14] 喬少杰,韓 楠,王 超,等.基于路網(wǎng)的移動對象動態(tài)雙層索引結(jié)構(gòu)[J].計(jì)算機(jī)學(xué)報(bào),2014,37(9):1947-1958.