[發(fā)明專(zhuān)利]一種面向空間數(shù)據(jù)連接操作的分布式數(shù)據(jù)存取方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410444716.0
• 申請(qǐng)日: 2014-09-03
• 公開(kāi)（公告）號(hào): CN104239469B
• 公開(kāi)（公告）日: 2017-09-19
• 發(fā)明（設(shè)計(jì)）人: 陸佳民;馮鈞
• 申請(qǐng)（專(zhuān)利權(quán)）人: 河海大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 南京蘇高專(zhuān)利商標(biāo)事務(wù)所(普通合伙)32204
• 代理人: 李玉平

技術(shù)領(lǐng)域

本發(fā)明涉及一種面向空間數(shù)據(jù)連接操作的分布式數(shù)據(jù)存取方法，屬于信息技術(shù)處理領(lǐng)域。

背景技術(shù)

空間數(shù)據(jù)的連接操作是指發(fā)現(xiàn)符合一定空間關(guān)系（覆蓋、鄰近、包含等）的空間對(duì)象二元組，一般分為兩個(gè)步驟：過(guò)濾與精化。前者利用空間數(shù)據(jù)的概要進(jìn)行來(lái)發(fā)現(xiàn)符合查詢(xún)要求的候選集，而后者則利用空間對(duì)象的高精度形狀數(shù)據(jù)來(lái)進(jìn)行比較，以得到最終的連接結(jié)果。在基于MapReduce并行處理模式進(jìn)行空間連接操作時(shí)，Map階段需用于對(duì)空間對(duì)象進(jìn)行粗粒度聚類(lèi)，而上述兩個(gè)步驟都則只可以在Reduce階段完成，因此需要將所有非過(guò)濾候選集的空間對(duì)象數(shù)據(jù)也通過(guò)網(wǎng)絡(luò)進(jìn)行遠(yuǎn)程存取，產(chǎn)生大量不必要的代價(jià)。

非過(guò)濾候選集的空間數(shù)據(jù)的遠(yuǎn)程存取代價(jià)構(gòu)成了面向分布式環(huán)境的空間數(shù)據(jù)連接連接操作的一個(gè)技術(shù)難點(diǎn)。

目前面向分布式環(huán)境的數(shù)據(jù)遠(yuǎn)程存取的方法主要有：Jeffrey Dean 和 Sanjay Ghemawat提出的MapReduce并行處理模式，闡述了并行化環(huán)境下數(shù)據(jù)處理的標(biāo)準(zhǔn)流程與體系結(jié)構(gòu)，為實(shí)現(xiàn)空間數(shù)據(jù)連接操作提供了良好的基礎(chǔ)。在此基礎(chǔ)上由Apache基金會(huì)實(shí)現(xiàn)的Hadoop平臺(tái)則成為主流的并行處理平臺(tái)，所有數(shù)據(jù)按照鍵-值對(duì)的形式存儲(chǔ)在分布式文件系統(tǒng)HDFS，并在需要時(shí)進(jìn)行遠(yuǎn)程存取（Dean, J. & Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters Proceedings of the 6th Symposium on Operating Systems Design & Implementation - Volume 6, USENIX Association, 2004）。Shubin Zhang等在MapReduce并行處理模式的基礎(chǔ)上對(duì)空間數(shù)據(jù)的并行化連接操作進(jìn)行了實(shí)現(xiàn)，由于過(guò)濾與精化均在Reduce階段進(jìn)行處理，因此通過(guò)HDFS對(duì)全體空間對(duì)象數(shù)據(jù)進(jìn)行遠(yuǎn)程讀?。╖hang, S.； Han, J.； Liu, Z.； Wang, K. & Xu, Z. SJMR: Parallelizing Spatial Join With MapReduce on Clusters Cluster Computing and Workshops, 2009）。Jens Dittrich等人在HDFS基礎(chǔ)上，建立了Hadoop++系統(tǒng)，對(duì)所有存儲(chǔ)在HDFS上的文件建立內(nèi)部索引。盡管沒(méi)有減少遠(yuǎn)程存取的數(shù)據(jù)量，但在對(duì)數(shù)據(jù)進(jìn)行讀取后，借由內(nèi)部索引可以加快本地?cái)?shù)據(jù)的讀取速度（Dittrich, J.； Quiane-Ruiz, J.； Jindal, A.； Kargin, Y.； Setty, V. & Schad, J. Hadoop++: Making A Yellow Elephant Run Like A Cheetah (Without It Even Noticing) Proceedings of the VLDB Endowment, 2010）。Yongqiang He等提出了列式分布存儲(chǔ)結(jié)構(gòu)，將關(guān)系數(shù)據(jù)表中的每一列作為HDFS中的獨(dú)立模塊進(jìn)行遠(yuǎn)程存取，減小了關(guān)系數(shù)據(jù)操作中對(duì)于無(wú)關(guān)數(shù)據(jù)的存取代價(jià)（He, Y.； Lee, R.； Huai, Y.； Shao, Z.； Jain, N.； Zhang, X. & Xu, Z. RCFile: A fast and space-efficient data placement structure in MapReduce-based warehouse systems Data Engineering (ICDE), 2011 IEEE 27th International Conference on, 2011）。

目前，涉及到分布式環(huán)境下數(shù)據(jù)遠(yuǎn)程存取的方法在針對(duì)空間數(shù)據(jù)對(duì)象進(jìn)行連接操作時(shí)，均需對(duì)全體對(duì)象的高精度形狀數(shù)據(jù)進(jìn)行遠(yuǎn)程存取。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問(wèn)題是針對(duì)上述背景技術(shù)的不足，提供了一種面向空間數(shù)據(jù)連接操作的分布式數(shù)據(jù)存取方法。

本發(fā)明為實(shí)現(xiàn)上述發(fā)明目的采用如下技術(shù)方案：

步驟1，對(duì)給定的分布式空間數(shù)據(jù)樣本進(jìn)行抽樣，進(jìn)而制定出多維空間內(nèi)的細(xì)粒度網(wǎng)格結(jié)構(gòu)，方法如下:

步驟1-1，對(duì)于分布在并行數(shù)據(jù)庫(kù)內(nèi)，以?xún)蓚€(gè)關(guān)系數(shù)據(jù)表形式所存儲(chǔ)的空間數(shù)據(jù)進(jìn)行樣本抽??；