EN中文

地球信息科学学报 >

2017 , Vol. 19 >Issue 2: 152 - 160

DOI: https://doi.org/10.3724/SP.J.1047.2017.00152

地球信息科学理论与方法

支持频繁位置更新的移动对象索引方法

  • 彭召军 , 1, * ,
  • 封俊翔 2 ,
  • 王青山 1 ,
  • 熊伟 1
展开
  • 1. 信息工程大学,郑州 450001
  • 2. 95956部队,西安 710061

作者简介：彭召军（1992-）,男,硕士生,研究方向为地理空间数据库索引技术和时空数据库索引技术。E-mail:

收稿日期: 2016-07-12

  要求修回日期: 2016-10-23

  网络出版日期: 2017-02-17

基金资助

国家自然科学基金项目（41501507）

收起

A Moving Object Indexing Method that Supports Frequent Location Updating

  • PENG Zhaojun , 1, * ,
  • FENG Junxiang 2 ,
  • WANG Qingshan 1 ,
  • XIONG Wei 1
Expand
  • 1. Information Engineering University, Zhengzhou 450001, China
  • 2. 95956 Troops, Xi'an 100042, China
*Corresponding author: PENG Zhanjun, E-mail:

Received date: 2016-07-12

  Request revised date: 2016-10-23

  Online published: 2017-02-17

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

传统R-tree及其变种难以满足移动对象频繁更新位置的需求。本文通过在R*-tree中引入多种移动对象索引策略,提出一种基于延迟更新和备忘录更新/插入相结合的移动对象索引结构LUMR*-tree（Lazy Update Memo R*-tree）。利用延迟更新策略,LUMR*-tree能够在几乎不改变索引结构的前提下快速完成更新操作;通过引入更新备忘录（Update Memo, UM）,LUMR*-tree将复杂的更新操作简化为插入操作,避免了从索引树中频繁删除旧记录的过程;借助垃圾清理器定期清理索引树和UM中的旧记录,动态维护UM中的数据项和内存大小,保证了LUMR*-tree的稳定性和高效性。实验结果表明,LUMR*-tree通过牺牲少量查询性能获得了优良的更新性能,能够满足移动对象频繁位置更新的需求,具有较好的实用价值和广泛的应用前景。

关键词： 移动对象; R*-树; 延迟更新; LUMR*-tree; UM

本文引用格式

彭召军 , 封俊翔 , 王青山 , 熊伟 . 支持频繁位置更新的移动对象索引方法[J]. 地球信息科学学报, 2017 , 19(2) : 152 -160 . DOI: 10.3724/SP.J.1047.2017.00152

Abstract

Traditional R-tree and its variants cannot support frequent location updating of moving objects. By introducing a variety of moving object indexing strategies in R*-tree, we proposed a moving object index structure-LUMR*-tree (Lazy Update Memo R*-tree), which combines lazy update and memo update/insert strategy. The LUMR*-tree can quickly complete update without changing its structure by lazy update strategy. It can also simplify an update operation to an insert operation with the Update Memo (UM), which can avoid frequently purging old entries from the index tree effectively. The removal of old entries is implemented by a garbage cleaner inside the LUMR*-tree. Thus, data items and memory size of UM are maintained dynamically, which ensures high stability and efficiency of the LUMR*-tree. Experimental results show that, the LUMR*-tree achieved significantly higher update performance at the cost of slightly poorer query performance, it can support frequent location updating of moving objects. To sum up, the LUMR*-tree has good practical values and wide application prospects.

Key words： Moving Object; R*-tree; Lazy Update; LUMR*-tree; UM

1 引言

