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

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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊亞飛;鄭丹晨;韓敏;;一種基于多尺度輪廓點(diǎn)空間關(guān)系特征的形狀匹配方法[J];自動(dòng)化學(xué)報(bào);2015年08期

2 吳明光;;一種空間分布模式驅(qū)動(dòng)的空間索引[J];測(cè)繪學(xué)報(bào);2015年01期

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

4 陳鵬;周旋珍;陳瑞鑫;;空間對(duì)象多級(jí)網(wǎng)格索引有效性的數(shù)學(xué)證明[J];軟件導(dǎo)刊;2013年12期

5 劉潤(rùn)濤;陳琳琳;田廣悅;;Z曲線網(wǎng)格劃分的最近鄰查詢[J];計(jì)算機(jī)工程與應(yīng)用;2013年22期

6 嚴(yán)蔚敏;李冬梅;吳偉民;;數(shù)據(jù)結(jié)構(gòu)(C語言版)[J];計(jì)算機(jī)教育;2012年12期

7 周瑜;劉俊濤;白翔;;形狀匹配方法研究與展望[J];自動(dòng)化學(xué)報(bào);2012年06期

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

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

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

相關(guān)博士學(xué)位論文 前4條

1 崔登吉;空間分布模式驅(qū)動(dòng)的空間數(shù)據(jù)組織與索引研究[D];南京師范大學(xué);2016年

2 林偉華;多重近似空間索引及其相關(guān)檢索技術(shù)研究[D];華中科技大學(xué);2009年

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

4 趙仁亮;基于Voronoi圖的空間關(guān)系計(jì)算研究[D];中南大學(xué);2002年

相關(guān)碩士學(xué)位論文 前10條

1 蔡報(bào)豐;形狀匹配中的若干關(guān)鍵問題研究[D];南昌航空大學(xué);2016年

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

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

4 李曉;基于上下文的形狀匹配算法研究與實(shí)現(xiàn)[D];華中師范大學(xué);2012年

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

6 王貴玲;基于新型R~*Q-樹空間數(shù)據(jù)索引結(jié)構(gòu)的研究[D];河南理工大學(xué);2009年

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

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

9 吳元洪;空間索引技術(shù)及其應(yīng)用研究[D];重慶大學(xué);2003年

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

本文編號(hào)：2701010