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

【文章來(lái)源】：國(guó)防科技大學(xué)湖南省 211工程院校 985工程院校

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖1.1兩層R-樹示例

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

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

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

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



本文編號(hào)：3143290