時(shí)空數(shù)據(jù)庫中移動(dòng)查詢的選擇性估算算法.pdf

1、人類社會(huì)活動(dòng)的“移動(dòng)性”是移動(dòng)通信、移動(dòng)互聯(lián)網(wǎng)、移動(dòng)定位服務(wù)、移動(dòng)商務(wù)等重大應(yīng)用得以發(fā)展的內(nèi)在動(dòng)因。隨著移動(dòng)通信向第三代的演變，移動(dòng)用戶的定位技術(shù)和設(shè)備也在迅速普及，極大地推動(dòng)了基于位置的服務(wù)迅速發(fā)展。 各種定位設(shè)備不斷產(chǎn)生并積累海量的、包含移動(dòng)對象時(shí)空信息的數(shù)據(jù)，對基于時(shí)間和位置信息的時(shí)空數(shù)據(jù)庫的要求越來越迫切，成為近期被廣為研究的技術(shù)。傳統(tǒng)的估算器估算查詢結(jié)果的大小，查詢優(yōu)化器利用估算的結(jié)果大小來確定執(zhí)行查詢的有效辦法。由于

2、它在查詢執(zhí)行前運(yùn)行，估算器估算結(jié)果的準(zhǔn)確性成為衡量一種估算器的重要標(biāo)準(zhǔn)。時(shí)空數(shù)據(jù)庫研究對象是時(shí)空數(shù)據(jù)，不同于關(guān)系型數(shù)據(jù)庫中的非時(shí)空數(shù)據(jù)，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫估算查詢結(jié)果大小的方法在時(shí)空數(shù)據(jù)庫中已經(jīng)不適用了。為了解決這一問題，構(gòu)造用來估算時(shí)空查詢結(jié)果大小的估算器已經(jīng)成為時(shí)空數(shù)據(jù)庫研究的難點(diǎn)和熱點(diǎn)。 現(xiàn)有的時(shí)空查詢的估算器主要有采樣法估算器、直方圖類估算器和帶參數(shù)技術(shù)估算器等，研究發(fā)現(xiàn)大多數(shù)估算器都存在構(gòu)建時(shí)間代價(jià)高，處理查詢類型少，

3、估算精度低等缺點(diǎn)。針對這些不足，本文提出了一種新的、基于代價(jià)模型的選擇性估算算法。該算法需改造TPR-樹索引結(jié)構(gòu)，通過改造TPR-樹，使節(jié)點(diǎn)內(nèi)的移動(dòng)對象相對速度最小，減小了葉子節(jié)點(diǎn)的時(shí)空偏斜度。用改造后的TPR-樹節(jié)點(diǎn)內(nèi)的移動(dòng)對象來構(gòu)建估算器的直方圖，減少構(gòu)建直方圖的時(shí)間代價(jià)。并保持查詢窗口與移動(dòng)對象運(yùn)動(dòng)關(guān)系不變，把移動(dòng)對象的動(dòng)態(tài)查詢、靜態(tài)對象的動(dòng)態(tài)查詢、移動(dòng)對象的靜態(tài)查詢等多種查詢類型轉(zhuǎn)化為移動(dòng)對象的靜態(tài)查詢類型，簡化估算過程，提高估