【摘要】：空間索引是依據空間對象的位置和形狀或空間對象之間的某種空間關系按一定順序排列的一種數據結構,旨在快速篩選與特定空間操作無關的空間對象,是確保高效搜索和展示空間數據效率的重要指標,其性能的優(yōu)劣直接影響地理信息系統(tǒng)與空間數據庫的整體性能。目前,國內外涌現出各類空間索引結構,盡管他們從不同角度對空間索引算法進行了優(yōu)化,但仍存在很大的局限性。其中,在索引樹結構方面,節(jié)點間較高的空間重疊度,造成索引樹深度的增加、同一空間查詢出現多條查詢路徑等一系列弊端,從而降低了空間索引質量,影響空間索引性能。而且隨著數據量和數據類型復雜程度的劇增以及索引數據的不斷更新,這類弊端也愈發(fā)明顯�？臻g對象近似(SpatialObjectApproximation)精度較低,是導致索引節(jié)點間較大重疊度的一個重要問題。通過使用相關空間目標近似技術(如最小外接矩形)可減少原始空間目標復雜的空間關系計算,從而提高空間查詢效率。地理信息系統(tǒng)處理的空間目標具有不規(guī)則的幾何形狀(如道路、河流等),若直接利用其精確空間位置來實現某些給定的空間操作(如相交、包含等),計算量會急劇增加。但現有方法未挖掘空間目標的幾何形態(tài)特征,導致索引節(jié)點間存在較高的空間重疊度,進而影響空間查詢性能的提升。針對上述問題,本文以優(yōu)化空間索引結構為目標,從空間目標近似技術出發(fā),結合線、面地理矢量要素的幾何形態(tài)特征,提出了基于幾何模板(Geometric Template)近似的空間索引優(yōu)化方法,其中幾何模板是指以柵格方式對原始幾何對象進行粗略近似的圖形。并設計相關空間數據檢索實驗,實驗表明了該空間索引優(yōu)化方法明顯提高了窗口查詢與空間連接查詢效率與精度。本文具體研究內容與成果如下:(1)面向二維空間索引優(yōu)化的幾何模板針對空間對象近似精度不高、難以平衡索引樹構建效率及空間復雜度等的問題,本文提出了基于多級網格剖分的幾何模板構建方案。定義了以網格數據結構為基礎的幾何模板結構,設計了基于改進最小編輯距離和幾何模板頻率直方圖的歸類算法、基于圖形字典的幾何模板位編碼算法以及基于位操作和幾何模板空間關系預取的混合機制下的空間關系粗計算策略。(2)基于幾何模板近似的空間索引優(yōu)化方法鑒于R*樹是R-樹變體中應用最為廣泛的一類,本文以R*樹為例,提出了基于幾何模板近似的空間索引優(yōu)化方法,旨在將幾何模板替換R*樹中的最小外接矩形,以達到優(yōu)化的目的。通過對比分析基于幾何模板近似和基于最小外接矩形近似下空間索引數據構建、刪除、窗口查詢和空間連接查詢以及節(jié)點分裂等算法的差異性。本文提出了基于幾何模板空間關系粗計算的窗口查詢與空間連接查詢詳細算法。設計了基于幾何模板變換(起點變換、級別變換)和位運算的節(jié)點分裂算法,構造了基于幾何模板類型和級別的面積、周長計算方法,以此為基礎,最終提出了基于幾何模板近似的空間索引構建和刪除算法。(3)設計原型系統(tǒng)進行實驗驗證通過選擇中國區(qū)域內有代表性的線和面狀OSM(Open Street Map)矢量數據集,本文構建了 VGIS原型系統(tǒng),從窗口查詢效率、精度和存儲空間壓縮比方面,對提出的基于幾何模板近似的空間索引優(yōu)化方法進行實驗分析。結果表明,基于幾何模板近似的空間索引優(yōu)化方法以增加少量建樹時間,換取更少的窗口查詢與空間連接查詢時間以及存儲空間占用量,提高了空間查詢性能和空間利用率,且擴展了查詢謂詞。
【圖文】：

Ｒ－Ｆｉｌｅ邋（Ｈｕｔｆｌｅｓｚ邋ｅｔａｌ．，１９９０）、ＭｕｌｔｉＬａｙｅｒ邋Ｇｒｉｄ邋Ｆｉｌｅ邋（Ｓｉｘ邋ｅｔ邋ａｌ．，１９８８）、網格索引逡逑（ＧＵｎｔｈｅｒｅｔａｌ．，１９８９；胡久鄉(xiāng)等，２００２）。此類索引在進行空間檢索時，首先計算逡逑出查詢對象所在的網格，然后在候選網格中快速查詢空間目標。如圖１－１所示。逡逑Ｒ標映射技術邐目標復制技術邐目標近似技術邐基于分層技術逡逑！點對筆更高丨丨邐°邐Ｉ：邐最小外丨丨邐罕ｔａｔＪｃ逡逑；＇——晙邋Ａ點邋｜丨丨邋｜Ｔ｜７｜邐：：邋＾邋Ａ邋＾邋ｈｉ邋ｒＭ邐；逡逑ＩＥ｝－邐５邐ｌ：ｉ邋Ｓ邋—士邋ｉ逡逑：區(qū)｝＾邋ＩＩ邐Ｙ３ＤＨ一邋基本網格邋ｉ逡逑Ｉ邐邐邐邐—邐邐１＿邐—邐邐－逡逑圖ｉ－ｉ空間索引分類逡逑目前，眾多國內外研究學者針對各類空間索引的不足，從不同角度提出了一逡逑些改進策略，主要包括：在空間劃分方面，一方面引入了空間聚類方法如！＾逡逑ＭＥＡＮ邋（Ｋａｎｕｎｇｏｅｔａｌ．，２００２）及其改進結構（胡偉，２００３）、Ｃｈａｍｅｌｅｏｎ邋（Ｋａｒｙｐｉｓ逡逑ｅｔ邋ａｌ．，邋２００２）、Ａｌｅｘ邋（Ｒｏｄｒｉｇｕｅｚ邋ｅｔ邋ａｌ．，２０１４）等以及邋Ｖｏｒｏｎｏｉ邋（周培德，１９９９），代逡逑表的有聚類Ｒ－樹（黃繼先，２００５；余冬梅，２０１２；崔環(huán)宇，，２０１６）、ＨＣＲ索引（黃繼逡逑先，２００６）、ＰａｔｔｅｒｎＬｉｓｔ邋（崔登吉，２０１６）等，另一方面，從空間分布模式角度出發(fā)，逡逑針對不同分布模式米用不同處理策略，代表的有Ｐａｔｔｅｒｎ－ｔｒｅｅ空間索引（吳明光，逡逑２０１５）；在空間目標近似方面

