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

A Moving Object Indexing Method that Supports Frequent Location Updating

作　　者：彭召军[1] 封俊翔 王青山[1] 熊伟[1] PENG Zhaojun FENG Junxiang WANG Qingshan XIONG Wei(Information Engineering University, Zhengzhou 450001, China 95956 Troops, Xi＇an 100042, China)

机构地区：[1]信息工程大学 [2]95956部队

出　　处：《地球信息科学学报》2017年第2期152-160,共9页Journal of Geo-information Science

基　　金：国家自然科学基金项目(41501507)

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

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]