隨著空間數(shù)據(jù)的規(guī)模急劇增加,空間索引成為影響空間數(shù)據(jù)檢索性能的關(guān)鍵因素。近年來,計算機處理器的發(fā)展趨勢正從高主頻的單核處理器轉(zhuǎn)向片上多處理器（CMP, Chip Multi-Processor）,從依靠指令級的并行轉(zhuǎn)向線程級并行。并行計算模式正越來越受到重視,同時也得到了許多實際應(yīng)用,為提升空間索引批量加載性能提供了新的硬件環(huán)境。研究者對基于R-樹的批量加載技術(shù)做了大量的研究,面向多核處理器環(huán)境對算法并行化的工作也正成為研究熱點。本文在深入分析國內(nèi)外空間索引結(jié)構(gòu)和并行計算技術(shù)的基礎(chǔ)上,就以下內(nèi)容進行了研究:1)空間索引并行批量加載代價模型分析了動態(tài)R-樹的生成過程及算法,并歸納了動態(tài)算法在海量數(shù)據(jù)索引方面的性能問題,然后闡述了R-樹靜態(tài)批量加載的過程及相關(guān)算法,分析在面向空間查詢應(yīng)用中該方法的性能優(yōu)勢。建立了空間索引并行批量加載代價模型,為構(gòu)建高效的查詢執(zhí)行計劃提供理論依據(jù)。2)空間索引并行批量加載算法基于Hilbert R-樹索引構(gòu)建算法,分析其在多核處理器結(jié)構(gòu)上的可并行性,設(shè)計并實現(xiàn)了索引并行批量加載算法,提高了在片上多處理器架構(gòu)上空間索引的加載效率。通過實驗,從運行時間、并行效率... 

【文章來源】：國防科技大學湖南省 211工程院校 985工程院校

【文章頁數(shù)】：73 頁

【學位級別】：碩士

【部分圖文】：

圖1.1兩層R-樹示例

分調(diào)動片上多處理器的計算優(yōu)勢，首先需要根據(jù)多核處理器編程模型，并在此基礎(chǔ)上分析傳統(tǒng)串行算法的可并行性以及數(shù)、數(shù)據(jù)劃分、內(nèi)存和 Cache 大小等因素，建立算法并行優(yōu)寫高效的并行算法。對多核處理器硬件結(jié)構(gòu)，在 Hilbert R-樹靜態(tài)批量加載算法基行批量加載算法，充分利用多核計算資源，提高索引的構(gòu)建檢索速度。2.2 R-樹的構(gòu)建方法前最常用的一種空間數(shù)據(jù)訪問方法，R-樹是 B-樹在多維空間它也是一顆高度平衡的樹。R-樹種存儲的不是對象本身，而形(MBR)，所有 MBR 的邊與一個全局坐標系的軸平行，如圖每一個結(jié)點都跟磁盤文件中的一頁相對應(yīng)，因此在進行空間對很少的結(jié)點進行搜索，而不用對所有結(jié)點進行遍歷，大大索性能[26]。

圖 2.2 兩種不同的處理方案本課題基于片上多處理器(CMP)設(shè)計空間索引并行批量加載算法，以實現(xiàn)快速高效的索引構(gòu)建�？紤]空間索引并行批量加載的代價模型，需要分析在索引構(gòu)建過程中多方面因素的影響，如 CPU 核數(shù)、CPU 計算效率、I/O 代價、頁面大小、內(nèi)存大小和數(shù)據(jù)內(nèi)存交換時間等等。通過對空間索引批量加載算法的研究，索引靜態(tài)批量加載的時間損耗主要決定于對空間對象的外部排序代價。例如在 Hilbert R-樹算法中，空間對象就是依據(jù)對應(yīng)的 Hilbert 值進行排列，然后再一次性的構(gòu)建 R-樹，即首先生成大量最底層的結(jié)點，然后再生成倒數(shù)第二層結(jié)點，直至只剩下最后一個根結(jié)點為止。實驗證明，系統(tǒng)中能夠使用的主存大小非常關(guān)鍵，這也是我們在代價模型中考慮的因素之一。表 2.1 列出了在建立代價模型過程中用到的變量。表 2.1 代價模型中的變量說明變量 定義D 數(shù)據(jù)空間的維度NcoreCPU 中的核數(shù)T磁盤上每個頁面的 I/O 時間

【參考文獻】：
期刊論文
[1]支持多線程的空間數(shù)據(jù)GSQL解析器設(shè)計與實現(xiàn)[J]. 張震,王超,熊偉,雷霖,景寧.  計算機應(yīng)用研究. 2011(02)
[2]三維Hilbert曲線在圖像置亂中的應(yīng)用[J]. 萬里紅,孫燮華,林旭亮.  計算機工程. 2011(02)
[3]應(yīng)用GPU集群加速計算蛋白質(zhì)分子場[J]. 張繁,王章野,姚建,吳韜,彭群生.  計算機輔助設(shè)計與圖形學學報. 2010(03)
[4]空間數(shù)據(jù)的訪問方法與查詢技術(shù)研究[J]. 樸英花.  電腦知識與技術(shù). 2010(03)
[5]開源GIS進展及其典型應(yīng)用研究[J]. 胡慶武,陳亞男,周洋,熊成利.  地理信息世界. 2009(01)
[6]基于多核集群系統(tǒng)的并行編程模型的研究[J]. 胡晨駿,王曉蔚.  計算機技術(shù)與發(fā)展. 2008(04)
[7]多核微機基于OpenMP的并行計算[J]. 蔡佳佳,李名世,鄭鋒.  計算機技術(shù)與發(fā)展. 2007(10)
[8]基于SMP集群系統(tǒng)的并行編程模式研究與分析[J]. 宋偉,宋玉.  計算機技術(shù)與發(fā)展. 2007(02)
[9]R樹家族的演變和發(fā)展[J]. 張明波,陸鋒,申排偉,程昌秀.  計算機學報. 2005(03)
[10]空間數(shù)據(jù)引擎關(guān)鍵技術(shù)與應(yīng)用分析[J]. 張明波,申排偉,陸鋒,程昌秀.  地球信息科學. 2004(04)

碩士論文
[1]空間數(shù)據(jù)庫規(guī)則技術(shù)研究[D]. 張震.國防科學技術(shù)大學 2010
[2]基于空間數(shù)據(jù)庫的柵格數(shù)據(jù)存儲管理關(guān)鍵技術(shù)研究[D]. 王超.國防科學技術(shù)大學 2009
[3]基于多核系統(tǒng)的內(nèi)存管理研究[D]. 何進仙.電子科技大學 2009
[4]基于R-樹的空間數(shù)據(jù)索引技術(shù)的研究與實現(xiàn)[D]. 周帆.哈爾濱理工大學 2009
[5]空間索引技術(shù)研究[D]. 張廳.中南大學 2007
[6]基于Linux的地理空間數(shù)據(jù)管理系統(tǒng)設(shè)計與實現(xiàn)[D]. 朱進.浙江大學 2007
[7]基于R樹的空間索引技術(shù)的研究與應(yīng)用[D]. 付偉.四川大學 2006
[8]面向空間數(shù)據(jù)庫引擎的空間索引系統(tǒng)[D]. 陳鎮(zhèn)虎.北京工業(yè)大學 2002



本文編號：3143290