城市路網上動態遷移的移動對象索引結構

張郁彬，張深深，孟旭東

(1.寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003；2.南京郵電大學 江蘇省電信網絡融合實驗室，江蘇 南京 210003；3.南京郵電大學 計算機學院，江蘇 南京 210003)

0 引 言

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

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

因此針對城市路網上移動對象在道路分布上的不均衡，設計了內外存遷移的索引結構(hot-spots dynamic migration index，HDMI)。該索引結構根據道路車輛密度的動態變化自適應地實現內外存索引遷移，以適應負載增長，降低索引維護代價。

1 相關工作

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

目前，國內外研究學者提出了一些基于受限網絡的移動對象索引結構，例如Frentzos等提出的雙層索引結構FNR-tree[10]，其在一定程度上彌補了基于路網的移動對象索引技術的不足。FNR-tree的上層索引結構2DR-tree用來索引路段信息，下層索引結構1DR-tree用來管理移動對象的軌跡，2DR-tree中每個葉子節點都對應著一個下層1DR-tree。但FNR-tree存在幾點不足：

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

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

(3)FNR-tree將移動對象出現在路網每個位置的機率視為均等。但是現實路網中，不同道路的交通繁忙程度是不同的。

針對FNR-tree的不足，Almeida等提出了索引結構MON-tree[11]，其對道路網絡的索引不再基于直線邊，而是基于折線道路，降低了移動對象跨越不同邊時的代價。MON-tree的缺陷在于對交通網絡的索引基于道路，會造成節點的重合。

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

(1)不支持對移動對象軌跡的高效查詢，因為需要遍歷整個下層R-tree群，造成極大的開銷。

(2)索引維護的代價較高，每當移動對象發生位置更新請求時，索引進行一次維護，需要一次插入和刪除操作。

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

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

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

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

定義1：路網Network=(Edge,Node)，其中Edge為路段的集合，每一條路段對應一條封閉的線段；Node為道路節點的集合，每個節點對應地圖上的一個經緯度(x,y)。

定義2：道路節點Node=(nodeId,x,y)，其中nodeId為道路節點的標識，x和y為節點在地圖空間平面上的經緯度。

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

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

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

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

position=positions+weight×(s/len)

(1)

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

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

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

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

3 HDMI的數據結構

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

3.1 熱點區域

在實際路網中，不同道路上的移動對象分布的不均勻導致相應道路上的位置更新頻率差異很大；針對不同道路軌跡的查詢頻率差異明顯。如果將這些被頻繁訪問的道路和移動對象存儲在內存中，則能大幅度提升移動對象索引結構的性能。正是基于此，HDMI索引結構針對動態變化的熱點區域引入基于內存的索引結構，以減少索引結構的磁盤訪問次數，最大限度地提升索引結構的性能。

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

(2)

隨著移動對象在路網分布的不斷變化，組成熱點區域的熱點道路也在動態變化，內外存索引根據熱點區域的變化進行遷移更新，保證新增的熱點區域和移動對象能被內存索引管理，將由于車輛密度降低導致變為非熱點的區域和移動對象遷移到外存，以此來保證繁忙道路索引常駐系統內存中，以響應該區域內頻繁的移動對象位置更新。

3.2 上層城市路網索引

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

3.3 下層移動對象軌跡索引

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

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

圖1 HDMI下層索引結構以及移動對象軌跡

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

4 基于HDMI索引結構的操作算法

4.1 上層索引結構的更新算法

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

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

輸出：自適應的上層路網索引。

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)根據每個移動對象位置更新信息查詢上層R*-tree索引，計算每條道路中移動對象的個數(第2～4行),計算每條道路的車輛密度(第6行)；

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

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

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

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

下層動態索引的建立和維護的整個過程如算法2所示，其主要步驟為：

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

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

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

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

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

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

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

輸入：批量更新的移動對象更新信息Movei=1n，熱點區域道路表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個索引記錄，M為R-tree一個節點中的最大條目數。有n個移動對象進行位置更新，其中有m個位于熱點區域的道路，由于熱點道路中移動對象的更新在內存完成，不考慮更新代價，所以算法2的時間復雜度為O(n-m×logMN)。

4.3 時空窗口查詢

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

(2)遍歷每個交點(Edgei,xi,yi)，計算交點在道路的唯一標識roadIdi和相對位置position(第3行)；

