Abstract: In order to eliminate the parallel performance impact caused by locking operations and improve the throughput of moving object databases, this paper proposes a GPU accelerated indexing method, based on a grid data structure, combined with quad-trees. By using GPU to count object movements and keep deciding whether a particular node should be split or child nodes of a common father should be merged, bottle necked nodes can be translated to quad-tree without interfering CPU, hence waiting time of other threads caused by locking operations raised by  object data updating can be reduced. The method is simple while more adaptive to scenarios where the distribution of moving objects is skewed. It also avoids the shortcomings of existing methods that have performance bottle neck on hot area, or spend plenty of calculation resources on structure balancing. The experimental results suggest that, compared with existing indexing methods, the proposed method shows higher throughput and lower response time. The advantage is more significant under skewed distribution of moving objects.

Key words: moving object indexing, dynamic grid indexing, spatial database, GPU accelerated

摘要： 为减少加锁操作对移动对象数据库并行性能的影响并提高其吞吐量，提出一种由GPU加速的网格结合四叉树的索引方法。采用由GPU对出入节点对象进行计数并持续计算节点拆分/合并条件的方式，在不影响CPU计算能力的前提下，将存在性能瓶颈的网格节点转化为四叉树，从而减少对象数据更新时加锁操作造成的其他线程等待时间。该方法结构简单且更适用于对象不均匀分布的场景，避免了现有索引方式或在热点区域存在性能瓶颈，或需花费大量计算资源进行结构平衡等缺点。实验结果表明，该方法与现有移动对象索引方式相比具有数据吞吐量大、响应速度快等特点，在移动对象空间分布不均匀的场景下其优势更为明显。

关键词: 移动对象索引, 动态网格索引, 空间数据库, GPU加速