城市路网上动态迁移的移动对象索引结构

张郁彬，张深深，孟旭东

(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.