随着无线通信、GPS以及北斗等空间定位技术的迅速发展和应用,在车辆导航、军事监控及位置服务等领域需要对移动终端的实时位置信息进行监控与管理[1]。传统的空间数据索引技术[2]主要用于快速检索静态的对象,索引结构中存储的是空间对象的精确位置。当空间对象的位置不断发生变化时,索引结构需要动态调整。对于移动对象[3]索引而言,不仅要考虑查询效率,还必须重点考虑更新代价问题,有效提升索引的更新性能[4]。
R-树[5]是一类常用的多路查找树,具有自动平衡、空间利用率较高、便于外存存储等优点[6],被广泛应用于大型数据库系统[7]中。然而,随着移动对象的位置不断发生变化,R-树中存储的数据需要不断更新,这将导致索引结构急剧恶化,索引的整体性能急剧降低。针对此问题,国内外的众多专家学者进行了深入研究,提出了一系列支持频繁位置更新的移动对象索引策略。文献[8]针对R-树中自顶向下（Top-Down）的更新方式需要遍历更多节点而导致更新效率低的问题,提出一种自底向上（Bottom-Up）的更新策略,通过牺牲少量查询性能获取更高的更新性能。文献[9]综合考虑索引的查询和更新效率,提出了一种容忍大批量更新的移动对象索引CTR-tree。文献[10]提出的RUM-tree使用基于备忘录更新的方式将更新操作转化为简单的插入操作,有效提高了索引的更新效率。
本文在R*-tree[11]的基础上,引入多种支持频繁更新位置的移动对象索引方法和策略[12],提出一种基于延迟更新和备忘录更新/插入相结合的移动对象索引结构LUMR*-tree。在R*-tree中,增加记录移动对象状态特征的UM[13]辅助内存结构,通过有效扩展中间节点MBR以及自顶向下和自底向上相结合的策略共同完成移动对象的位置更新,同时利用垃圾清理器[10]（Gabage cleaner）定期清除索引树中的旧记录,动态维护UM的数据项和内存大小,使LUMR*-tree能够满足移动对象频繁位置更新的需求。实验结果表明,LUMR*-tree具有较高的更新效率和查询效率。

2 移动对象索引策略

在传统R*-tree中,对象的更新通常采用自顶向下的方式,分成删除和插入2个独立的步骤完成,频繁使用删除-重插机制实现索引更新将会导致其整体性能急剧下降。从对象更新的角度看,R*-tree存在以下3点不足：
（1）R*-tree中直接存储对象的精确位置信息,当移动对象的位置不断变化时,索引结构需要动态调整;
（2）R*-tree的节点允许目录矩形覆盖与重叠,采用自顶向下方式查找旧数据项时,需要遍历多条路径和多个节点,这无疑会增加索引的更新代价;
（3）为提高查询性能,R*-tree要求目录矩形尽可能紧凑,当移动对象位于目录矩形的边界附近并可能频繁出入目录矩形边界时,每一次删除或插入操作都可能引起节点分裂、合并和调整,这将大大增加索引的更新代价。
基于以上几点不足和R*-tree的结构特点,本文引入以下更新策略。

2.1 自底向上的更新方式

传统R*-tree更新时首先采用自顶向下方式找到旧数据项所在的叶子节点,先从节点中删除旧数据项,然后再次采用自顶向下方式选择最合适的叶子节点插入新数据项。这种删除-重插的更新机制,可能导致节点分裂和合并,更新操作相当复杂。
如图1所示,通过在R*-tree中增加一个用于索引数据项的二级索引（以Hash-table为例）,可以直接访问叶子节点中的数据项。其中,Ri表示R*-tree的索引项,ri、pi表示不同类型的数据项。Hash-table通过唯一的指针指向R*-tree,其中存储的数据项可描述为<ObjID, Ptr>,ObjID代表数据项ID,Ptr表示指向索引树中对应数据项的指针。
自底向上的更新思路是通过Hash Table直接找到叶子节点中对应的旧数据项,用新数据项代替,同时修改索引树中受影响的节点。这种更新方式主要针对叶子节点及其父亲节点,当节点分裂时会增加父亲节点的维护代价。
Fig. 1 Structure of R*-tree and auxiliary index

