24873.分布式并行計(jì)算環(huán)境下gml空間數(shù)據(jù)的劃分策略及算法研究

1、I摘要摘要GML具有簡(jiǎn)單性、半結(jié)構(gòu)化、互操作性、開放性、通用性、靈活性等特點(diǎn)，因而在諸多領(lǐng)域得到了廣泛應(yīng)用。隨著地理信息領(lǐng)域求解問題的不斷拓展，所遇到的問題也越來(lái)越復(fù)雜，規(guī)模越來(lái)越大，傳統(tǒng)GIS的空間數(shù)據(jù)存儲(chǔ)與空間分析算法的效率優(yōu)化和性能提升無(wú)法滿足海量數(shù)據(jù)的存儲(chǔ)與空間運(yùn)算需求。利用分布式并行計(jì)算平臺(tái)可以很好地解決這一問題。分布式并行系統(tǒng)的優(yōu)劣很大程度取決于數(shù)據(jù)劃分策略的好壞，而目前空間數(shù)據(jù)的劃分方法沒有考慮空間關(guān)聯(lián)關(guān)系。因此針對(duì)一種適

2、合GML空間數(shù)據(jù)的綜合考慮負(fù)載平衡、鄰近程度、面積平衡及空間關(guān)聯(lián)關(guān)系的空間數(shù)據(jù)劃分方法，本文取得了以下研究成果：第一，研究分析了基于Hilbert空間排列碼的空間數(shù)據(jù)劃分和基于K平均聚類算法的空間數(shù)據(jù)劃分兩種算法的缺點(diǎn)。前者在保持各結(jié)點(diǎn)的空間數(shù)據(jù)所占范圍平衡性上表現(xiàn)不佳，而后者則由于初始質(zhì)心的不確定性導(dǎo)致劃分結(jié)果不穩(wěn)定。第二，結(jié)合Hilbert空間排列碼和K平均聚類算法，并綜合考慮對(duì)象的空間關(guān)聯(lián)關(guān)系提出一種新的GML數(shù)據(jù)劃分算法。該算法

3、考慮了各結(jié)點(diǎn)負(fù)載平衡、對(duì)象的鄰近程度、面積平衡及對(duì)象間的空間關(guān)聯(lián)關(guān)系。最后，根據(jù)提出的GML空間數(shù)據(jù)劃分算法，分析設(shè)計(jì)了GML分布式存儲(chǔ)系統(tǒng)，完成了基于Hadoop平臺(tái)的分布式并行GML存儲(chǔ)系統(tǒng)的數(shù)據(jù)劃分模塊。通過(guò)系統(tǒng)驗(yàn)證了數(shù)據(jù)劃分算法的負(fù)載平衡性，并與acleSpatial和基于K平均聚類的空間數(shù)據(jù)劃分算法的并行加速比做了比較分析，與Hilbert碼劃分算法做了等分區(qū)域查詢效率對(duì)比。結(jié)果表明，本劃分算法擁有良好的負(fù)載平衡性和優(yōu)秀的并行

4、查詢效率。關(guān)鍵詞：關(guān)鍵詞：GML分布式計(jì)算并行計(jì)算數(shù)據(jù)劃分HadoopIII目錄目錄摘要........................................................................IAbstract...................................................................II目錄........................

5、..............................................III第一章緒論...............................................................11.1研究背景及意義....................................................11.2國(guó)內(nèi)外研究現(xiàn)狀.............................

6、.......................11.2.1國(guó)內(nèi)外分布式并行計(jì)算研究現(xiàn)狀..................................11.2.2國(guó)內(nèi)外分布式空間數(shù)據(jù)劃分的研究現(xiàn)狀............................41.2.3國(guó)內(nèi)外GML空間數(shù)據(jù)存儲(chǔ)研究現(xiàn)狀................................41.3本文的主要內(nèi)容...........................

7、.........................5第二章分布式并行計(jì)算與GML概述...........................................62.1分布式并行計(jì)算概述................................................62.1.1分布式計(jì)算....................................................62.1.2并行計(jì)算.

8、.....................................................72.1.3分布式并行計(jì)算的應(yīng)用..........................................82.2分布式并行計(jì)算關(guān)鍵技術(shù)............................................82.2.1網(wǎng)格計(jì)算關(guān)鍵技術(shù)....................................

9、..........82.2.2云計(jì)算關(guān)鍵技術(shù)................................................92.3分布式并行數(shù)據(jù)庫(kù).................................................102.4GML概述...........................................................112.4.1GML概念.......

10、...............................................112.4.2GML的主要模式................................................122.4.3GML空間數(shù)據(jù)特征..............................................142.4.4GML數(shù)據(jù)解析..................................

11、................15第三章分布式并行計(jì)算環(huán)境下GML空間數(shù)據(jù)的劃分............................163.1Hilbert空間排列碼.................................................163.1.1Hilbert碼描述................................................163.1.2Hilbert碼在空間數(shù)據(jù)

12、劃分中的應(yīng)用..............................173.2K平均聚類算法....................................................173.2.1算法描述.....................................................173.2.2算法在空間數(shù)據(jù)劃分中的應(yīng)用...................................1