地球信息科学学报

地球信息科学学报 ›› 2017, Vol. 19 ›› Issue (2): 152-160.doi: 10.3724/SP.J.1047.2017.00152

• 地球信息科学理论与方法 • 上一篇    下一篇

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

彭召军1(), 封俊翔2, 王青山1, 熊伟1   

  1. 1. 信息工程大学,郑州 450001
    2. 95956部队,西安 710061
  • 收稿日期:2016-07-12 修回日期:2016-10-23 出版日期:2017-02-28 发布日期:2017-02-17
  • 作者简介:

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

  • 基金资助:
    国家自然科学基金项目（41501507）

A Moving Object Indexing Method that Supports Frequent Location Updating

PENG Zhaojun1,*(), FENG Junxiang2, WANG Qingshan1, XIONG Wei1   

  1. 1. Information Engineering University, Zhengzhou 450001, China
    2. 95956 Troops, Xi'an 100042, China
  • Received:2016-07-12 Revised:2016-10-23 Online:2017-02-28 Published:2017-02-17
  • Contact: PENG Zhaojun E-mail:107618599@qq.com

RichHTML

PDF (PC)

赞

被引次数

1 | 1

摘要：

传统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

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