牛言濤，何茂順，姚玉霞

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

0 引言

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

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

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é)點(diǎn)結(jié)構(gòu)中增加了聚集信息。

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

3 aTPRA-tree聚集查詢算法

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

定義1 TPBR(Time-Parameterized Bounding Rectangle，TPBR)運(yùn)動(dòng)趨勢(shì)點(diǎn).在TPBR的四個(gè)頂點(diǎn)中，與TPBR基準(zhǔn)點(diǎn)相對(duì)角的頂點(diǎn)稱為TPBR運(yùn)動(dòng)趨勢(shì)點(diǎn)。

定義2 TPBR決定點(diǎn)(Decision Points，DB).在TPBR的四個(gè)頂點(diǎn)中，除了TPBR基準(zhǔn)點(diǎn)和TPBR運(yùn)動(dòng)趨勢(shì)點(diǎn)之外的另外兩個(gè)頂點(diǎn)稱為TPBR決定點(diǎn)。

示例圖2，TPBR的運(yùn)動(dòng)趨勢(shì)點(diǎn)為頂點(diǎn)b，決定點(diǎn)DB為頂點(diǎn)a和d，查詢qT即為矩形B。

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

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

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

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

證畢。

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

4 實(shí)驗(yàn)評(píng)估

本實(shí)驗(yàn)采用的模擬數(shù)據(jù)生成器與文獻(xiàn)［8］相同，生成100K和10K的數(shù)據(jù)若干組，進(jìn)行實(shí)驗(yàn)。角度區(qū)間數(shù)目表示aNum設(shè)置為8。qRlen(查詢空間窗口大小)分別固定為100×100，300×300，600×600，900×900，1200×1200，1500×1500，而此時(shí)的qTlen(查詢時(shí)間窗口大小)設(shè)定為20。接著，設(shè)定qRlen為900×900，qTlen分別為10、20、30、50、80、100，分別進(jìn)行20次窗口查詢實(shí)驗(yàn)，且分別設(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ù)測(cè)范圍聚集查詢的性能，實(shí)驗(yàn)數(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)，等.面向移動(dòng)對(duì)象的高效預(yù)測(cè)范圍聚集查詢方法［J］.計(jì)算機(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］何茂順，董一鴻，付世昌.移動(dòng)對(duì)象預(yù)測(cè)聚集范圍查詢方法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(9):130-133.