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

1、人類(lèi)社會(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)用戶(hù)的定位技術(shù)和設(shè)備也在迅速普及，極大地推動(dòng)了基于位置的服務(wù)迅速發(fā)展。 各種定位設(shè)備不斷產(chǎn)生并積累海量的、包含移動(dòng)對(duì)象時(shí)空信息的數(shù)據(jù)，對(duì)基于時(shí)間和位置信息的時(shí)空數(shù)據(jù)庫(kù)的要求越來(lái)越迫切，成為近期被廣為研究的技術(shù)。傳統(tǒng)的估算器估算查詢(xún)結(jié)果的大小，查詢(xún)優(yōu)化器利用估算的結(jié)果大小來(lái)確定執(zhí)行查詢(xún)的有效辦法。由于

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

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