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

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