基于aTPRA-tree的移动对象预测范围聚集查询算法研究

牛言涛，何茂顺，姚玉霞

(1.吉林农业大学发展学院，长春 130600;2.宁波大学 计算机科学技术研究所，宁波 315211)

0 引言

Ine’s等［1］综述了PRA(Predictive Range Aggregate，PRA)查询方法，PRA是移动对象数据库中的一种重要的查询类型之一。当前，PRA查询方法主要有两种:一是精确聚集，如采用 TPR-tree［2］、VCI R-tree［3］和STRIPE［4］索引等。二是近似查询，如 STH 技术［5］、SAMH 方法［6］和 AMH*［7］等。

以上方法由于没有考虑移动对象在时空域上的特殊性，TPR-tree索引随着时间的推移，性能将逐渐恶化，结点面积和结点重叠面积将逐渐增大，导致查询性能下降。文献［8］基于PRA-tree提出aTPRA-tree索引结构，本文基于aTPRA-tree给出预测范围聚集查询定理和算法。通过该剪枝算法加速了查询的过程，提高了预测范围聚集查询的性能和效率。

2 aTPRA-tree索引结构

aTPRA-tree［8］(The aggregation TPR-tree based on the Angle，aTPRA-tree)(如图1)沿用 TPR-tree 的索引结构，但在TPR-tree的索引结点结构中增加了聚集信息。

图1 aTPRA-tree索引结构

3 aTPRA-tree聚集查询算法

廖巍等［2］提出了一种剪裁不需要访问结点的方法，即定理1。本文提出aTPRA-tree剪枝定理和算法，使得相对于定理1更快速判断出其结点是否要被访问。先给出两个定义:

定义1 TPBR(Time-Parameterized Bounding Rectangle，TPBR)运动趋势点.在TPBR的四个顶点中，与TPBR基准点相对角的顶点称为TPBR运动趋势点。

定义2 TPBR决定点(Decision Points，DB).在TPBR的四个顶点中，除了TPBR基准点和TPBR运动趋势点之外的另外两个顶点称为TPBR决定点。

示例图2，TPBR的运动趋势点为顶点b，决定点DB为顶点a和d，查询qT即为矩形B。

图2 TPBR与查询窗口的拓扑图

aTPRA-tree剪枝定理给定中间索引结点的某个TPBR和PRA查询q(qR，qT)，若TPBR决定点在查询窗口qT内落在查询qR中，则该索引结点下的子树中所有移动对象都将会在查询窗口qT内落在查询qR中，则此时PRA查询算法只需返回该结点的聚集信息即可。证明:

不妨假设，a在将来落在B中的时刻记做ta，d落在B中的时刻记做td，且ta＞td。在td时刻，d在边gh之上且在边fh之右，由于顶点c和d在一条线上，则c也在边gh之上且在边fh之右，此时顶点a在边ef之下，同理，c也在边ef之下。而等到了ta时刻，顶点a在边eg之右，在边fh之左，且在边ef之下，则c此时也在边eg之右，在边fh之左，且在边ef之下。由于顶点c在td时刻已在边gh之上，且cd边没有向下的速度，则ta时刻顶点c也在边gh之上，这样在ta时刻顶点c也落在矩形B中。

同理，可以证出顶点b在td时刻也落在矩形B中。根据定理1［2］，可知该索引结点下的子树的所有移动对象在查询窗口qT中都会落在矩形B内，则在PRA中，返回该结点的聚集信息即可。

证毕。

结合aTPRA-tree剪枝定理，给定aTPRA-tree的线性链表L，聚集查询结果Agg(q)以及聚集函数Count函数。给出算法如下:

4 实验评估

本实验采用的模拟数据生成器与文献［8］相同，生成100K和10K的数据若干组，进行实验。角度区间数目表示aNum设置为8。qRlen(查询空间窗口大小)分别固定为100×100，300×300，600×600，900×900，1200×1200，1500×1500，而此时的qTlen(查询时间窗口大小)设定为20。接着，设定qRlen为900×900，qTlen分别为10、20、30、50、80、100，分别进行20次窗口查询实验，且分别设置100K和10K的数据量。

图3显示了aTPRA-tree在qTlen大小一致而qRlen不同的情况下(qTlen为20)，平均读写次数比同等条件下的TPR-tree性能要好。图4显示了在不同的qTlen情况下，aTPRA-tree的性能优于TPR-tree(qRlen为900×900)。同理，图5和图6显示了在数据量为10K的情况下，aTPRA-tree也比TPR-tree查询性能好很多。

图3 aTPRA-tree与TPR-tree查询性能比较1(100K)

图5 aTPRA-tree与TPR-tree查询性能比较1(10K)

5 结语

图4 aTPRA-tree与TPR-tree查询性能比较2(100K)

图6 aTPRA-tree与TPR-tree查询性能比较2(10K)

本文在aTPRA-tree索引结构基础上，提出了aTPRA-tree剪枝定理和算法。通过该剪枝定理加速了查询的过程，提高了预测范围聚集查询的性能，实验数据证明了此方法的有效性。

［1］Ine’s Fernando，Vega Lo’pez，Richard T Snodgrass.Spatiotemporal aggregate computation:A survey［J］.IEEE TKDE，2005，17(2):271-286.

［2］廖巍，景宁，钟志农，等.面向移动对象的高效预测范围聚集查询方法［J］.计算机研究与发展，2007，44(6):1015-1021.

［3］Prabhakar Sunil，Xia Yuni，Kalashnikev Dmitri V，et al.Query Indexing and Velocity Constrained Indexing:Scalable Techniques for Continuous-Queries on Moving Objects［J］.IEEE Transactions on Computers，2002，51(10):1124-1140.

［4］Patel J，Chen Y，Chakka V.STRIPES:An efficient index for predicted trajectories［C］//Processdings of the International Conference on Management of Data，Paris，France，2004:635-646.

［5］Tao Yufei，Sun Jimeng，Papadias Dimitris.Selectively estimation for predictive spatio-temporal queries［C］.ICDE2003，Bangalore，India，2003.

［6］Jimeny Sun，Dimitris Papadias，Yufei Tao，et al.Querying about the past，the present，and the future in spatio-temporal［C］.Toronto，Canada:ICDE，2004:202-213.

［7］Cheqing Jin ，Weibin Guo ，Futong Zhao.Getting qualified answers for aggregate queries in spatio-temporal databases［C］.Proceeding of 9th APWEB and 8th WAIM.Heidelberg:Springer Berlin，2007:220-227.

［8］何茂顺，董一鸿，付世昌.移动对象预测聚集范围查询方法［J］.计算机工程与应用，2011，47(9):130-133.