基于MapRedue的大規(guī)模矢量空間數(shù)據(jù)選擇查詢處理

何濤++劉強(qiáng)++鄭澤忠++劉帥

摘 要：為高效地處理大規(guī)模矢量空間數(shù)據(jù)，基于Hadoop的并行計(jì)算框架MapRedue，實(shí)現(xiàn)了一種分布式的矢量空間數(shù)據(jù)選擇查詢處理方法。首先，分析OGC簡單要素標(biāo)準(zhǔn)與Hadoop的Key/Value數(shù)據(jù)模型，設(shè)計(jì)了可存儲(chǔ)于Hadoop HDFS的矢量文件格式；其次，根據(jù)兩階段的過濾-精煉策略，對Map 輸入數(shù)據(jù)分片、選擇查詢處理過程及Reduce結(jié)果合并等關(guān)鍵步驟進(jìn)行了詳細(xì)闡述；最后，基于上述技術(shù)，利用Hadoop集群環(huán)境對所提出的方法進(jìn)行驗(yàn)證，該方法具有較好的可行性和較高的效率。

關(guān)鍵詞：MapRedue 選擇查詢 存儲(chǔ)模型 Key/Value 矢量數(shù)據(jù)文件

中圖分類號(hào)： 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）03（c）-0193-02

隨著全球空間數(shù)據(jù)集的急劇增長，海量空間數(shù)據(jù)帶來了豐富的信息，而面對如此龐大和復(fù)雜的數(shù)據(jù)集，隨之產(chǎn)生了數(shù)據(jù)存儲(chǔ)與管理問題。國內(nèi)外很多學(xué)者嘗試?yán)肏adoop云計(jì)算技術(shù)處理矢量空間數(shù)據(jù)。張書彬等利用MapReduce并行處理空間查詢的數(shù)據(jù)分割方法、副本避免方法實(shí)現(xiàn)空間查詢[1]；趙彥榮等基于Hadoop提出了一種并行連接查詢算法CHMJ[2]，提高了連接查詢的處理效率；尹芳等基于開源Hadoop 的矢量空間數(shù)據(jù)分布式處理研究[3]；王永剛對Hadoop云計(jì)算平臺(tái)下地理信息服務(wù)的若干關(guān)鍵技術(shù)進(jìn)行了研究[4]。

基于上述研究，該文以Hadoop分布式文件系統(tǒng)存儲(chǔ)矢量空間數(shù)據(jù)，根據(jù)空間查詢處理的兩階段過濾與精煉策略，并充分利用MapRedue并行計(jì)算框架處理海量數(shù)據(jù)的優(yōu)勢，設(shè)計(jì)一種簡單實(shí)用的選擇查詢方法，有效提高了對大規(guī)模矢量空間數(shù)據(jù)的查詢處理效率。

1 基本概念

1.1 空間選擇查詢

在GIS中，常見的對空間矢量數(shù)據(jù)的查詢有三種，即：空間選擇查詢、空間連接查詢和最近鄰查詢。其中，空間選擇查詢和連接查詢是最基本的查詢操作?？臻g選擇查詢是最重要的一種空間查詢操作，它能夠作為其他空間查詢操作（如空間連接查詢和最近鄰查詢）的基礎(chǔ)。代表性的空間選擇查詢包括空間點(diǎn)查詢和空間區(qū)域查詢。點(diǎn)查詢（Point Query）通過給定一個(gè)查詢點(diǎn)P和一個(gè)空間對象集M，查找出M中所有包含點(diǎn)P的空間對象。區(qū)域查詢通過給定一個(gè)多邊形區(qū)域R和一個(gè)空間對象集M，查找出M中所有與R相交或被R包含的空間對象。

1.2 MapReduce并行計(jì)算框架

Hadoop是一款開源分布式系統(tǒng)基礎(chǔ)架構(gòu)，它支持在商用硬件構(gòu)建的大型集群上運(yùn)行應(yīng)用程序，實(shí)現(xiàn)對海量數(shù)據(jù)的分布式處理。其核心技術(shù)包括并行計(jì)算框架MapReduce和分布式文件系統(tǒng)HDFS，分別是Google MapReduce和GFS的開源實(shí)現(xiàn)。MapReduce是一種并行計(jì)算的編程模型，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運(yùn)算。

2 基于MapReduce的空間選擇查詢

2.1 矢量數(shù)據(jù)存儲(chǔ)模型

