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

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

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

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

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