QGrid:一种空间移动对象并行索引结构  

QGrid: A Parallel Indexing Structure for Spatial Moving Objects

作　　者：李传文[1] 车庆首 谷峪[1] 邓庆绪[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2016年第11期1541-1545,1550,共6页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(61300021);中央高校基本科研业务费专项资金资助项目(N140404008)

摘　　要：为提高空间移动对象数据更新效率和查询准确率,提出了一种空间移动对象并行索引结构.利用主索引和辅助索引支持对空间对象进行基于范围的查询和基于对象标识的查询,还通过查询索引将更新操作和可能受其影响的查询操作相连接,在满足并行操作时间片语义的同时,避免了传统方法进行范围查询时对查询范围内相关对象及相关索引结构全部进行锁定的需求.实验结果表明:高负载环境下,该索引结构不但能保证查询准确率,其处理能力也明显优于传统索引结构.该索引通过提高系统并行度,使同一范围内的更新和查询操作可以并行执行,提升了系统整体运行效率.In order to improve updating efficiency and querying accuracy for spatial moving object data, a parallel indexing structure for spatial moving objects was proposed. A main index and an auxiliary index were contained in the proposed structure, which were used for supporting range based and identity based spatial object query operations, respectively. A query index was also utilized which hooks updating operations to querying operations that may be influenced. Thus locking relevent spatial objects and indexing structures could be avoided when range query operations are processed. At the same time, it also support timeslice semantics for parallel operations. Experimental results show that, under high working load, the structure can not only guarantee querying accuracy, the throughput is also obviously higher than that of the existing methods. The index improves the degree of system parallelism, makes it possible for object updating and querying operations in same ranges be processed in parallel, and therefore improves the overall efficiency of the system. © 2016, Editorial Department of Journal of Northeastern University. All right reserved.

关 键 词：空间移动对象 空间数据索引 范围查询 时间片查询 并行更新 

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