目前，開放地理信息聯(lián)盟OGC（Open Geospatial Consortium）制定了許多與空間信息、基于位置服務(wù)相關(guān)的標(biāo)準(zhǔn)，其中簡單要素模型（圖1）是OGC最為重要的幾何對象模型。簡單要素幾何對象中主要定義了點(diǎn)、線、面和集合對象。通過將空間對象與空間參考系進(jìn)行關(guān)聯(lián)，空間對象被抽象表達(dá)為空間參考系統(tǒng)（Spatial Reference System）所描述的幾何體（Geometry）。大多數(shù)空間關(guān)系及空間分析都基于這個(gè)類層次體系進(jìn)行研究，并且平臺(tái)是獨(dú)立的，可以應(yīng)用到分布式計(jì)算系統(tǒng)[5]。該文中同樣采用簡單要素模型來存儲(chǔ)矢量數(shù)據(jù)。

2.2 HDFS矢量數(shù)據(jù)文件

在OGC簡單要素模型中，可以采用WKT（Well-Known Text）和WKB（Well-Known Binary）兩種編碼方式表示幾何對象。WKT通過文本來描述幾何對象和空間參考，而WKB通過二進(jìn)制字節(jié)形式描述空間對象。由于HDFS不直接支持矢量數(shù)據(jù)結(jié)構(gòu)，矢量數(shù)據(jù)需要進(jìn)行轉(zhuǎn)化后才能在Hadoop中使用。Hadoop非常擅長處理非結(jié)構(gòu)化文本數(shù)據(jù)，默認(rèn)使用文本作為輸入，因此本文采用WKT來描述矢量空間對象，利用開源GeoTools-2.7.5工具包，設(shè)計(jì)了一種便于在hadoop中分布式存儲(chǔ)的矢量數(shù)據(jù)文件，如圖1。

在矢量數(shù)據(jù)文件中，每一行表示一個(gè)空間對象。通過HDFS來存儲(chǔ)和管理矢量數(shù)據(jù)文件，就是直接將創(chuàng)建的矢量數(shù)據(jù)文件上傳到HDFS文件系統(tǒng)，然后HDFS對其進(jìn)行自動(dòng)分片，生成大量的數(shù)據(jù)塊（缺省為64M），分別存儲(chǔ)到不同的節(jié)點(diǎn)上。

2.3 MapReduce矢量數(shù)據(jù)選擇查詢方法

由于空間查詢多為計(jì)算密集型操作，為了提高查詢效率，本文采用兩階段的過濾-精煉算法。第一階段過濾，將空間對象用其最小外包矩形表示，當(dāng)查詢區(qū)域?yàn)榫匦螘r(shí)，兩個(gè)矩形是否相交最多只需要4次判斷就能確定，過濾后得到候選集。第二階段精煉，通過對候選集使用精確的幾何條件和屬性條件判斷，最終獲得符合查詢要求的空間對象集。

在map函數(shù)中，從HDFS矢量數(shù)據(jù)文件依次讀取空間對象，經(jīng)過過濾階段和精煉階段的篩選，reduce函數(shù)將滿足查詢條件的空間對象集輸出到HDFS文件系統(tǒng)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

實(shí)驗(yàn)平臺(tái)使用1臺(tái)計(jì)算機(jī)作為宿主機(jī)，安裝VMware9虛擬機(jī)，同時(shí)虛擬出3臺(tái)相同的計(jì)算機(jī)。三臺(tái)虛擬機(jī)分別安裝Linux操作系統(tǒng)，并部署Hadoop-1.0.0構(gòu)成分布式處理集群，其中一臺(tái)同時(shí)作為master節(jié)點(diǎn)和slave節(jié)點(diǎn)，另外兩臺(tái)作為slave節(jié)點(diǎn)。宿主機(jī)：CPU：AMD 5200+，內(nèi)存：4.00 GB，操作系統(tǒng)：win7（64位），開發(fā)環(huán)境：eclipse3.7.1；虛擬機(jī)：操作系統(tǒng)均為Ubuntu-11.10-desktop-i386，內(nèi)存：512 MB。實(shí)驗(yàn)數(shù)據(jù)：矢量數(shù)據(jù)（數(shù)據(jù)量：168MB，133099個(gè)線空間對象），格式：ESRI Shapefile文件。

3.2 矢量數(shù)據(jù)查詢實(shí)驗(yàn)

由空間選擇查詢算法可知，實(shí)驗(yàn)步驟如下：（1）將矢量數(shù)據(jù)存入HDFS；（2）選取查詢窗口；（3）執(zhí)行基于MapReduce的矢量數(shù)據(jù)過濾-精煉算法；（4）查詢結(jié)果寫入HDFS（圖2）。

