TPR-树性能优化研究

Research and improvement of TPR-Tree

为了降低TPR-树的时间复杂度、提高查询效率，提出结点分裂的改进算法及基于距离的结构调整策略。改进算法把TPBR（time-pararneterized bounding rectangle）在某时间段内的周长定积分作为代价函数，并在投影定积分值最大的轴上进行结点分裂，做到了同时兼顾移动对象的空间属性与速度属性。在结构调整策略中通过删除结点中移动距离超过阈值的记录，从而使TPBRs的扩张速度变慢，在一定程度上抑制了TPBRs之间的重叠。实验结果表明，与原TPR-树结点分裂算法相比，改进后的结点分裂算法的运行时间降低了5～8倍，查询性能至少提高了50％，而且，在此基础上应用基于距离的结构调整策略使查询性能进一步提高约10％。

In order to reduce the complexity of algorithms and enhance the efficiency of TPR-tree, an improved node-split algorithm and a distance-based structure adjusting policy are proposed. The definite integral of perimeter for TPBR （time-parameterized bounding rectangle） within a period of time is considered as penalty metrics in the improved algorithm, which also decides a split axis as the one with the smaUest projection definite integral value. The distance-based structure adjusting policy makes slow the expand speed of TPBRs by deleting the records of objects that move too far. The experimental comparison shows that the complexity of improved node-split algorithm is only 12-20% of primary node-split algorithm of TPR-tree, and the TPR-tree used improved node-split algorithm whose query performance is up to 50% better than the primary TPR-tree. Furthermore, the query performance of TPR-tree used distance-based structure adjusting policy can also increase by 10% or so solely.