可以有效地提高空間操作的速度和效率。因此，針對無空間索引支持的連接操作逡逑難以滿足應用需求，本文將不予討論。逡逑空間連接與其他空間查詢相同，通常分為兩部分：過濾和求精，如圖１－３所逡逑／Ｊｎ邋0逡逑｜邐逡逑Ｍ邋選祺邋ｊ－—ｊ（Ｔ）逡逑ｄＤ７＾．邋Ｌ＿邐逡逑圖１－３空間連接處理流程（Ｂｒｉｎｋｈｏｆｆｅｔａｌ．，邋１９９４）逡逑如圖１－３所示，ＢｒｉｎｋｈｏｆｆＴ．等人提出的空間連接的三步體系主要分為三個步逡逑驟（Ｂｒｉｎｋｈｏｆｆ邋ｅｔ邋ａｌ．，１９９４）。逡逑（１）
【學位授予單位】：南京師范大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：P208

【參考文獻】

相關期刊論文 前10條

1 楊亞飛;鄭丹晨;韓敏;;一種基于多尺度輪廓點空間關系特征的形狀匹配方法[J];自動化學報;2015年08期

2 吳明光;;一種空間分布模式驅動的空間索引[J];測繪學報;2015年01期

3 戴晶;吳明光;鄭培蓓;王蕾;崔登吉;陳泰生;;基于Hilbert曲線的STR索引改進算法[J];武漢大學學報(信息科學版);2014年07期

4 陳鵬;周旋珍;陳瑞鑫;;空間對象多級網格索引有效性的數學證明[J];軟件導刊;2013年12期

5 劉潤濤;陳琳琳;田廣悅;;Z曲線網格劃分的最近鄰查詢[J];計算機工程與應用;2013年22期

6 嚴蔚敏;李冬梅;吳偉民;;數據結構(C語言版)[J];計算機教育;2012年12期

7 周瑜;劉俊濤;白翔;;形狀匹配方法研究與展望[J];自動化學報;2012年06期

8 余冬梅;;基于K-Means聚類的R-樹空間索引方法研究與分析[J];科技導報;2012年11期

9 牛慶肖;張樺;徐光平;薛彥兵;;基于鏈碼和快速傅里葉變換的輪廓描繪方法[J];光電子.激光;2011年12期

10 裘曉峰;熊偉;蔡蕾;吳燁;陳宏盛;;基于Hilbert R樹的空間連接算法Cache性能分析[J];現代電子技術;2011年21期

相關博士學位論文 前4條

1 崔登吉;空間分布模式驅動的空間數據組織與索引研究[D];南京師范大學;2016年

2 林偉華;多重近似空間索引及其相關檢索技術研究[D];華中科技大學;2009年

3 黃繼先;基于R-樹的空間數據庫查詢技術研究[D];中南大學;2005年

4 趙仁亮;基于Voronoi圖的空間關系計算研究[D];中南大學;2002年

相關碩士學位論文 前10條

1 蔡報豐;形狀匹配中的若干關鍵問題研究[D];南昌航空大學;2016年

2 崔環(huán)宇;基于改進聚類的R樹索引方法研究[D];哈爾濱理工大學;2016年

3 康建玲;基于鏈碼和形狀上下文的形狀描述與匹配的研究[D];吉林大學;2013年

4 李曉;基于上下文的形狀匹配算法研究與實現[D];華中師范大學;2012年

5 田慧貞;一種基于STR R-tree空間索引的研究[D];電子科技大學;2012年

6 王貴玲;基于新型R~*Q-樹空間數據索引結構的研究[D];河南理工大學;2009年

7 李楊;基于最小邊界圓和最小包圍扇形的空間索引方法[D];哈爾濱理工大學;2009年

8 蔡浴泓;空間數據庫索引技術的研究與探索[D];華東師范大學;2008年

9 吳元洪;空間索引技術及其應用研究[D];重慶大學;2003年

10 陳鎮(zhèn)虎;面向空間數據庫引擎的空間索引系統(tǒng)[D];北京工業(yè)大學;2002年

本文編號：2701010