從實(shí)驗(yàn)結(jié)果可以得出，第一，當(dāng)集群中節(jié)點(diǎn)數(shù)目相同時(shí)，隨著查詢數(shù)據(jù)量的增大，查詢時(shí)間變長，是因?yàn)椴樵兇翱诎瑪?shù)據(jù)條數(shù)增加，使得過濾-精煉過程的開銷也相應(yīng)變大。第二，對于同一個(gè)查詢窗口，集群中節(jié)點(diǎn)數(shù)量增加，查詢時(shí)間依次減小，其原因是Hadoop中默認(rèn)塊大小是64MB，HDFS上文件通常是按照64MB被切分為不同的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊盡可能分散存儲(chǔ)在不同數(shù)據(jù)節(jié)點(diǎn)中，并且每塊對應(yīng)一個(gè)Map任務(wù)，因此168MB的矢量數(shù)據(jù)對應(yīng)3個(gè)Map任務(wù)，隨著節(jié)點(diǎn)數(shù)增加，任務(wù)執(zhí)行的并行程度提高，當(dāng)節(jié)點(diǎn)數(shù)為3時(shí)，3個(gè)Map任務(wù)可以實(shí)現(xiàn)并行執(zhí)行，查詢窗口1，2，3相對于單節(jié)點(diǎn)的查詢效率分別提高了13.3%、16.3%和15.08%。

4 結(jié)語

該文根據(jù)hadoop的分布式存儲(chǔ)特點(diǎn)和矢量數(shù)據(jù)的存儲(chǔ)模型，設(shè)計(jì)一種適合hadoop存儲(chǔ)的矢量數(shù)據(jù)文件，通過對矢量數(shù)據(jù)MapReduce處理流程的分析，實(shí)現(xiàn)基于hadoop過濾-精煉算法的矢量數(shù)據(jù)的選擇查詢方法，通過實(shí)驗(yàn)，驗(yàn)證了本文提出方法的正確性和有效性。下一步，將研究基于MapRedue的大規(guī)模矢量空間數(shù)據(jù)連接查詢處理方法。

參考文獻(xiàn)

[1] 張書彬，韓冀中，劉志勇，等.基于MapReduce實(shí)現(xiàn)空間查詢的研究[J]. 高技術(shù)通訊，2010，20（7）：719-726.

[2] 趙彥榮，王偉平，孟丹，等.基于Hadoop的高效連接查詢處理算法CHMJ[J].軟件學(xué)報(bào)，2012（4）：124.

[3] 尹芳，馮敏，諸云強(qiáng)，等，基于開源Hadoop 的矢量空間數(shù)據(jù)分布式處理研究[J].計(jì)算機(jī)工程與應(yīng)用，2013（16）.

[4] 王永剛.基于Hadoop云計(jì)算平臺(tái)的地理信息服務(wù)若干關(guān)鍵技術(shù)研究[D].北京：中國科學(xué)院研究生院遙感應(yīng)用研究，2011.

[5] 范建永，龍明，熊偉.基于HBase的矢量空間數(shù)據(jù)分布式存儲(chǔ)研究[J].地理與地理信息，2012，28（5）：39-42.endprint

摘 要：為高效地處理大規(guī)模矢量空間數(shù)據(jù)，基于Hadoop的并行計(jì)算框架MapRedue，實(shí)現(xiàn)了一種分布式的矢量空間數(shù)據(jù)選擇查詢處理方法。首先，分析OGC簡單要素標(biāo)準(zhǔn)與Hadoop的Key/Value數(shù)據(jù)模型，設(shè)計(jì)了可存儲(chǔ)于Hadoop HDFS的矢量文件格式；其次，根據(jù)兩階段的過濾-精煉策略，對Map 輸入數(shù)據(jù)分片、選擇查詢處理過程及Reduce結(jié)果合并等關(guān)鍵步驟進(jìn)行了詳細(xì)闡述；最后，基于上述技術(shù)，利用Hadoop集群環(huán)境對所提出的方法進(jìn)行驗(yàn)證，該方法具有較好的可行性和較高的效率。

關(guān)鍵詞：MapRedue 選擇查詢 存儲(chǔ)模型 Key/Value 矢量數(shù)據(jù)文件

中圖分類號(hào)： 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）03（c）-0193-02

