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

摘要：

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

所属期刊栏目：19

分类号：TP3;TN9

资助基金：国家自然科学基金项目41501507。

在线出版日期：2017-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：152-160