多重近似空間索引及其相關(guān)檢索技術(shù)研究.pdf

1、當(dāng)前，GIS應(yīng)用日益廣泛和深入，空間數(shù)據(jù)量也日益增多，這就需要作為GIS核心的空間數(shù)據(jù)庫(kù)系統(tǒng)具有快速的檢索能力，而空間數(shù)據(jù)索引是空間數(shù)據(jù)庫(kù)系統(tǒng)的關(guān)鍵技術(shù)之一，它的好壞直接影響到空間數(shù)據(jù)庫(kù)性能的優(yōu)劣，也直接影響著空間數(shù)據(jù)庫(kù)的檢索性能。國(guó)內(nèi)外眾多學(xué)者提出了各類空間索引技術(shù)，他們主要集中在從算法優(yōu)化的角度去提高空間數(shù)據(jù)的檢索性能，但其檢索性能提高的空間很有限。針對(duì)這一問(wèn)題，本文在前人有關(guān)空間數(shù)據(jù)索引及空間數(shù)據(jù)檢索的研究基礎(chǔ)上，以空間換時(shí)間的策

2、略，利用空間對(duì)象的多重近似圖形構(gòu)建空間索引，并基于該索引進(jìn)行相關(guān)空間數(shù)據(jù)檢索，為更大限度的提高空間數(shù)據(jù)檢索能力提供一個(gè)新的研究思路與方法。
　　 基于以上的研究問(wèn)題與研究思路，本文依托“海量空間數(shù)據(jù)的多重近似索引方法研究”項(xiàng)目開展了研究工作，并取得了一定的理論研究成果，即該索引方法能在窗口、方向、鄰近距離及半連接等檢索上獲得更好的效率，從而為GIS系統(tǒng)在海量空間數(shù)據(jù)中能進(jìn)行更高效的檢索提供了一種新的索引方法。
　　 首先

3、，論文討論了空間數(shù)據(jù)的特點(diǎn)、空間數(shù)據(jù)庫(kù)的關(guān)鍵技術(shù)以及空間對(duì)象間的拓?fù)?、距離以及方向關(guān)系，分析了空間對(duì)象的外部和內(nèi)部近似表達(dá)，然后將傳統(tǒng)索引中只利用空間對(duì)象的外部近似擴(kuò)展為既有空間對(duì)象的外部近似又有空間對(duì)象的內(nèi)部近似，即以空間對(duì)象的多重近似來(lái)構(gòu)建索引，并以R-tree 為索引原型構(gòu)建基于多重近似的MR-tree和MRD-tree索引結(jié)構(gòu)，然后給出了相關(guān)索引的插入、刪除及查找算法，并通過(guò)實(shí)驗(yàn)比較分析了基于多重近似索引與基于外部近似索引的構(gòu)建

4、效率及窗口范圍查詢效率。另外，在建立基于多重近似索引過(guò)程中，討論了空間對(duì)象的內(nèi)部近似表達(dá)的最大內(nèi)接圓和最大內(nèi)接矩形的幾種求解算法及其效率。
　　 其次，論文在基于多重近似索引基礎(chǔ)上，探討了方向關(guān)系檢索、距離關(guān)系檢索以及距離方向半連接的方法與性能。即：1）在方向關(guān)系矩陣模型、開域方向模型基礎(chǔ)上，討論了基于多重近似索引下的定性與定量方向檢索方法，并通過(guò)實(shí)驗(yàn)對(duì)基于多重近似索引與外部近似索引下的方向檢索效率進(jìn)行了對(duì)比分析；2）詳細(xì)討論了

5、各種距離度量方法，提出了基于多重近似索引下的點(diǎn)、線、面的最鄰近查詢和反最鄰近查詢算法，并通過(guò)實(shí)驗(yàn)對(duì)基于多重近似索引與外部近似索引下的最鄰近查詢和反最鄰近查詢效率進(jìn)行比較分析；3）介紹了半連接的基本概念，探討了距離關(guān)系、方向關(guān)系以及空間對(duì)象數(shù)量的約束模型，給出了基于多重近似索引下的距離方向半連接實(shí)現(xiàn)方法，并通過(guò)實(shí)驗(yàn)對(duì)基于多重近似索引與外部近似索引下的距離方向半連接的效率進(jìn)行了比較分析。實(shí)驗(yàn)表明：基于多重近似索引在構(gòu)建時(shí)比基于外部近似索引效