隨著全球空間數(shù)據(jù)集的急劇增長，海量空間數(shù)據(jù)帶來了豐富的信息，而面對如此龐大和復(fù)雜的數(shù)據(jù)集，隨之產(chǎn)生了數(shù)據(jù)存儲(chǔ)與管理問題。國內(nèi)外很多學(xué)者嘗試?yán)肏adoop云計(jì)算技術(shù)處理矢量空間數(shù)據(jù)。張書彬等利用MapReduce并行處理空間查詢的數(shù)據(jù)分割方法、副本避免方法實(shí)現(xiàn)空間查詢[1]；趙彥榮等基于Hadoop提出了一種并行連接查詢算法CHMJ[2]，提高了連接查詢的處理效率；尹芳等基于開源Hadoop 的矢量空間數(shù)據(jù)分布式處理研究[3]；王永剛對Hadoop云計(jì)算平臺(tái)下地理信息服務(wù)的若干關(guān)鍵技術(shù)進(jìn)行了研究[4]。

基于上述研究，該文以Hadoop分布式文件系統(tǒng)存儲(chǔ)矢量空間數(shù)據(jù)，根據(jù)空間查詢處理的兩階段過濾與精煉策略，并充分利用MapRedue并行計(jì)算框架處理海量數(shù)據(jù)的優(yōu)勢，設(shè)計(jì)一種簡單實(shí)用的選擇查詢方法，有效提高了對大規(guī)模矢量空間數(shù)據(jù)的查詢處理效率。

1 基本概念

1.1 空間選擇查詢

在GIS中，常見的對空間矢量數(shù)據(jù)的查詢有三種，即：空間選擇查詢、空間連接查詢和最近鄰查詢。其中，空間選擇查詢和連接查詢是最基本的查詢操作。空間選擇查詢是最重要的一種空間查詢操作，它能夠作為其他空間查詢操作（如空間連接查詢和最近鄰查詢）的基礎(chǔ)。代表性的空間選擇查詢包括空間點(diǎn)查詢和空間區(qū)域查詢。點(diǎn)查詢（Point Query）通過給定一個(gè)查詢點(diǎn)P和一個(gè)空間對象集M，查找出M中所有包含點(diǎn)P的空間對象。區(qū)域查詢通過給定一個(gè)多邊形區(qū)域R和一個(gè)空間對象集M，查找出M中所有與R相交或被R包含的空間對象。

1.2 MapReduce并行計(jì)算框架

Hadoop是一款開源分布式系統(tǒng)基礎(chǔ)架構(gòu)，它支持在商用硬件構(gòu)建的大型集群上運(yùn)行應(yīng)用程序，實(shí)現(xiàn)對海量數(shù)據(jù)的分布式處理。其核心技術(shù)包括并行計(jì)算框架MapReduce和分布式文件系統(tǒng)HDFS，分別是Google MapReduce和GFS的開源實(shí)現(xiàn)。MapReduce是一種并行計(jì)算的編程模型，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運(yùn)算。

2 基于MapReduce的空間選擇查詢

2.1 矢量數(shù)據(jù)存儲(chǔ)模型

目前，開放地理信息聯(lián)盟OGC（Open Geospatial Consortium）制定了許多與空間信息、基于位置服務(wù)相關(guān)的標(biāo)準(zhǔn)，其中簡單要素模型（圖1）是OGC最為重要的幾何對象模型。簡單要素幾何對象中主要定義了點(diǎn)、線、面和集合對象。通過將空間對象與空間參考系進(jìn)行關(guān)聯(lián)，空間對象被抽象表達(dá)為空間參考系統(tǒng)（Spatial Reference System）所描述的幾何體（Geometry）。大多數(shù)空間關(guān)系及空間分析都基于這個(gè)類層次體系進(jìn)行研究，并且平臺(tái)是獨(dú)立的，可以應(yīng)用到分布式計(jì)算系統(tǒng)[5]。該文中同樣采用簡單要素模型來存儲(chǔ)矢量數(shù)據(jù)。

2.2 HDFS矢量數(shù)據(jù)文件

在OGC簡單要素模型中，可以采用WKT（Well-Known Text）和WKB（Well-Known Binary）兩種編碼方式表示幾何對象。WKT通過文本來描述幾何對象和空間參考，而WKB通過二進(jìn)制字節(jié)形式描述空間對象。由于HDFS不直接支持矢量數(shù)據(jù)結(jié)構(gòu)，矢量數(shù)據(jù)需要進(jìn)行轉(zhuǎn)化后才能在Hadoop中使用。Hadoop非常擅長處理非結(jié)構(gòu)化文本數(shù)據(jù)，默認(rèn)使用文本作為輸入，因此本文采用WKT來描述矢量空間對象，利用開源GeoTools-2.7.5工具包，設(shè)計(jì)了一種便于在hadoop中分布式存儲(chǔ)的矢量數(shù)據(jù)文件，如圖1。

