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

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

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

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

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

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

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