(3)針對每個(roadIdi,positioni)，根據Road_Hash表定位下層所對應的內外存R-tree(第4行)；

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

算法3：時空窗口查詢。

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

輸出：移動對象標識集合result。

3 roadIdi,positioni←根據(Edgei,xi,yi)求得交點的位置和道路標識;

4 roadR-tree←searchRoadHash(roadIdi);

5 MUi←查詢roadR-tree中(positioni,△t)的節點;

7 moveId←從MU取得移動對象的標識；

8 result←添加moveId到結果集;

9 end

10 end

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

5 實驗與性能分析

5.1 實驗數據集

實驗采用的城市路網數據集是從網站http://www.openstreetmap.org/下載的北京真實OpenStreetMap(OSM)地圖，如表1所示，其中包含北京城區內57 036條道路和317 551個交點。

表1 北京城市路網數據

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

5.2 索引建立和維護代價比較分析

索引建立和維護時的I/O代價是評判一個索引結構性能的重要指標，所以分別計算在1 000、2 000、3 000、5 000和10 000個北京出租車數量的情況下NDTR-tree和HDMI建立和維護索引過程中I/O的次數，結果如圖2所示。

圖2 I/O次數比較

從圖2可以看到，隨著移動對象數量的不斷遞增，NDTR-tree磁盤節點的存取I/O次數迅速增加，HDMI索引結構隨著移動對象數據的增加磁盤節點存取次數變化相對平穩，所以HDMI索引的更新性能優于NDTR-tree。

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

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

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

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

5.3 時空窗口查詢性能分析

(1)熱點區域變化。

在移動對象數量分別為1 000、2 000、3 000、5 000、10 000，占據地圖15%查詢窗口的情況下并且分別以地圖的5%、10%、15%、20%作為熱點區域進行范圍查詢實驗，對比查詢時所耗費時間。當索引結構HDMI自適應到熱點區域占路網5%、10%、15%、20%的時候，暫停索引的更新，同時保證查詢窗口經過熱點區域。圖3為HDMI索引結構的時空范圍查詢基于不同的熱點區域時間開銷。

圖3 時空窗口查詢

兩次實驗證明HDMI索引的窗口查詢性能在引入熱點區域后得到了很大提升，不過受熱點區域的影響較大，熱點區域越大查詢性能越高，因為熱點區域索引結構是內存索引，比外存索引查詢速度快很多。但熱點區域太大會占用大量內存，并且內外存索引遷移更新時有一定的代價，所以選擇合適范圍的熱點區域對于系統的整體性能至關重要。

(2)查詢窗口變化。

在移動對象數量分別為1 000、2 000、3 000、5 000、10 000并且分別以地圖的10%、15%、20%、30%的面積作為查詢窗口進行范圍查詢實驗，對比查詢時所耗費時間。當索引結構HDMI自適應到熱點區域占路網10%的時候，暫停索引的更新，同時根據熱點區域的范圍保證查詢窗口經過熱點區域。圖4顯示了NDTR-tree、HDMI索引結構基于不同的查詢窗口的時空窗口查詢的時間開銷代價。

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

圖4 時空窗口查詢

6 結束語

針對NDTR-tree等索引結構在索引維護和軌跡查詢方面的不足，提出了一種城市路網上動態遷移的索引結構HDMI。內存索引管理熱點區域及其中的移動對象，非熱點區域及其中的移動對象則由外存索引管理，內外存索引根據熱點區域的變化進行遷移更新，實現了快速查詢。同時，HDMI實現了基于緩存的更新，減少了系統I/O訪問次數和時間。實驗結果證明HDMI在索引維護和查詢性能上優于NDTR-tree，但HDMI只能索引城市路網上移動對象的歷史和當前軌跡，對未來軌跡的索引將是今后研究的重點。

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

[2] 孟小峰,丁治明.移動數據管理:概念與技術[M].北京:清華大學出版社,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] 丁治明.一種適合于頻繁位置更新的網絡受限移動對象軌跡索引[J].計算機學報,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] 丁治明,李肖南,余 波.網絡受限移動對象過去、現在及將來位置的索引[J].軟件學報,2009,20(12):3193-3204.

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

[14] 喬少杰,韓 楠,王 超,等.基于路網的移動對象動態雙層索引結構[J].計算機學報,2014,37(9):1947-1958.