基于MapRedue的大規模矢量空間數據選擇查詢處理

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

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

關鍵詞：MapRedue 選擇查詢 存儲模型 Key/Value 矢量數據文件

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

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

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

1 基本概念

1.1 空間選擇查詢

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

1.2 MapReduce并行計算框架

Hadoop是一款開源分布式系統基礎架構，它支持在商用硬件構建的大型集群上運行應用程序，實現對海量數據的分布式處理。其核心技術包括并行計算框架MapReduce和分布式文件系統HDFS，分別是Google MapReduce和GFS的開源實現。MapReduce是一種并行計算的編程模型，用于大規模數據集（大于1TB）的并行運算。

2 基于MapReduce的空間選擇查詢

2.1 矢量數據存儲模型

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

2.2 HDFS矢量數據文件

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

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

2.3 MapReduce矢量數據選擇查詢方法

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

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

3 實驗與結果分析

3.1 實驗環境與數據

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

3.2 矢量數據查詢實驗

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

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

4 結語

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

參考文獻

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

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

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

[4] 王永剛.基于Hadoop云計算平臺的地理信息服務若干關鍵技術研究[D].北京：中國科學院研究生院遙感應用研究，2011.

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

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

關鍵詞：MapRedue 選擇查詢 存儲模型 Key/Value 矢量數據文件

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

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

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

1 基本概念

1.1 空間選擇查詢

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

1.2 MapReduce并行計算框架

Hadoop是一款開源分布式系統基礎架構，它支持在商用硬件構建的大型集群上運行應用程序，實現對海量數據的分布式處理。其核心技術包括并行計算框架MapReduce和分布式文件系統HDFS，分別是Google MapReduce和GFS的開源實現。MapReduce是一種并行計算的編程模型，用于大規模數據集（大于1TB）的并行運算。

2 基于MapReduce的空間選擇查詢

2.1 矢量數據存儲模型

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

2.2 HDFS矢量數據文件

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

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

2.3 MapReduce矢量數據選擇查詢方法

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

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

3 實驗與結果分析

3.1 實驗環境與數據

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

3.2 矢量數據查詢實驗

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

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

4 結語

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

參考文獻

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

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

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

[4] 王永剛.基于Hadoop云計算平臺的地理信息服務若干關鍵技術研究[D].北京：中國科學院研究生院遙感應用研究，2011.

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

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

關鍵詞：MapRedue 選擇查詢 存儲模型 Key/Value 矢量數據文件

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

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

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

1 基本概念

1.1 空間選擇查詢

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

1.2 MapReduce并行計算框架

Hadoop是一款開源分布式系統基礎架構，它支持在商用硬件構建的大型集群上運行應用程序，實現對海量數據的分布式處理。其核心技術包括并行計算框架MapReduce和分布式文件系統HDFS，分別是Google MapReduce和GFS的開源實現。MapReduce是一種并行計算的編程模型，用于大規模數據集（大于1TB）的并行運算。

2 基于MapReduce的空間選擇查詢

2.1 矢量數據存儲模型

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

2.2 HDFS矢量數據文件

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

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

2.3 MapReduce矢量數據選擇查詢方法

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

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

3 實驗與結果分析

3.1 實驗環境與數據

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

3.2 矢量數據查詢實驗

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

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

4 結語

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

參考文獻

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

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

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

[4] 王永剛.基于Hadoop云計算平臺的地理信息服務若干關鍵技術研究[D].北京：中國科學院研究生院遙感應用研究，2011.

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