大規(guī)模空間數(shù)據(jù)的高性能查詢處理關(guān)鍵技術(shù)研究.pdf

1、對地觀測、GIS和傳感器網(wǎng)絡(luò)等空間數(shù)據(jù)獲取技術(shù)的革命性進步、存儲器價格的顯著下降以及人們希望從空間數(shù)據(jù)中獲取知識等客觀需求，催生了大數(shù)據(jù)，空間數(shù)據(jù)管理技術(shù)迎來了大數(shù)據(jù)時代。傳統(tǒng)的并行計算和空間數(shù)據(jù)庫技術(shù)在應(yīng)對容量大、類型多樣的空間查詢處理和分析挑戰(zhàn)時，遇到了可擴展性差、支持類型單一等困難。近年來，Map Red uce技術(shù)異軍突起，通過集群上的分布式并行計算獲得良好的系統(tǒng)性能，并以高度的可擴展性，滿足不斷增長的數(shù)據(jù)量的處理需求，成為大數(shù)

2、據(jù)分析的主流技術(shù)之一。因此，結(jié)合MapRed uce技術(shù)進行大規(guī)模空間數(shù)據(jù)的高性能查詢處理成為一種發(fā)展趨勢。最近以來，這一方向已經(jīng)引起國內(nèi)外學(xué)者的注意，開展了初步研究并取得了一定的成果，但為了取得更好的查詢效果并滿足實際應(yīng)用需求，在關(guān)鍵空間查詢算法設(shè)計及性能優(yōu)化等方面均存在進一步探索的巨大空間。本文從實際需求出發(fā)，借鑒傳統(tǒng)的并行空間查詢算法和空間數(shù)據(jù)庫技術(shù)，結(jié)合MapRed uce并行計算模型的特點，從以下四個方面對大規(guī)?？臻g數(shù)據(jù)的高性

3、能查詢處理技術(shù)開展了研究：
　　1．并行計算模型抽象與空間數(shù)據(jù)建模
　　為指導(dǎo)MapRed uce框架下并行空間查詢算法的設(shè)計，對并行計算模型和數(shù)據(jù)存儲模型進行了研究。首先，利用無依賴并行和串行同步計算的形式化定義抽象了MapRed uce并行編程模型，采用分階段方法對各個階段的代價模型進行分析；其次，針對MapRed uce框架下空間數(shù)據(jù)的存儲需求，在分析空間數(shù)據(jù)信息模型和空間數(shù)據(jù)對象-關(guān)系存儲模型的基礎(chǔ)上，設(shè)計了空間數(shù)據(jù)

4、的key-va lue存儲模型并進行了實現(xiàn)。
　　2．空間數(shù)據(jù)索引的并行構(gòu)建
　　針對大規(guī)?？臻g數(shù)據(jù)R-樹索引的構(gòu)建需求，提出了基于Hilbert曲線和隨機采樣的并行空間劃分函數(shù)生成方法，利用生成的空間劃分函數(shù)，使得大規(guī)模空間數(shù)據(jù)的R-樹索引構(gòu)建符合MapRed uce無依賴并行和串行同步的計算抽象，并設(shè)計了并行處理階段的算法，最后從負載均衡、構(gòu)建效率和構(gòu)建質(zhì)量等方面實驗驗證算法的可行性和高效性；其次，針對大規(guī)模批量遙感影像

5、瓦片金字塔索引的構(gòu)建需求，基于全球瓦片金字塔模型，提出一種基于分辨率和空間范圍自動匹配的瓦片金字塔索引的生成方法，詳細設(shè)計了Map階段瓦片并行生成和Red uce階段瓦片并行合并處理方法，并提出了一種過濾優(yōu)化方法，最后實驗驗證了算法的高效性和可擴展性。
　　3．空間數(shù)據(jù)的并行連接聚集查詢
　　在面向大規(guī)?？臻g數(shù)據(jù)的空間連接查詢上，用戶經(jīng)常需要連接查詢中的統(tǒng)計聚集信息。對此，提出了MapRed uce框架下兩種不同條件下的并行

6、連接聚集算法。首先，針對非索引條件下的并行空間連接聚集問題，提出了一種MapRed uce框架下的過濾合并(Map-Reduce-Filter-Merge，MRFM)方法，Map階段利用空間網(wǎng)格將整個空間連接聚集任務(wù)劃分為無關(guān)聯(lián)的任務(wù)子集，Red uce階段則對每個任務(wù)執(zhí)行部分聚集的空間連接聚集操作，F(xiàn)ilte r階段對單次分配空間對象的連接聚集結(jié)果進行過濾操作，然后Merge階段對多次分配空間對象的連接聚集結(jié)果進行合并。其次，將R-樹

7、索引引入到空間連接聚集操作中，利用分布式R-樹來索引大規(guī)?？臻g數(shù)據(jù)并生成任務(wù)集，然后利用任務(wù)連通圖進行任務(wù)劃分，使其符合無依賴并行計算模型，并設(shè)計了Map和Red uce階段的并行處理算法，比非索引的空間連接聚集操作更加自然，并且性能得到提升。
　　4．空間數(shù)據(jù)的并行k近鄰連接查詢
　　MapRed uce框架下處理 k近鄰連接查詢的核心在于數(shù)據(jù)的劃分，現(xiàn)有方法主要采用數(shù)據(jù)塊的劃分方法，但執(zhí)行時間隨數(shù)據(jù)規(guī)模的增長呈平方項增長