何濤++劉強++鄭澤忠++劉帥

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

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

中圖分類號： 文獻標識碼：A 文章編號：1674-098X（2014）03（c）-0193-02

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

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

1 基本概念

1.1 空間選擇查詢

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

1.2 MapReduce并行計算框架

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

2 基于MapReduce的空間選擇查詢

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

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

3.2 矢量數(shù)據(jù)查詢實驗

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

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

4 結(jié)語

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

參考文獻

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

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

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

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

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

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

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

中圖分類號： 文獻標識碼：A 文章編號：1674-098X（2014）03（c）-0193-02

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

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

1 基本概念

1.1 空間選擇查詢

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

1.2 MapReduce并行計算框架

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

2 基于MapReduce的空間選擇查詢

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

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

3.2 矢量數(shù)據(jù)查詢實驗

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

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

4 結(jié)語

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

參考文獻

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

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

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

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

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

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

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

中圖分類號： 文獻標識碼：A 文章編號：1674-098X（2014）03（c）-0193-02

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

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

1 基本概念

1.1 空間選擇查詢

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

1.2 MapReduce并行計算框架

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

2 基于MapReduce的空間選擇查詢

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

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

3.2 矢量數(shù)據(jù)查詢實驗

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

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

4 結(jié)語

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

參考文獻

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

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

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

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

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