在矢量數(shù)據(jù)文件中，每一行表示一個(gè)空間對象。通過HDFS來存儲(chǔ)和管理矢量數(shù)據(jù)文件，就是直接將創(chuàng)建的矢量數(shù)據(jù)文件上傳到HDFS文件系統(tǒng)，然后HDFS對其進(jìn)行自動(dòng)分片，生成大量的數(shù)據(jù)塊（缺省為64M），分別存儲(chǔ)到不同的節(jié)點(diǎn)上。

2.3 MapReduce矢量數(shù)據(jù)選擇查詢方法

由于空間查詢多為計(jì)算密集型操作，為了提高查詢效率，本文采用兩階段的過濾-精煉算法。第一階段過濾，將空間對象用其最小外包矩形表示，當(dāng)查詢區(qū)域?yàn)榫匦螘r(shí)，兩個(gè)矩形是否相交最多只需要4次判斷就能確定，過濾后得到候選集。第二階段精煉，通過對候選集使用精確的幾何條件和屬性條件判斷，最終獲得符合查詢要求的空間對象集。

在map函數(shù)中，從HDFS矢量數(shù)據(jù)文件依次讀取空間對象，經(jīng)過過濾階段和精煉階段的篩選，reduce函數(shù)將滿足查詢條件的空間對象集輸出到HDFS文件系統(tǒng)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

實(shí)驗(yàn)平臺(tái)使用1臺(tái)計(jì)算機(jī)作為宿主機(jī)，安裝VMware9虛擬機(jī)，同時(shí)虛擬出3臺(tái)相同的計(jì)算機(jī)。三臺(tái)虛擬機(jī)分別安裝Linux操作系統(tǒng)，并部署Hadoop-1.0.0構(gòu)成分布式處理集群，其中一臺(tái)同時(shí)作為master節(jié)點(diǎn)和slave節(jié)點(diǎn)，另外兩臺(tái)作為slave節(jié)點(diǎn)。宿主機(jī)：CPU：AMD 5200+，內(nèi)存：4.00 GB，操作系統(tǒng)：win7（64位），開發(fā)環(huán)境：eclipse3.7.1；虛擬機(jī)：操作系統(tǒng)均為Ubuntu-11.10-desktop-i386，內(nèi)存：512 MB。實(shí)驗(yàn)數(shù)據(jù)：矢量數(shù)據(jù)（數(shù)據(jù)量：168MB，133099個(gè)線空間對象），格式：ESRI Shapefile文件。

3.2 矢量數(shù)據(jù)查詢實(shí)驗(yàn)

由空間選擇查詢算法可知，實(shí)驗(yàn)步驟如下：（1）將矢量數(shù)據(jù)存入HDFS；（2）選取查詢窗口；（3）執(zhí)行基于MapReduce的矢量數(shù)據(jù)過濾-精煉算法；（4）查詢結(jié)果寫入HDFS（圖2）。

從實(shí)驗(yàn)結(jié)果可以得出，第一，當(dāng)集群中節(jié)點(diǎn)數(shù)目相同時(shí)，隨著查詢數(shù)據(jù)量的增大，查詢時(shí)間變長，是因?yàn)椴樵兇翱诎瑪?shù)據(jù)條數(shù)增加，使得過濾-精煉過程的開銷也相應(yīng)變大。第二，對于同一個(gè)查詢窗口，集群中節(jié)點(diǎn)數(shù)量增加，查詢時(shí)間依次減小，其原因是Hadoop中默認(rèn)塊大小是64MB，HDFS上文件通常是按照64MB被切分為不同的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊盡可能分散存儲(chǔ)在不同數(shù)據(jù)節(jié)點(diǎn)中，并且每塊對應(yīng)一個(gè)Map任務(wù)，因此168MB的矢量數(shù)據(jù)對應(yīng)3個(gè)Map任務(wù)，隨著節(jié)點(diǎn)數(shù)增加，任務(wù)執(zhí)行的并行程度提高，當(dāng)節(jié)點(diǎn)數(shù)為3時(shí)，3個(gè)Map任務(wù)可以實(shí)現(xiàn)并行執(zhí)行，查詢窗口1，2，3相對于單節(jié)點(diǎn)的查詢效率分別提高了13.3%、16.3%和15.08%。

4 結(jié)語

