Abstract: Positional uncertainty is one key feature of the moving objects. Existing uncertain moving objects indexing technology aims to improve the efficiency of querying. However, when moving objects positions update frequently, the update cost is huge. In order to solve this cost problem, this paper modifies the group partition strategy of TPU-tree and gives an index structure named GTPU-tree that supports frequent position update. Furthermore, this paper proposes  a group partition algorithm STSG based on spatial trajectory of similarity and moving objects group updating algorithm. GTPU-tree reduces the number of disk I/O by reducing the update number in the same group, thus decreasing the update cost. This paper compares and analyzes the algorithm efficiency of GTPU-tree and TPU2M-tree. The experimental results demonstrate that while the number of moving objects is large, GTPU-tree update cost will be lower than TPU2M-tree; Compared with TPU-tree, GTPU-tree performs better than TPU-tree, which improves the inserting performance by 30% and reduces the update cost by 35%.

Key words: position uncertainty, TPU-tree, TPU2M-tree, group partition, update cost

摘要： 位置不确定性是移动对象的重要特点之一。已有的不确定移动对象索引技术旨在提高查询效率，但是当移动对象位置频繁更新时，存在更新代价较大的问题。针对移动对象频繁位置更新引起的开销增加问题，在TPU-tree索引结构上支持移动对象群组划分策略，给出了一种适用于频繁位置更新的索引结构GTPU-tree。在此基础上提出了基于空间轨迹相似度的群组划分算法STSG（spatial trajectory of similarity group）和不确定移动对象群组更新算法。GTPU-tree通过减少同一分组中移动对象的更新次数，降低磁盘I/O次数，从而降低更新代价。通过实验对基于GTPU-tree和TPU2M-tree等索引结构的算法效率进行了对比分析，结果表明GTPU-tree相比于TPU2M-tree在移动对象数量较大时，GTPU-tree的更新代价将低于TPU2M-tree；与TPU-tree相比插入性能提高约30%，更新代价降低约35%。

关键词: 位置不确定性, TPU树, TPU2M树, 群组划分, 更新代价