图1 R*-tree结构和二次索引

2.2 扩展MBR

如图2所示,当移动对象沿着R*-tree目录矩形的边界运动时,如果对象多次进出目录矩形,将会导致R*-tree不断执行删除和插入操作,这将大幅度增加R*-tree的更新代价。借鉴文献[14]中的思想,引入扩展MBR（Extended MBR, EMBR）的概念,通过扩展目录矩形减少索引的更新代价。
Fig. 2 Extended MBR

图2 扩展 MBR

EMBR[14]定义为：在d维空间中,移动对象O表示为{O1, O2,…, OK},其中Oi（1≤i≤K）代表不同时刻的移动对象,其对应的位置表示为 o k = ( p k 1 , p k 2 , … , p k d ) （1≤k≤d）,则有：
EMBR =（EI1, EI2 ,…, EId） （1）
E I i = min ( p k i - ε ) , 1 ≤ k ≤ K max ( p k i + ε 1 ≤ k ≤ K （2）
式中： ε 为一常量,表示目录矩形的扩展率。可以预测,当 ε 的值越大,移动对象越出边界的几率越小,索引的更新代价越小。然而,这将导致目录矩形的重叠率和覆盖率变大,索引的查询效率将会降低。这种情况下,关键是选择一个大小合适的 ε ,使索引的整体性能达到最优。

2.3 更新备忘录

如文献[10]所述,在自底向上更新方式的基础上,在R*-tree中引入UM辅助索引结构,将进一步减少索引的更新代价。如图3（a）所示,在R*-tree中插入一个新记录时,计数器首先为其分配一个stamp（表示插入的顺序）,然后将新记录按R*-tree的插入算法插入到树中,最后添加/更新UM中的数据项。如图3（b）所示,当执行查询操作时,首先利用R*-tree的查询算法得到候选结果集,再通过UM将候选结果集中的旧记录剔除,得到最终的查询结果。
Fig. 3 Spatial operation processes of R*-treewith update memo

图3 加入UM的R*-tree空间操作流程

3 算法实现

在充分利用第2节介绍的更新策略的基础上,本文设计了LUMR*-tree的结构图（图4）,并实现了相关算法。
Fig. 4 Structure of LUMR*-tree

图4 LUMR*-tree结构图

对于LUMR*-tree的基本结构,有以下3点说明：
（1）树的结构。从根节点往下,树中各层级节点之间的指针均是双向的,这样能够从孩子节点直接访问父亲节点。在叶子层中,相邻兄弟节点用双向指针相连,便于兄弟节点之间快速访问。
（2）UM。UM中存储的数据项可描述为：（ oid , Ptr , S latest , N old ）。其中,oid和Ptr分别表示数据项ID和指向该数据项的指针;Slatest表示UM中该ID对应最新数据项的stamp;Nold表示UM中该ID对应的记录项集合中旧记录的个数;UM可以用于区分新旧数据项。
（3）叶子节点的数据项。叶子节点的数据项可描述为：（ MBR , oid , stamp ）。其中,MBR表示对象的最小外接矩形;oid表示对象ID;stamp是指对象插入时分配的标志,用于区分数据项的插入顺序。

3.1 插入算法

LUMR*-tree的插入算法与传统R*-tree类似。在插入过程中,首先利用计数器为待插入数据项分配stamp,然后利用R*-tree的插入算法,将新数据项插入LUMR*-tree中,同时将stamp分配给该数据项对应的叶子条目。为了体现该条目的最新性,需要对UM中的数据项进行更新。更新流程为：在UM中查找与插入数据项ID相同的记录项,如果不存在,直接将该数据项添加到UM中;否则,还需要将查找到的所有记录项的Slatest置为stamp,并将UM中该ID对应旧记录项的个数加1。插入算法如下：
Algorithm LUMR*-tree_Insert（）
Input: oid, newLocation
Output: LUMR*-tree
Begin
newRecord = （oid, newLocation）;
stamp ← StampCounter; Increment StampCounter;
Insert the newRecord to the LUMR*-tree;
Let ne be the inserted leaf entry for newRecord;
ne.stamp ← stamp;
Search oid in UM;
If no entry is found, insert （oid, Ptr, stamp, 1） to UM;
Otherwise, let umne be the found UM entry;
umne.Slatest ← stamp; Increment umne.Nold;
End

3.2 删除算法

从LUMR*-tree中删除一个对象与R*-tree有较大不同,删除过程其实是一次UM的更新过程,只需将UM中与该对象ID对应的最新数据项置为“旧（Obselete）”即可。这种更新不需要LUMR*-tree本身的参与,仅仅影响UM中与该对象对应的最新数据项。如果最新数据项存在,将Slatest置为新分配的stamp,并将UM中对应的Nold增加1;如果不存在,插入一个新数据项,使得：Slatest=stamp, Nold = 1, Ptr = NULL。通过这种方式,UM中所有与待删除对象对应的数据项都被置为“Obselete”,这些旧数据项最终将被清理器清除。删除算法如下：
Algorithm LUMR*-tree_Delete（）
Input: oid
Output: Updated UM
Begin
stamp ← StampCounter; Increment StampCounter;
Search oid in UM;
If no entry is found in UM, insert （oid, NULL, stamp, 1） to UM;
Otherwise, let umne be the found UM entry;
umne.Slatest ← stamp; Increment umne.Nold;
End

3.3 查询算法

在LUMR*-tree中,移动对象的新、旧记录可能同时存在,在执行查询操作时,首先利用LUMR*-tree得到候选结果集,再通过UM剔除满足查询条件的旧记录,得到最终结果集。查询算法如下（以范围查询为例,其他查询方式类似）：
Algorithm LUMR*-tree_RangeSearch（）
Input: QueryRegion
Output: Object-set
Begin
Search leafEntry by Top-Bottom Approach;
If QueryRegion contains leafEntry.MBR
Insert the leafEntry to Object-set;
Else return step 1 until the whole tree has been searched;
For each entry in Object-set
If the entry.stamp is obsolete in the UM
Delete this entry from Object-set
End

3.4 更新流程

如何有效地提高更新效率是移动对象索引技术一直重点关注的话题。在充分利用第2节介绍的技术的基础上,将延迟更新和备忘录插入/更新相结合,本文设计LUMR*-tree的更新流程如图5所示。
Fig. 5 Updated processes of LUMR*-tree

图5 LUMR*-tree的更新流程

3.5 垃圾清理

如果UM中的旧记录过多,势必会影响索引的整体性能。因此,使用“垃圾清理器”定期清除索引树中包含的旧记录,动态维护UM内存结构的大小,保证索引的稳定性和高效性。垃圾清理算法如下：
Algorithm LUMR*-tree_Clean （）
Input: LeafNode N
Output: Cleaned LUMR*-tree
Begin
For each entry e in N
Search e.oid in UM
If no entry is found, return;
Otherwise, let ume be the found UM entry;
If （N.stamp == ume.Slatest）, return;
Else
（a） Delete e from N;
（b） Let ume be the UM entry for e.oid;
Decrement ume.Nold;
If （ume.Nold == 0）, delete ume from UM;
If N.entryCount < MINentries, re-insert the remaining entries of N into the LUMR*-tree;
Otherwise, adjust the MBRs of N and its ancestors in a bottom-up manner;End
在实际应用中,LUMR*-tree叶子层中的数据项通常存储于磁盘,而非叶子节点存储于内存。当执行插入或更新操作时,清理器可以并行地进行空间清理,这将在一定程度上提高清理的效率。然而,选择何时进行清理是一个需要重点关注的话题。本文引入检查率[15]（inspection ratio, ir）来衡量清理器的清理频率。当ir较小时,清理频率较低,索引树和UM中的旧记录多,会影响索引的查询效率;相反,较大的ir则会使清理器频繁地扫描叶子节点,引起不必要的磁盘访问,这将会影响到索引的更新效率。因此,ir的设置在索引的更新效率和查询效率之间存在平衡。在下面的实验中,将对ir作进一步分析。

4 实验与分析

为评价LUMR*-tree的性能,本文设计了一组实验,将LUMR*-tree与R*-tree、文献[14]中的LUR-tree进行对比,并对相关算法加以评估和分析。
实验数据集由文献[16]中的移动对象随机生成方法得到,在100 km×100 km的空间区域内模拟 1~10 M移动对象的运动情况,其默认值设置为 1 M。在运动开始时,随机为每一个移动对象设置一个初始位置,过一定时间t后批量更改移动对象的位置并发出索引更新请求。实验的主要参数如表1所示,其中粗体字表示默认值。
Tab. 1 Experiment parameters and values

表1 常用实验参数及取值

参数 值
移动对象的数量(M) [1, 10],1
目录矩形扩展率(ε) (0,0.0025,0.005),0.0025
更新次数(次) [1000,10000],1000
检查率(ir) [0,1],20%
查询窗口占整个区域的比率 (0.0001%,0.001%,0.01%,0.1%,1%),0.01%
在libSpatialIndex[17]空间索引库的基础上,分别构建R*-tree、LUR-tree和LUMR*-tree,节点大小设置为4 KB,页面缓存大小为200 KB。实验的硬件环境为：Intel（R） Core（TM） 2.5HZ CPU,内存为4096 MB RAM;软件环境为：Windows7操作系统和Visual C++ 2010集成开发环境。

4.1 扩展率

ε
扩展率 ε 直接影响索引树中目录矩形的重叠率和覆盖率,进而影响其整体性能。图6和图7分别比较了在不同 ε 的情况下,LUMR*-tree、R*-tree和LUR-tree完成范围查询和1000次更新操作所需要的磁盘I/O。
Fig. 6 Average disk I/O (range query)

图6 平均磁盘访问次数（范围查询）

Fig. 7 Total disk I/O (1000 updates)

图7 总磁盘访问次数（1000次更新）

由图6可知,随着查询窗口变大,3种索引执行查询操作所需的磁盘访问次数均明显增加,但LUMR*-tree（0）（ ε =0）、LUR-tree和R*-tree的磁盘访问次数相差不大。随着 ε 不断增加,LUMR*-tree需要更多磁盘访问次数来完成查询操作。这表明,LUMR*-tree的查询性能随 ε 增大而降低。在图7中,随着数据量增加,3种索引完成1000次更新操作所需的磁盘访问次数均有所增加,但R*-tree明显比其他2种索引增长得快,尤其当数据量超过7000时增长迅速,这可能是因为索引树的高度增加,节点发生了分裂和合并。分析可知,当数据量较大时,LUMR*-tree避免了不必要的节点访问和调整,能够有效减少更新操作代价。对于LUMR*-tree, ε 越大,索引的更新代价要相对而言小一些,但总体差别不大。

4.2 检查率ir和UM

检查率ir直接影响UM的大小和索引树中的旧记录数量,进而影响LUMR*-tree的查询、更新效率及失效率。假设LUMR*-tree中的叶子节点的个数为N,E为UM中记录项的大小,M为索引树中移动对象的总个数。在垃圾清理器运行之后,叶子节点中的旧记录将会被全部清除。在插入/更新操作累计执行 N ir 次后,清理器才运行一次。因此,在最坏的情况下索引树中旧记录的个数为 N ir 。在实际情况中,索引树中失效率的平均值为 N 2 ir × M ,UM的平均大小为 N × E 2 ir 。
图8（a）、（b）分别比较了检查率对UM大小和LUMR*-tree中旧记录数量的影响。不难看出,随着检查率增加,内存结构UM的大小和LUMR*-tree中旧记录比率呈下降趋势。这是因为,较大的检查率使清理器更加频繁地删除UM中过时的记录项和索引树中的旧记录。图8（c）描述了检查率对索引更新时间的影响。当ir约为20%时,LUMR*-tree和LUR-tree取得最小更新时间。当ir<20%时,检查率越小,索引的更新时间越多,这可能是由UM和索引树中过多的旧记录导致的。随着检查率不断增加（ir>20%时）,频繁的清理工作使索引的更新时间有所增加。如图8（d）所示,在查询性能上,R*-tree表现最佳,LUR-tree次之,LUMR*-tree表现最差。结合图8（c）、（d）分析可知,检查率对R*-tree的整体性能几乎没有影响,当ir=20%时,LUMR*-tree和LUR-tree获得了较好的更新和查询性能。
Fig. 8 Effect of inspection ratio

图8 检查率的影响

4.3 更新代价

假定索引树高度为H,总更新次数为T。对于延迟/备忘录更新,插入一个数据项需要先访问H个节点找到合适的叶子节点,再将其插入叶子节点中。当检查率为ir时,叶子节点需要被检查T*ir次,每一次检查需要一次磁盘I/O,因此一次更新操作的平均磁盘I/O为H+1+ir。
为了更好地验证LUMR*-tree的更新性能,在实验中,分别比较了不同更新次数和移动对象数量对更新性能的影响。由上述分析可知,当扩展率 ε =0.0025、检查率ir=20%时,LUMR*-tree整体性能较高。因此,在下面的实验中,将 ε =0.0025、ir=20%设置为默认值。
结合图9（a）-（d）,对于不同的更新次数和移动对象数量,LUMR*-tree的更新性能最优,LUR-tree表现次之,而R*-tree的更新性能随更新次数和移动对象数量的增加急剧降低（为了更好地体现索引更新性能的差异,当更新次数和移动对象数量较大时,R*-tree的实验结果未直接在图中表现出来）。由于R*-tree在处理更新操作的过程中采用简单的删除-重插方式,随着更新次数和移动对象数量不断增加,索引的空间结构不断恶化,导致更新性能急剧降低。借助UM辅助索引结构、Extend MBR以及自顶向下和自底向上相结合的更新策略,能够有效改善LUMR*-tree的更新性能,这在实验中得到了充分体现。
Fig. 9 Updating cost

图9 更新代价

4.4 查询代价

如4.2节所述,索引树中失效率的平均值为 N 2 ir × M ， 平均的失效记录数可表示为 N 2 ir × M × ∑ i = 1 M i M = N × ( M + 1 ) 4 ir × M 。执行一次查询操作时,需要先在索引树找出候选结果集,这一过程需要访问H个节点,然后利用UM过滤得到最终的结果集。设最终查询到的记录数为n,那么整个查询过程的时间复杂度为 O ( n + 1 ) ( t 1 + N × ( M + 1 ) 4 ir × M t 2 ) （设2个过程需要的迭代次数分别为t1、t2）。
在实验中,设置查询方式为窗口查询和最近邻查询,移动对象数量设置为10 000,查询时机为索引开始更新前和更新操作执行到一半时。由于最近邻查询得到的结论与窗口查询类似,本文只对窗口查询的结果加以展示和分析。
Fig. 10 Window searching

图10 窗口查询

图10(a)-(d)分别表示了LUMR*-tree、LUR-tree和R*-tree在不同大小查询窗口下范围查询所需的平均CPU Time和总磁盘I/O次数。综合分析可知：
（1）在查询性能上,R*-tree表现相对较好,LUMR*-tree和LUR-tree总体差别不大;
（2）随着查询窗口变大,LUMR*-tree和LUR-tree的查询代价增加得明显比R*-tree快。这是因为LUMR*-tree、LUR-tree以及UM中存储的旧记录,使得查询时需要更多遍历和筛选操作;
（3）图10（c）中,当查询窗口比率超过0.01%时,LUMR*-tree和LUR-tree的磁盘I/O迅速增加,这可能是因为查询范围增大使需要遍历的节点数量迅速增多。
（4）索引更新前后,R*-tree查询性能相差较大。如图10（d）所示,当更新操作执行到一半,查询窗口比率超过0.01%时,R*-tree的查询性能急剧恶化,这可能是因为频繁的更新操作破坏了R*-tree的空间结构,查询时需要遍历更多路径和节点。

5 结论

本文在R*-tree的基础上,引入基于延迟更新和备忘录更新/插入的移动对象索引策略,针对移动对象频繁更新位置所导致的索引运行效率低的问题,提出了一种支持大批量频繁位置更新的移动对象索引结构LUMR*-tree。与R*-tree和LUR-tree相比,LUMR*-tree借助多种更新策略简化了索引的更新操作。实验结果表明,在牺牲少量查询性能的情况下,LUMR*-tree获得了更高的更新性能,利用UM辅助索引结构保证了索引的稳定性和高效性。未来的研究方向是在不确定移动对象中,通过引入时间和速度维度,将问题扩展到对时空数据和历史数据的更新和查询。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Saltenis S, Jensen C S, Leutenegger, et al. Indexing the positions of continuously moving objects[D]. In: Mobile Data Management, 2003.

[2]
谈国新. 一体化空间数据结构及其索引机制研究[J].测绘学报,1998,27(4):293-297.本文提出了一种新的栅矢一体化空间数据结构,该结构采用三级划分策略及几何目标元子充填表达技术,使空间数据栅格化的同时,也能满足精度要求.同时引入弧段栅格比特阵和面要素自适应空间索引结构,有效地提高了空间检索效率.试验证明,上述理论及方法是可行的.

DOI

[ Tan G X.Study of integrated spatial data structure and spatial index menchanism[J]. Acta Geodaetica et Cartographica Sinica, 1998,27(4): 293-297. ]

[3]
Kollios G, Gunopulos D, Tsotras V J.On indexing mobile objects[C]. Proc. 1999 ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June, 1999.

[4]
Tao Y F, Papadias D, Sun J.The TPR*-tree: An optimized spatio-temporal access method for predictive queries[C]. Proceedings of the VLDB 2003, San Francisco, 2003:790-801.

[5]
Guttman A.R-trees: A dynamic index structure for spatial searching[C]. In Proc. of 20th Int. Conf. on Very Large Data Bases, Morgan Kaufmann, 1984.

[6]
Ouri Wolfson, Xu B, Sam Chamberlain, et al.Moving objects databases: Issues and solutions[C]. International Conference on Scientific & Statistical Database Management, 2015,33(4):111-117.

[7]
Mong Li Lee, Wynne Hsu, Christian S Jensen, et al.Supporting frequent updates in R-trees: A bottom-up approach[C]. Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.

[8]
Cheng R, Xia Y, Prabhakar S, et al.Change tolerant indexing for conatantly evolving data[C]. International Conference on Data Engineering, 2005:391-402.

[9]
Silva Y N, Xiong X, Aref W G.The RUM-tree: supporting frequent updates in R-trees[J]. The VLDB Journal, 2009,18(3):719-738.ABSTRACT The problem of frequently updating multi-dimensional indexes arises in many location-dependent applications. While the R-tree and its variants are the dominant choices for indexing multi-dimensional objects, the R-tree exhibits inferior performance in the presence of frequent updates. In this paper, we present an R-tree variant, termed the RUM-tree (which stands for R-tree with update memo) that reduces the cost of object updates. The RUM-tree processes updates in a memo-based approach that avoids disk accesses for purging old entries during an update process. Therefore, the cost of an update operation in the RUM-tree is reduced to the cost of only an insert operation. The removal of old object entries is carried out by a garbage cleaner inside the RUM-tree. In this paper, we present the details of the RUM-tree and study its properties. We also address the issues of crash recovery and concurrency control for the RUM-tree. Theoretical analysis and comprehensive experimental evaluation demonstrate that the RUM-tree outperforms other R-tree variants by up to one order of magnitude in scenarios with frequent updates.

DOI

[10]
Beckmann N, Kriegel H P, Schnieide R, et al.The R*-tree: An efficient and robust access method for points and rectangles[C]. In: Proc. of ACM Intl. Conf. on the Management of Data(SIGMOD), 1990:322-331.

[11]
Agarwal P K, Arge L, Erickson J, et al.Efficient tradeoff schemes in data structures for querying moving objects[C]. The 12th Annual European Symposium on Algorithms, 2004:4-15.

[12]
Xiong X, Aref W G: R-trees with update memos[C]. In: ICDE, 2006.

[13]
D Kwon, Lee S J, Lee S. Indexing the current positions of moving objects using the lazy update R-tree[C]. 3rd Intl. Conference on Mobile Data Management, 2002.

[14]
丁晓峰,金海,赵娜.支持频繁位置更新的不确定移动对象索引策略[J].计算机学报,2012,35(12):2588-2593.移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需 求,如何在频繁位置更新应用中索引不确定移动对象的当前及未来位置信息成为当前的研究热点之一.TPU树是针对不确定移动对象的当前及未来位置信息索引的 策略,其具有较高的概率域查询效率,但是其采用的传统自顶向下更新算法,存在频繁位置更新效率低下的问题.通过在TPU树上增加一个记录不确定移动对象状 态特征的更新备忘录(UM)内存结构,文中提出了一种支持频繁位置更新的不确定移动对象索引策略TPU2M树,并在此基础之上提出了一种改进的基于备忘录 (MMBU/I)的更新/插入算法.代价分析和实验仿真表明,采用MMBU/I算法的TPU2M树频繁更新性能大大优于TPU树和ABx树索引,且概率查 询性能与传统索引大致相当,因此具有很好的实用价值和广泛的应用前景.

DOI

[ Ding X F, Jin H, Zhao N.Indexing of uncertain moving objects with frequent updates[J]. Chinese Journal of Computers, 2012,35(12):2588-2593. ]

[15]
Bringkhoff T.A framework for generating network based moving objects[J]. Geoinformatica, 2002,2(6):162-175.Benchmarking spatiotemporal database systems requires the definition of suitable datasets simulating the typical behavior of moving objects. Previous approaches for generating spatiotemporal data do not consider that moving objects often follow a given network. Therefore, benchmarks require datasets consisting of such etwork-based moving objects. In this paper, the most important properties of network-based moving objects are presented and discussed. Essential aspects are the maximum speed and the maximum capacity of connections, the influence of other moving objects on the speed and the route of an object, the adequate determination of the start and destination of an object, the influence of external events, and time-scheduled traffic. These characteristics are the basis for the specification and development of a new generator for spatiotemporal data. This generator combines real data (the network) with user-defined properties of the resulting dataset. A framework is proposed where the user can control the behavior of the generator by re-defining the functionality of selected object classes. An experimental performance investigation demonstrates that the chosen approach is suitable for generating large data sets.

DOI

[16]
Marios Hadjieleftheriou. libSpatialindex[DB/OL].https://github.com/libspatialindex/ libspatialindex.ABSTRACT The iterative closest point (ICP) algorithm is one of the most popular approaches to shape registration currently in use. At the core of ICP is the computationally-intensive determination of nearest neighbors (NN). As of now there has been no comprehensive analysis of competing search strategies for NN. This paper compares several libraries for nearest-neighbor search (NNS) on both simulated and real data with a focus on shape registration. In addition, we present a novel efficient implementation of NNS via k-d trees as well as a novel algorithm for NNS in octrees.

DOI

Options
文章导航

/

〈 〉