Abstract: This paper presents a new method for partitioning space in the basis of existing space partitioning based B+tree index of moving objects, the method improves the efficiency of indexing in the situation of that moving objects are non-uniformly distributed by partitioning space using two-level grids. The paper proposes algorithms for range and kNN queries. The result of extensive experiments shows that the performance of the index is hardly impacted by the non-uniform distribution of moving objects.

Key words: moving objects, B+tree index, two-level grids

摘要： 在已有的基于空间分割的移动对象B+树索引基础上，提出一种分割空间的新方法，对空间进行二层网格分割，使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明， 该索引结构的性能基本不受移动对象分布的影响。

关键词: 移动对象, B+树索引, 二层网格

CLC Number: 

• N945