基于aTPRA-tree的移動對象預(yù)測范圍聚集查詢算法研究

牛言濤，何茂順，姚玉霞

(1.吉林農(nóng)業(yè)大學(xué)發(fā)展學(xué)院，長春 130600;2.寧波大學(xué) 計算機科學(xué)技術(shù)研究所，寧波 315211)

0 引言

Ine’s等［1］綜述了PRA(Predictive Range Aggregate，PRA)查詢方法，PRA是移動對象數(shù)據(jù)庫中的一種重要的查詢類型之一。當(dāng)前，PRA查詢方法主要有兩種:一是精確聚集，如采用 TPR-tree［2］、VCI R-tree［3］和STRIPE［4］索引等。二是近似查詢，如 STH 技術(shù)［5］、SAMH 方法［6］和 AMH*［7］等。

以上方法由于沒有考慮移動對象在時空域上的特殊性，TPR-tree索引隨著時間的推移，性能將逐漸惡化，結(jié)點面積和結(jié)點重疊面積將逐漸增大，導(dǎo)致查詢性能下降。文獻［8］基于PRA-tree提出aTPRA-tree索引結(jié)構(gòu)，本文基于aTPRA-tree給出預(yù)測范圍聚集查詢定理和算法。通過該剪枝算法加速了查詢的過程，提高了預(yù)測范圍聚集查詢的性能和效率。

2 aTPRA-tree索引結(jié)構(gòu)

aTPRA-tree［8］(The aggregation TPR-tree based on the Angle，aTPRA-tree)(如圖1)沿用 TPR-tree 的索引結(jié)構(gòu)，但在TPR-tree的索引結(jié)點結(jié)構(gòu)中增加了聚集信息。

圖1 aTPRA-tree索引結(jié)構(gòu)

3 aTPRA-tree聚集查詢算法

廖巍等［2］提出了一種剪裁不需要訪問結(jié)點的方法，即定理1。本文提出aTPRA-tree剪枝定理和算法，使得相對于定理1更快速判斷出其結(jié)點是否要被訪問。先給出兩個定義:

定義1 TPBR(Time-Parameterized Bounding Rectangle，TPBR)運動趨勢點.在TPBR的四個頂點中，與TPBR基準(zhǔn)點相對角的頂點稱為TPBR運動趨勢點。

定義2 TPBR決定點(Decision Points，DB).在TPBR的四個頂點中，除了TPBR基準(zhǔn)點和TPBR運動趨勢點之外的另外兩個頂點稱為TPBR決定點。

示例圖2，TPBR的運動趨勢點為頂點b，決定點DB為頂點a和d，查詢qT即為矩形B。

圖2 TPBR與查詢窗口的拓?fù)鋱D

aTPRA-tree剪枝定理給定中間索引結(jié)點的某個TPBR和PRA查詢q(qR，qT)，若TPBR決定點在查詢窗口qT內(nèi)落在查詢qR中，則該索引結(jié)點下的子樹中所有移動對象都將會在查詢窗口qT內(nèi)落在查詢qR中，則此時PRA查詢算法只需返回該結(jié)點的聚集信息即可。證明:

不妨假設(shè)，a在將來落在B中的時刻記做ta，d落在B中的時刻記做td，且ta＞td。在td時刻，d在邊gh之上且在邊f(xié)h之右，由于頂點c和d在一條線上，則c也在邊gh之上且在邊f(xié)h之右，此時頂點a在邊ef之下，同理，c也在邊ef之下。而等到了ta時刻，頂點a在邊eg之右，在邊f(xié)h之左，且在邊ef之下，則c此時也在邊eg之右，在邊f(xié)h之左，且在邊ef之下。由于頂點c在td時刻已在邊gh之上，且cd邊沒有向下的速度，則ta時刻頂點c也在邊gh之上，這樣在ta時刻頂點c也落在矩形B中。

同理，可以證出頂點b在td時刻也落在矩形B中。根據(jù)定理1［2］，可知該索引結(jié)點下的子樹的所有移動對象在查詢窗口qT中都會落在矩形B內(nèi)，則在PRA中，返回該結(jié)點的聚集信息即可。

證畢。

結(jié)合aTPRA-tree剪枝定理，給定aTPRA-tree的線性鏈表L，聚集查詢結(jié)果Agg(q)以及聚集函數(shù)Count函數(shù)。給出算法如下:

4 實驗評估

本實驗采用的模擬數(shù)據(jù)生成器與文獻［8］相同，生成100K和10K的數(shù)據(jù)若干組，進行實驗。角度區(qū)間數(shù)目表示aNum設(shè)置為8。qRlen(查詢空間窗口大小)分別固定為100×100，300×300，600×600，900×900，1200×1200，1500×1500，而此時的qTlen(查詢時間窗口大小)設(shè)定為20。接著，設(shè)定qRlen為900×900，qTlen分別為10、20、30、50、80、100，分別進行20次窗口查詢實驗，且分別設(shè)置100K和10K的數(shù)據(jù)量。

圖3顯示了aTPRA-tree在qTlen大小一致而qRlen不同的情況下(qTlen為20)，平均讀寫次數(shù)比同等條件下的TPR-tree性能要好。圖4顯示了在不同的qTlen情況下，aTPRA-tree的性能優(yōu)于TPR-tree(qRlen為900×900)。同理，圖5和圖6顯示了在數(shù)據(jù)量為10K的情況下，aTPRA-tree也比TPR-tree查詢性能好很多。

圖3 aTPRA-tree與TPR-tree查詢性能比較1(100K)

圖5 aTPRA-tree與TPR-tree查詢性能比較1(10K)

5 結(jié)語

圖4 aTPRA-tree與TPR-tree查詢性能比較2(100K)

圖6 aTPRA-tree與TPR-tree查詢性能比較2(10K)

本文在aTPRA-tree索引結(jié)構(gòu)基礎(chǔ)上，提出了aTPRA-tree剪枝定理和算法。通過該剪枝定理加速了查詢的過程，提高了預(yù)測范圍聚集查詢的性能，實驗數(shù)據(jù)證明了此方法的有效性。

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

［2］廖巍，景寧，鐘志農(nóng)，等.面向移動對象的高效預(yù)測范圍聚集查詢方法［J］.計算機研究與發(fā)展，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，F(xiàn)rance，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 ，F(xiàn)utong 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］何茂順，董一鴻，付世昌.移動對象預(yù)測聚集范圍查詢方法［J］.計算機工程與應(yīng)用，2011，47(9):130-133.