空間數(shù)據(jù)庫(kù)中移動(dòng)對(duì)象位置管理技術(shù)研究.pdf

1、隨著移動(dòng)技術(shù)進(jìn)步和移動(dòng)應(yīng)用深入生活,移動(dòng)對(duì)象規(guī)模及由其產(chǎn)生的信息量急速增長(zhǎng),促使移動(dòng)對(duì)象數(shù)據(jù)庫(kù)迅猛發(fā)展。作為提升移動(dòng)對(duì)象數(shù)據(jù)庫(kù)查詢(xún)效率的關(guān)鍵技術(shù),移動(dòng)對(duì)象索引結(jié)構(gòu)及其相應(yīng)算法的優(yōu)劣直接影響到應(yīng)用的性能表現(xiàn)。由于移動(dòng)對(duì)象新特性使得傳統(tǒng)數(shù)據(jù)庫(kù)的索引結(jié)構(gòu)不能被直接繼承使用,新的移動(dòng)對(duì)象索引結(jié)構(gòu)不斷被提出,大致可分為管理移動(dòng)對(duì)象的過(guò)去信息歷史信息索引和管理移動(dòng)對(duì)象近期及未來(lái)信息的預(yù)測(cè)查詢(xún)索引兩大類(lèi)別。但是,移動(dòng)對(duì)象索引技術(shù)還沒(méi)有達(dá)到可以進(jìn)行大規(guī)

2、模商用的程度,移動(dòng)對(duì)象索引的性能還需要進(jìn)一步提高。通過(guò)對(duì)移動(dòng)對(duì)象的數(shù)據(jù)特性的研究,總結(jié)了移動(dòng)對(duì)象管理的難點(diǎn),結(jié)合前人的工作,提出了高效的索引結(jié)構(gòu)和相關(guān)算法。
　　首先,針對(duì)移動(dòng)對(duì)象查詢(xún)過(guò)程中出現(xiàn)的候選查詢(xún)范圍過(guò)大問(wèn)題,提出了基于時(shí)間域、速度域和空間域的多域劃分技術(shù),其中時(shí)間域提供處理移動(dòng)性的能力,速度域劃分負(fù)責(zé)縮減候選查詢(xún)范圍,空間域劃分結(jié)合空間填充曲線(xiàn)完成高維位置屬性一維化。多域劃分使得每個(gè)劃分對(duì)應(yīng)的查詢(xún)候選范圍大幅減小,從而獲

3、得較小的移動(dòng)對(duì)象候選集,減小了查詢(xún)耗費(fèi)。在多域劃分的基礎(chǔ)上,設(shè)計(jì)實(shí)現(xiàn)了移動(dòng)點(diǎn)狀對(duì)象索引MPB-tree。以該結(jié)構(gòu)為平臺(tái),證明了多域劃分的可行性和有效性,驗(yàn)證了對(duì)于多域劃分的定性和定量推理,得到了關(guān)于最佳多域劃分參數(shù)的計(jì)算方法。MPB-tree使用空間填充曲線(xiàn)結(jié)合空間域劃分將高維移動(dòng)對(duì)象一維化,其中空間填充曲線(xiàn)的秩對(duì)索引效率有直接影響。通過(guò)對(duì)查詢(xún)過(guò)程中節(jié)點(diǎn)訪(fǎng)問(wèn)問(wèn)題進(jìn)行研究,推導(dǎo)出MPB-tree中空間填充曲線(xiàn)秩與多域劃分參數(shù)之間的關(guān)系,設(shè)

4、計(jì)了自適應(yīng)的空間填充曲線(xiàn)秩,提出了以此為基礎(chǔ)的自適應(yīng)移動(dòng)點(diǎn)狀對(duì)象管理機(jī)制。
　　其次,針對(duì)移動(dòng)多邊形對(duì)象形狀不規(guī)則、拓?fù)浜途嚯x計(jì)算復(fù)雜度高的問(wèn)題,提出使用基于時(shí)間參數(shù)化外包矩形和時(shí)間參數(shù)化多重內(nèi)接圓的多重時(shí)間參數(shù)化近似表達(dá)來(lái)分別對(duì)移動(dòng)多邊形的內(nèi)外邊界進(jìn)行擬合。多重時(shí)間參數(shù)化近似表達(dá)能夠在索引的葉子節(jié)點(diǎn)入口中代替移動(dòng)對(duì)象,參與更新與查詢(xún)過(guò)程,完成組織和過(guò)濾任務(wù)。提出了基于多重時(shí)間參數(shù)化近似表達(dá)的M2TPR-tree及其相應(yīng)算法,驗(yàn)證

5、了多重時(shí)間參數(shù)化近似表達(dá)在擬合移動(dòng)多邊形對(duì)象方面的優(yōu)勢(shì)。多重時(shí)間參數(shù)化近似表達(dá)會(huì)引起葉子節(jié)點(diǎn)入口尺寸增大,引起索引高度的增長(zhǎng),導(dǎo)致索引結(jié)構(gòu)性能退化。根據(jù)時(shí)間參數(shù)化多重內(nèi)接圓不參與結(jié)構(gòu)組織的特點(diǎn),提出使用單獨(dú)的哈希結(jié)構(gòu)對(duì)其進(jìn)行管理,在不影響查詢(xún)性能的同時(shí)解決了索引退化問(wèn)題。針對(duì)TPR*-tree周期性整體重建引起的服務(wù)不連續(xù),采用時(shí)間域劃分策略,以時(shí)間域上的多子樹(shù)交替更新代替周期性整體重建,提高了索引結(jié)構(gòu)的可用性。
　　另外,本文還

6、針對(duì)基于位置服務(wù)中最常見(jiàn)的kNN查詢(xún)進(jìn)行了特別的研究。在點(diǎn)狀移動(dòng)數(shù)據(jù)查詢(xún)方面,提出了基于MPB-tree的半徑迭代算法,利用多域劃分的優(yōu)勢(shì),提高了點(diǎn)狀移動(dòng)對(duì)象kNN查詢(xún)的效率。移動(dòng)多邊形對(duì)象的kNN查詢(xún)方面,提出基于多重時(shí)間參數(shù)化近似表達(dá)分支界限算法。通過(guò)研究移動(dòng)點(diǎn)、TPBR和TPMultiEC之間的空間關(guān)系及距離計(jì)算,得到了基于TPBR和TPMultiEC的分支界限查詢(xún)距離度量。通過(guò)低誤差的距離度量,索引結(jié)構(gòu)遍歷過(guò)程中的剪枝效果得到大