云環(huán)境下空間大數(shù)據(jù)連接查詢處理算法的研究與實現(xiàn).pdf

1、隨著對地觀測技術(shù)和位置服務(wù)技術(shù)的快速發(fā)展，空間數(shù)據(jù)規(guī)模急劇增加，已成為大空間數(shù)據(jù)，如何利用云計算對這類數(shù)據(jù)進(jìn)行高效的空間連接查詢處理，是當(dāng)前空間數(shù)據(jù)管理領(lǐng)域的研究熱點之一?，F(xiàn)有的基于MapReduce的空間連接查詢處理算法，如PPBSM等存在過濾能力弱、數(shù)據(jù)過度復(fù)制等問題，并且計算后還需要進(jìn)行重復(fù)避免，這樣帶來了額外的CPU和I/O代價。為此，本文針對空間連接查詢存在的問題，進(jìn)行了深入研究，主要做了以下幾方面的工作。
　　首先，針

2、對現(xiàn)有MapReduce空間連接查詢處理算法存在的過度復(fù)制等問題，提出了兩種空間連接查詢優(yōu)化算法，即基于過濾的空間連接查詢優(yōu)化算法(FBSJ)和基于網(wǎng)格擴(kuò)充的空間連接優(yōu)化算法(GEBSJ)。FBSJ算法利用經(jīng)過收縮的內(nèi)部網(wǎng)格的MBR過濾掉部分無用的跨分區(qū)單元對象，降低了Reduce階段的計算代價。GEBSJ算法采用基于R-tree的網(wǎng)格索引來過濾無用連接對象，并減少連接對象的多余復(fù)制。該算法利用一類數(shù)據(jù)預(yù)處理擴(kuò)充原始網(wǎng)格并構(gòu)建網(wǎng)格索引，

3、另外一類數(shù)據(jù)搜索網(wǎng)格索引進(jìn)行數(shù)據(jù)復(fù)制，這樣會降低數(shù)據(jù)的復(fù)制量同時無需重復(fù)避免，分別從CPU和I/O角度優(yōu)化了算法。
　　其次，提出了一種改進(jìn)的基于分布式R*樹索引的空間連接查詢處理算法。本文引入分布式R*樹并對其進(jìn)行了改進(jìn)，首先按照Hilbert空間填充曲線編碼使得空間區(qū)域數(shù)據(jù)實現(xiàn)均勻劃分，并在每個分區(qū)中構(gòu)建局部R*樹索引，然后利用這些分布式R*樹索引構(gòu)建一個全局索引信息文件。在進(jìn)行連接計算時，如果兩類數(shù)據(jù)集都存在索引，則利用全局

4、索引信息文件生成任務(wù)隊列，然后執(zhí)行基于R*樹的連接查詢處理;如果只有一類數(shù)據(jù)集存在索引，則充分利用該索引信息將無索引數(shù)據(jù)復(fù)制分配到各個子索引所在的Reducer任務(wù)上并行構(gòu)建索引，然后再執(zhí)行基于R*樹的連接查詢處理。由于分布式索引的存在，相對于處理無索引數(shù)據(jù)的PPBSM算法，查詢性能最高能提升38.5％。
　　最后，通過實際數(shù)據(jù)集和合成數(shù)據(jù)集上的大量實驗，對本文所提出的兩類空間連接查詢處理算法進(jìn)行了測試分析。實驗結(jié)果表明，本文所提