基于RQOP樹(shù)空間數(shù)據(jù)索引技術(shù)的研究.pdf

1、數(shù)字城市及數(shù)字地球技術(shù)正一步步走向成熟，百度地圖、谷歌地圖等應(yīng)用軟件一步步走進(jìn)我們的生活，地理信息系統(tǒng)的重要性日益顯現(xiàn)?？臻g數(shù)據(jù)索引技術(shù)在地理信息系統(tǒng)（GIS）中有著重要地位。它的好壞直接決定了整個(gè)地理信息系統(tǒng)系統(tǒng)的性能。研究空間數(shù)據(jù)結(jié)構(gòu)以尋找更好的空間數(shù)據(jù)索引方法，一直是眾多學(xué)者不懈努力的目標(biāo)，因此對(duì)它的研究有著理論和實(shí)際的雙重意義。
　　RQOP樹(shù)作為空間數(shù)據(jù)樹(shù)，是通過(guò)定義最小外包矩形(MBR)的排序關(guān)系，利用這些排序關(guān)系對(duì)空

2、間目標(biāo)數(shù)據(jù)進(jìn)行劃分為四叉樹(shù)的形式，使得樹(shù)高度平衡。傳統(tǒng)的R樹(shù)解決了空間數(shù)據(jù)搜索的功能，而RQOP樹(shù)結(jié)合了R樹(shù)的優(yōu)點(diǎn)，進(jìn)一步提高了空間數(shù)據(jù)的搜索效率。深入研究改進(jìn)RQOP樹(shù)對(duì)提高空間數(shù)據(jù)處理有積極作用。
　　本文研究 R樹(shù)的變種—RQOP樹(shù)的空間數(shù)據(jù)索引方法，以獲取更高性能的空間數(shù)據(jù)索引機(jī)制為目標(biāo)。根據(jù)數(shù)據(jù)之間的關(guān)系，對(duì)RQOP樹(shù)進(jìn)行結(jié)構(gòu)上的重組，使樹(shù)形更加緊湊。由于RQOP樹(shù)相對(duì)與其他R樹(shù)、CF樹(shù)等檢索速度更快，因此研究改進(jìn)RQO

3、P樹(shù)，以提升搜索速度，以及減少的存儲(chǔ)空間占用成為本文的主要目的。
　　本文以空間物體的最小外包矩形(Minimum Bounding Rectangle)為近似表達(dá)方式，以獲得具有較高性能的空間數(shù)據(jù)索引結(jié)構(gòu)為目標(biāo)，通過(guò)定義空間目標(biāo)間的排序關(guān)系并利用這些排序關(guān)系對(duì)數(shù)據(jù)空間的劃分方法進(jìn)行探討。
　　本文對(duì)如何建立含包含關(guān)系的空間數(shù)據(jù)四分劃方法深入研究，在原 RQOP樹(shù)的基礎(chǔ)上改進(jìn)劃分規(guī)則，采取新的規(guī)則后，分別用最小覆蓋、最小重疊

4、的四分劃方法構(gòu)建出新的RQOP樹(shù)。使實(shí)體數(shù)據(jù)不只存在于最底層，其包含關(guān)系能在樹(shù)狀結(jié)構(gòu)中能得到體現(xiàn)。減少子葉節(jié)點(diǎn)，使整體結(jié)構(gòu)更為緊湊，并用實(shí)驗(yàn)證明新的劃分方法的先進(jìn)性。并根據(jù)改進(jìn)后的RQOP樹(shù)，闡述了改進(jìn)后的節(jié)點(diǎn)插入、刪除、合并等算法。
　　以上述研究為基礎(chǔ)，給出了一種基于RQOP樹(shù)改進(jìn)的新空間數(shù)據(jù)索引結(jié)構(gòu)，該結(jié)構(gòu)中對(duì)于中間節(jié)點(diǎn)的利用提出優(yōu)化方案；設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)實(shí)驗(yàn)驗(yàn)證系統(tǒng)原型。通過(guò)該系統(tǒng)驗(yàn)證表明其對(duì)于提高檢索效率有較高的可行性。