該文根據(jù)hadoop的分布式存儲(chǔ)特點(diǎn)和矢量數(shù)據(jù)的存儲(chǔ)模型，設(shè)計(jì)一種適合hadoop存儲(chǔ)的矢量數(shù)據(jù)文件，通過對矢量數(shù)據(jù)MapReduce處理流程的分析，實(shí)現(xiàn)基于hadoop過濾-精煉算法的矢量數(shù)據(jù)的選擇查詢方法，通過實(shí)驗(yàn)，驗(yàn)證了本文提出方法的正確性和有效性。下一步，將研究基于MapRedue的大規(guī)模矢量空間數(shù)據(jù)連接查詢處理方法。

參考文獻(xiàn)

[1] 張書彬，韓冀中，劉志勇，等.基于MapReduce實(shí)現(xiàn)空間查詢的研究[J]. 高技術(shù)通訊，2010，20（7）：719-726.

[2] 趙彥榮，王偉平，孟丹，等.基于Hadoop的高效連接查詢處理算法CHMJ[J].軟件學(xué)報(bào)，2012（4）：124.

[3] 尹芳，馮敏，諸云強(qiáng)，等，基于開源Hadoop 的矢量空間數(shù)據(jù)分布式處理研究[J].計(jì)算機(jī)工程與應(yīng)用，2013（16）.

[4] 王永剛.基于Hadoop云計(jì)算平臺(tái)的地理信息服務(wù)若干關(guān)鍵技術(shù)研究[D].北京：中國科學(xué)院研究生院遙感應(yīng)用研究，2011.

[5] 范建永，龍明，熊偉.基于HBase的矢量空間數(shù)據(jù)分布式存儲(chǔ)研究[J].地理與地理信息，2012，28（5）：39-42.endprint

摘 要：為高效地處理大規(guī)模矢量空間數(shù)據(jù)，基于Hadoop的并行計(jì)算框架MapRedue，實(shí)現(xiàn)了一種分布式的矢量空間數(shù)據(jù)選擇查詢處理方法。首先，分析OGC簡單要素標(biāo)準(zhǔn)與Hadoop的Key/Value數(shù)據(jù)模型，設(shè)計(jì)了可存儲(chǔ)于Hadoop HDFS的矢量文件格式；其次，根據(jù)兩階段的過濾-精煉策略，對Map 輸入數(shù)據(jù)分片、選擇查詢處理過程及Reduce結(jié)果合并等關(guān)鍵步驟進(jìn)行了詳細(xì)闡述；最后，基于上述技術(shù)，利用Hadoop集群環(huán)境對所提出的方法進(jìn)行驗(yàn)證，該方法具有較好的可行性和較高的效率。

關(guān)鍵詞：MapRedue 選擇查詢 存儲(chǔ)模型 Key/Value 矢量數(shù)據(jù)文件

中圖分類號(hào)： 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）03（c）-0193-02

隨著全球空間數(shù)據(jù)集的急劇增長，海量空間數(shù)據(jù)帶來了豐富的信息，而面對如此龐大和復(fù)雜的數(shù)據(jù)集，隨之產(chǎn)生了數(shù)據(jù)存儲(chǔ)與管理問題。國內(nèi)外很多學(xué)者嘗試?yán)肏adoop云計(jì)算技術(shù)處理矢量空間數(shù)據(jù)。張書彬等利用MapReduce并行處理空間查詢的數(shù)據(jù)分割方法、副本避免方法實(shí)現(xiàn)空間查詢[1]；趙彥榮等基于Hadoop提出了一種并行連接查詢算法CHMJ[2]，提高了連接查詢的處理效率；尹芳等基于開源Hadoop 的矢量空間數(shù)據(jù)分布式處理研究[3]；王永剛對Hadoop云計(jì)算平臺(tái)下地理信息服務(wù)的若干關(guān)鍵技術(shù)進(jìn)行了研究[4]。

基于上述研究，該文以Hadoop分布式文件系統(tǒng)存儲(chǔ)矢量空間數(shù)據(jù)，根據(jù)空間查詢處理的兩階段過濾與精煉策略，并充分利用MapRedue并行計(jì)算框架處理海量數(shù)據(jù)的優(yōu)勢，設(shè)計(jì)一種簡單實(shí)用的選擇查詢方法，有效提高了對大規(guī)模矢量空間數(shù)據(jù)的查詢處理效率。

1 基本概念

1.1 空間選擇查詢

