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

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