在GIS中，常見的對空間矢量數(shù)據(jù)的查詢有三種，即：空間選擇查詢、空間連接查詢和最近鄰查詢。其中，空間選擇查詢和連接查詢是最基本的查詢操作?？臻g選擇查詢是最重要的一種空間查詢操作，它能夠作為其他空間查詢操作（如空間連接查詢和最近鄰查詢）的基礎(chǔ)。代表性的空間選擇查詢包括空間點(diǎn)查詢和空間區(qū)域查詢。點(diǎn)查詢（Point Query）通過給定一個(gè)查詢點(diǎn)P和一個(gè)空間對象集M，查找出M中所有包含點(diǎn)P的空間對象。區(qū)域查詢通過給定一個(gè)多邊形區(qū)域R和一個(gè)空間對象集M，查找出M中所有與R相交或被R包含的空間對象。

1.2 MapReduce并行計(jì)算框架

Hadoop是一款開源分布式系統(tǒng)基礎(chǔ)架構(gòu)，它支持在商用硬件構(gòu)建的大型集群上運(yùn)行應(yīng)用程序，實(shí)現(xiàn)對海量數(shù)據(jù)的分布式處理。其核心技術(shù)包括并行計(jì)算框架MapReduce和分布式文件系統(tǒng)HDFS，分別是Google MapReduce和GFS的開源實(shí)現(xiàn)。MapReduce是一種并行計(jì)算的編程模型，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運(yùn)算。

2 基于MapReduce的空間選擇查詢

2.1 矢量數(shù)據(jù)存儲(chǔ)模型

目前，開放地理信息聯(lián)盟OGC（Open Geospatial Consortium）制定了許多與空間信息、基于位置服務(wù)相關(guān)的標(biāo)準(zhǔn)，其中簡單要素模型（圖1）是OGC最為重要的幾何對象模型。簡單要素幾何對象中主要定義了點(diǎn)、線、面和集合對象。通過將空間對象與空間參考系進(jìn)行關(guān)聯(lián)，空間對象被抽象表達(dá)為空間參考系統(tǒng)（Spatial Reference System）所描述的幾何體（Geometry）。大多數(shù)空間關(guān)系及空間分析都基于這個(gè)類層次體系進(jìn)行研究，并且平臺(tái)是獨(dú)立的，可以應(yīng)用到分布式計(jì)算系統(tǒng)[5]。該文中同樣采用簡單要素模型來存儲(chǔ)矢量數(shù)據(jù)。

2.2 HDFS矢量數(shù)據(jù)文件

在OGC簡單要素模型中，可以采用WKT（Well-Known Text）和WKB（Well-Known Binary）兩種編碼方式表示幾何對象。WKT通過文本來描述幾何對象和空間參考，而WKB通過二進(jìn)制字節(jié)形式描述空間對象。由于HDFS不直接支持矢量數(shù)據(jù)結(jié)構(gòu)，矢量數(shù)據(jù)需要進(jìn)行轉(zhuǎn)化后才能在Hadoop中使用。Hadoop非常擅長處理非結(jié)構(gòu)化文本數(shù)據(jù)，默認(rèn)使用文本作為輸入，因此本文采用WKT來描述矢量空間對象，利用開源GeoTools-2.7.5工具包，設(shè)計(jì)了一種便于在hadoop中分布式存儲(chǔ)的矢量數(shù)據(jù)文件，如圖1。

在矢量數(shù)據(jù)文件中，每一行表示一個(gè)空間對象。通過HDFS來存儲(chǔ)和管理矢量數(shù)據(jù)文件，就是直接將創(chuàng)建的矢量數(shù)據(jù)文件上傳到HDFS文件系統(tǒng)，然后HDFS對其進(jìn)行自動(dòng)分片，生成大量的數(shù)據(jù)塊（缺省為64M），分別存儲(chǔ)到不同的節(jié)點(diǎn)上。

2.3 MapReduce矢量數(shù)據(jù)選擇查詢方法

由于空間查詢多為計(jì)算密集型操作，為了提高查詢效率，本文采用兩階段的過濾-精煉算法。第一階段過濾，將空間對象用其最小外包矩形表示，當(dāng)查詢區(qū)域?yàn)榫匦螘r(shí)，兩個(gè)矩形是否相交最多只需要4次判斷就能確定，過濾后得到候選集。第二階段精煉，通過對候選集使用精確的幾何條件和屬性條件判斷，最終獲得符合查詢要求的空間對象集。

在map函數(shù)中，從HDFS矢量數(shù)據(jù)文件依次讀取空間對象，經(jīng)過過濾階段和精煉階段的篩選，reduce函數(shù)將滿足查詢條件的空間對象集輸出到HDFS文件系統(tǒng)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

實(shí)驗(yàn)平臺(tái)使用1臺(tái)計(jì)算機(jī)作為宿主機(jī)，安裝VMware9虛擬機(jī)，同時(shí)虛擬出3臺(tái)相同的計(jì)算機(jī)。三臺(tái)虛擬機(jī)分別安裝Linux操作系統(tǒng)，并部署Hadoop-1.0.0構(gòu)成分布式處理集群，其中一臺(tái)同時(shí)作為master節(jié)點(diǎn)和slave節(jié)點(diǎn)，另外兩臺(tái)作為slave節(jié)點(diǎn)。宿主機(jī)：CPU：AMD 5200+，內(nèi)存：4.00 GB，操作系統(tǒng)：win7（64位），開發(fā)環(huán)境：eclipse3.7.1；虛擬機(jī)：操作系統(tǒng)均為Ubuntu-11.10-desktop-i386，內(nèi)存：512 MB。實(shí)驗(yàn)數(shù)據(jù)：矢量數(shù)據(jù)（數(shù)據(jù)量：168MB，133099個(gè)線空間對象），格式：ESRI Shapefile文件。

3.2 矢量數(shù)據(jù)查詢實(shí)驗(yàn)

由空間選擇查詢算法可知，實(shí)驗(yàn)步驟如下：（1）將矢量數(shù)據(jù)存入HDFS；（2）選取查詢窗口；（3）執(zhí)行基于MapReduce的矢量數(shù)據(jù)過濾-精煉算法；（4）查詢結(jié)果寫入HDFS（圖2）。

從實(shí)驗(yàn)結(jié)果可以得出，第一，當(dāng)集群中節(jié)點(diǎn)數(shù)目相同時(shí)，隨著查詢數(shù)據(jù)量的增大，查詢時(shí)間變長，是因?yàn)椴樵兇翱诎瑪?shù)據(jù)條數(shù)增加，使得過濾-精煉過程的開銷也相應(yīng)變大。第二，對于同一個(gè)查詢窗口，集群中節(jié)點(diǎn)數(shù)量增加，查詢時(shí)間依次減小，其原因是Hadoop中默認(rèn)塊大小是64MB，HDFS上文件通常是按照64MB被切分為不同的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊盡可能分散存儲(chǔ)在不同數(shù)據(jù)節(jié)點(diǎn)中，并且每塊對應(yīng)一個(gè)Map任務(wù)，因此168MB的矢量數(shù)據(jù)對應(yīng)3個(gè)Map任務(wù)，隨著節(jié)點(diǎn)數(shù)增加，任務(wù)執(zhí)行的并行程度提高，當(dāng)節(jié)點(diǎn)數(shù)為3時(shí)，3個(gè)Map任務(wù)可以實(shí)現(xiàn)并行執(zhí)行，查詢窗口1，2，3相對于單節(jié)點(diǎn)的查詢效率分別提高了13.3%、16.3%和15.08%。

4 結(jié)語

該文根據(jù)hadoop的分布式存儲(chǔ)特點(diǎn)和矢量數(shù)據(jù)的存儲(chǔ)模型，設(shè)計(jì)一種適合hadoop存儲(chǔ)的矢量數(shù)據(jù)文件，通過對矢量數(shù)據(jù)MapReduce處理流程的分析，實(shí)現(xiàn)基于hadoop過濾-精煉算法的矢量數(shù)據(jù)的選擇查詢方法，通過實(shí)驗(yàn)，驗(yàn)證了本文提出方法的正確性和有效性。下一步，將研究基于MapRedue的大規(guī)模矢量空間數(shù)據(jù)連接查詢處理方法。

參考文獻(xiàn)

[1] 張書彬，韓冀中，劉志勇，等.基于MapReduce實(shí)現(xiàn)空間查詢的研究[J]. 高技術(shù)通訊，2010，20（7）：719-726.

[2] 趙彥榮，王偉平，孟丹，等.基于Hadoop的高效連接查詢處理算法CHMJ[J].軟件學(xué)報(bào)，2012（4）：124.

[3] 尹芳，馮敏，諸云強(qiáng)，等，基于開源Hadoop 的矢量空間數(shù)據(jù)分布式處理研究[J].計(jì)算機(jī)工程與應(yīng)用，2013（16）.

[4] 王永剛.基于Hadoop云計(jì)算平臺(tái)的地理信息服務(wù)若干關(guān)鍵技術(shù)研究[D].北京：中國科學(xué)院研究生院遙感應(yīng)用研究，2011.

[5] 范建永，龍明，熊偉.基于HBase的矢量空間數(shù)據(jù)分布式存儲(chǔ)研究[J].地理與地理信息，2012，28（5）：39-42.endprint