基于HBase與靜態(tài)多級格網(wǎng)索引的地表覆蓋數(shù)據(jù)高效檢索方法

祝琳瑩，張豐，杜震洪*，劉仁義，左玉強(qiáng)

(1. 浙江省資源與環(huán)境信息系統(tǒng)重點實驗室， 浙江 杭州 310028； 2. 浙江大學(xué) 地理信息科學(xué)研究所， 浙江 杭州 310027;3. 中國土地勘測規(guī)劃院， 北京 100035)

0 引 言

地表覆蓋數(shù)據(jù)是地理國情監(jiān)測的重要數(shù)據(jù)源[1]，是指通過對地形、水域、植被、荒漠與裸露地、人工表面等地表對象進(jìn)行動態(tài)化、定量化和空間化監(jiān)測而得到的一個全區(qū)域覆蓋的地表面狀要素集. 每一要素直接反映某一地塊的基礎(chǔ)地理信息，包括幾何信息與地物分類信息. 這些信息為水土流失評價、森林覆蓋率統(tǒng)計、土地利用評估等提供了可靠的數(shù)據(jù)源. 高效、可靠的地表覆蓋數(shù)據(jù)檢索方法是挖掘地表覆蓋數(shù)據(jù)潛在價值的前提.

地理國情普查中的地表覆蓋數(shù)據(jù)采集以縣級行政區(qū)為單位，圖 1所示為某縣地表覆蓋數(shù)據(jù)要素分類圖層. 與一般的空間矢量數(shù)據(jù)相比，地表覆蓋數(shù)據(jù)有以下特點： (1) 要素分布密集、數(shù)據(jù)量龐大，以浙江省為例，僅德清縣地表覆蓋數(shù)據(jù)要素量就有15萬左右(與地物分布情況及區(qū)域面積有關(guān))，全省要素總量更可達(dá)千萬級別；(2) 要素形狀復(fù)雜多變、面積差異大；(3) 要素空間分布不均勻，河流、湖泊跨越地理范圍大、分布稀疏，而人工建筑物范圍小、分布密集；(4) 數(shù)據(jù)定期批量更新，主要包括幾何信息的修改和屬性信息的更新. 隨著多期普查成果的錄入，地表覆蓋數(shù)據(jù)量將進(jìn)一步增大，這為實時的空間檢索與數(shù)據(jù)分析帶來了嚴(yán)峻的挑戰(zhàn).

傳統(tǒng)的關(guān)系型數(shù)據(jù)庫結(jié)合空間數(shù)據(jù)引擎的空間數(shù)據(jù)檢索方法，存在擴(kuò)展困難、檢索能力不足的弊端，無法滿足海量地表覆蓋數(shù)據(jù)的高效管理與檢索需求[2]. 隨著云計算技術(shù)的蓬勃發(fā)展，NoSQL數(shù)據(jù)庫因其良好的擴(kuò)展性、伸縮性以及強(qiáng)大的并行檢索能力，已在多個領(lǐng)域得到廣泛應(yīng)用[3]. HBase是一種十分流行的NoSQL數(shù)據(jù)庫，能為Hadoop、Spark等分布式計算平臺提供無縫的數(shù)據(jù)集成. 為了提高海量地表覆蓋數(shù)據(jù)的空間檢索效率，本文提出了一種基于HBase與靜態(tài)多級格網(wǎng)索引的地表覆蓋數(shù)據(jù)空間檢索方法，該方法通過MapReduce并行構(gòu)建面向地表覆蓋數(shù)據(jù)特征的靜態(tài)多級格網(wǎng)索引，通過多級過濾的方式提高空間范圍查詢效率，為實現(xiàn)海量地表覆蓋數(shù)據(jù)的高效空間檢索提供了新思路.

1 相關(guān)研究

1.1 HBase概述

HBase是Apache Hadoop的一個子項目，是Google云計算技術(shù)BigTable[4]的開源實現(xiàn). HBase是依托HDFS文件存儲系統(tǒng)的一個面向列、可伸縮、隨機(jī)實時讀寫訪問的分布式存儲系統(tǒng)，能存儲十億級別的結(jié)構(gòu)化數(shù)據(jù)[5].

HBase表是一種稀疏的、多維的、有序的索引表. 如表1所示，HBase定義了一個四維概念模型，由行鍵(row key)、列簇(column family)、列修飾符(column qualifier)和時間戳(time stamp)組成. 表的每一行代表一個數(shù)據(jù)對象，由row key唯一標(biāo)識并按其字典序排序，所以row key的設(shè)計非常重要，設(shè)計目標(biāo)是將相關(guān)聯(lián)的數(shù)據(jù)相鄰存儲以提高數(shù)據(jù)檢索的速度. 一行記錄由若干column family構(gòu)成，代表表中數(shù)據(jù)的信息類別，在定義表前需創(chuàng)建好column family. 每個column family可擁有任意數(shù)量的列成員，通過column qualifier識別，定義為column family： column qualifier. 列的定義是動態(tài)和可變的，因此，每一列可能不同. 通過行和列確定的存儲單元稱為單元格(cell). 每個cell都保存著同一個數(shù)據(jù)對象的多個版本，版本通過time stamp索引按降序排列，讀表時優(yōu)先取得最新值. cell內(nèi)的值由鍵(row key, column family： column qualifier, time stamp)唯一映射，不分類型，全部以字節(jié)碼的形式存儲. 在物理上，HBase將行分割，按照column family存儲數(shù)據(jù)，每個column family存儲在HDFS的一個單獨(dú)文件中. 一個空cell無與鍵關(guān)聯(lián)的值，不存儲在HBase中，但在概念表中是存在的，HBase以這種方式適應(yīng)稀疏行.

表1 HBase數(shù)據(jù)邏輯模型Table 1 Data logical model of HBase

1.2 空間索引現(xiàn)狀分析

空間對象的選擇查詢方式主要包括空間點查詢(spatial point query)、空間范圍查詢(spatial range query)、鄰近查詢(kNN, k nearest neighbor query)和空間連接(spatial join)等. 由于空間實體形態(tài)和拓?fù)潢P(guān)系復(fù)雜，空間查詢屬于計算密集型操作，具有較高的空間和時間復(fù)雜度. 空間索引是指通過建立數(shù)據(jù)邏輯與物理記錄間的對應(yīng)關(guān)系來描述空間數(shù)據(jù)在存儲介質(zhì)上位置的一種數(shù)據(jù)結(jié)構(gòu)，可大大加快空間數(shù)據(jù)的訪問速度. 通常情況下，空間索引中存儲有空間對象的最小外包矩形(mbr, minimum bounding rectangles)和唯一編碼值. 一次空間查詢過程可以概括為“過濾”(filter)和“精煉”(refinement)[6]2個步驟. “過濾”是指從空間索引中快速篩選出其mbr滿足空間查詢要求的空間對象候選集. “精煉”用于確定候選集中的元素是否真的符合查詢條件，其中涉及大量耗時的空間關(guān)系運(yùn)算，因此，過濾階段過濾掉的空間對象越多，查詢速度就越快.

目前，針對面狀地理實體的空間索引主要有R-樹[7]和四叉樹[8]索引以及它們的變種. R-樹是一種高度平衡樹，當(dāng)葉子結(jié)點存儲空間已滿時，插入數(shù)據(jù)后會自動分裂，且向根結(jié)點傳播，使整棵樹結(jié)構(gòu)進(jìn)行動態(tài)調(diào)整直至再度達(dá)到平衡，因此數(shù)據(jù)插入效率較低，結(jié)點相互影響，不適合索引并行構(gòu)建. 同時，R-樹兄弟結(jié)點對應(yīng)的空間區(qū)域互相重疊，易導(dǎo)致搜索路徑不唯一，當(dāng)數(shù)據(jù)分布密集時，其搜索性能會大大降低，甚至降低至與線性搜索的性能一樣. R+-樹的空間區(qū)域無重疊，減少了無效查詢，但插入和刪除操作效率極低，存在跨區(qū)域空間數(shù)據(jù)冗余存儲. R*-樹優(yōu)化了樹結(jié)點分裂算法，索引結(jié)構(gòu)優(yōu)于R-樹，但仍無法有效降低空間重疊度. 在傳統(tǒng)的四叉樹索引中，空間實體只能存儲在葉子結(jié)點里，當(dāng)?shù)乩韺嶓w對象分布不均時，易形成深度過大的不平衡四叉樹，且跨越葉子結(jié)點對應(yīng)空間的空間數(shù)據(jù)重復(fù)存儲，造成存儲空間浪費(fèi)和查詢效率低下.

隨著空間數(shù)據(jù)量的不斷增大，人們開始在分布式環(huán)境下構(gòu)建空間索引，主要圍繞R-樹的并行索引構(gòu)建展開研究. KAMEL等[9]最早提出了基于R-樹的并行查詢機(jī)制，在單處理器、多磁盤的硬件環(huán)境中，采用multiplexed R-樹結(jié)構(gòu)，應(yīng)用proximity index、最小交叉等指標(biāo)優(yōu)化樹結(jié)構(gòu)，并證明該索引結(jié)構(gòu)在空間數(shù)據(jù)分布均勻時具有較優(yōu)的并行查詢性能. SCHNITZER等[10]提出了M-R樹和MC-R樹，均采用主從模式將所有非葉子結(jié)點存儲在主節(jié)點上，葉子結(jié)點和空間對象直接存儲在從節(jié)點上，在每個節(jié)點內(nèi)構(gòu)造獨(dú)立索引，然后合并成總的R-樹索引，這樣的索引結(jié)構(gòu)緊湊、存儲空間利用率高，但仍未解決數(shù)據(jù)分布不均時查詢效率低下的問題. ELDAWY等[11]基于Hadoop實現(xiàn)了空間數(shù)據(jù)處理框架SptialHadoop，采用分層設(shè)計的思想，在主節(jié)點上建立全局索引，從而將數(shù)據(jù)劃分入從節(jié)點，在從節(jié)點上獨(dú)立構(gòu)建基于格網(wǎng)或R-樹結(jié)構(gòu)的局部索引，并利用MapReduce實現(xiàn)數(shù)據(jù)并行查詢. CRAY等[12]基于MapReduce的R-樹并行構(gòu)建算法，采用Z曲線和K-means聚類方法劃分空間，并行構(gòu)建局部索引，但索引質(zhì)量隨分區(qū)數(shù)量的增加而下降. 類似地，其余并行R-樹索引機(jī)制[13-15]主要采用2層或多層索引結(jié)構(gòu)，利用基于Hilbert曲線或Z曲線等空間聚類方法分割空間數(shù)據(jù)，在子空間區(qū)域內(nèi)獨(dú)立構(gòu)建局部索引，在索引結(jié)構(gòu)頂層合并為總索引. 然而，上述索引構(gòu)建算法仍無法擺脫R-樹結(jié)構(gòu)本身帶來的索引構(gòu)建效率低下和多路徑查詢等問題，無法提高實際應(yīng)用中的數(shù)據(jù)檢索速度. 除此之外，人們還設(shè)計了多種R-樹批量加載技術(shù)[16]，在保證查詢性能的前提下，對現(xiàn)有靜態(tài)數(shù)據(jù)進(jìn)行預(yù)處理，以壓縮R-樹結(jié)構(gòu)，提高結(jié)點空間的利用率，從而在一定程度上提升索引構(gòu)建速度. 較為典型的有packed R-樹、Hilbert packed-R樹和STR壓縮算法等，但是壓縮R-樹無法動態(tài)插入和刪除數(shù)據(jù)，故無法應(yīng)用于定期更新的數(shù)據(jù)索引.

隨著分布式數(shù)據(jù)庫的廣泛應(yīng)用，不少學(xué)者提出了基于HBase的空間數(shù)據(jù)索引方案. 范建永等[17]根據(jù)不同比例尺和圖層創(chuàng)建了不同的矢量數(shù)據(jù)存儲表，每個存儲表對應(yīng)一套按特定規(guī)則劃分的格網(wǎng)，格網(wǎng)索引的row key值由Hilbert空間曲線編碼確定，并利用MapReduce提高索引構(gòu)建速度，但將空間數(shù)據(jù)分開存儲不利于數(shù)據(jù)組織，且規(guī)則格網(wǎng)不適合分布不均的數(shù)據(jù)索引. HAN等[18]提出了HGrid數(shù)據(jù)模型——一種結(jié)合四叉樹和規(guī)則格網(wǎng)的混合索引，先將空間數(shù)據(jù)按四叉樹結(jié)構(gòu)劃分，再將四叉樹格網(wǎng)規(guī)則劃分，實驗表明，在range query和kNN操作上，該模型總體性能優(yōu)于四叉樹索引，不如規(guī)則格網(wǎng)索引. 張榆等[19]提出了一種空間文本數(shù)據(jù)索引結(jié)構(gòu)SK-HBase，即將空間文本對象的文本信息和空間信息經(jīng)Z曲線編碼后作為索引表行鍵，并提出了2種基于SK-HBase的空間關(guān)鍵字查詢算法. ZRA算法： 將空間查詢范圍轉(zhuǎn)化為Z曲線編碼值后掃描索引表，然后在HBase服務(wù)器端進(jìn)一步過濾. kd-ZRA算法： 在ZRA基礎(chǔ)上利用k-d樹將Z曲線編碼值劃分為多個，以提高大范圍空間下的掃描效率. 由于沒有預(yù)先將空間數(shù)據(jù)進(jìn)行有效劃分，僅靠Z曲線的聚類能力，過濾階段粗濾掉的數(shù)據(jù)量是非常有限的.

地表覆蓋對象不同于一般的面狀空間實體，其要素形態(tài)不規(guī)整、數(shù)據(jù)體量龐大、分布極不均勻. 傳統(tǒng)的面狀對象空間索引是動態(tài)建立的，面對海量空間數(shù)據(jù)，插入數(shù)據(jù)時因頻繁進(jìn)行索引結(jié)點分裂和索引結(jié)構(gòu)調(diào)整等操作，其索引構(gòu)建效率低下，且形成深層級結(jié)構(gòu)，從而影響數(shù)據(jù)存取速度. 同時，在數(shù)據(jù)大批量更新時，需重構(gòu)索引，不適合構(gòu)建基于多期數(shù)據(jù)的持久化索引. 基于地表覆蓋數(shù)據(jù)的特性，本文引入了支持并發(fā)構(gòu)建的靜態(tài)多級格網(wǎng)索引，將空間數(shù)據(jù)有效地劃入子集，依托HBase強(qiáng)大的數(shù)據(jù)隨機(jī)訪問能力，在索引中快速定位空間對象候選集，減輕數(shù)據(jù)精煉的壓力，從而提高空間數(shù)據(jù)搜索的效率.

2 地表覆蓋數(shù)據(jù)空間檢索設(shè)計

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

地表覆蓋數(shù)據(jù)存儲于HBase表中，每一條記錄對應(yīng)一個矢量要素、存儲要素的實體和屬性信息，便于以完整的地理空間實體為基本單位進(jìn)行訪問、添加、修改和刪除操作，每一個空間對象應(yīng)有唯一的編碼標(biāo)識和定位，這個編碼就是數(shù)據(jù)表row key. HBase數(shù)據(jù)模型不能提供類似關(guān)系型數(shù)據(jù)庫的關(guān)系查詢功能，僅能依據(jù)row key進(jìn)行數(shù)據(jù)的直接訪問(get)或范圍掃描(scan)，因此，row key是影響HBase數(shù)據(jù)訪問和存取速度的關(guān)鍵，應(yīng)與實際應(yīng)用需求緊密結(jié)合. 在地理國情普查中，地表覆蓋數(shù)據(jù)采集以縣級行政區(qū)為單位，分區(qū)獨(dú)立編碼，合并存儲時會出現(xiàn)編碼重復(fù)問題. 此外，查詢某一行政區(qū)劃內(nèi)某一地理國情分類下的要素是最常見的地表覆蓋數(shù)據(jù)檢索操作. 為了保證同一行政區(qū)、同一分類的矢量要素在數(shù)據(jù)表中聚集存儲，本文采用RegionCode+CC+FID編碼方式作為矢量要素唯一編碼(OID,Object ID)，并將其作為HBase數(shù)據(jù)存儲表的row key. 其中，Regioncode為12位行政區(qū)劃編碼，CC為4位地理國情分類碼，F(xiàn)ID為8位矢量要素編碼. 為了應(yīng)對數(shù)據(jù)的批量更新操作，記錄的每一條time stamp定義為不同批次數(shù)據(jù)的時間版本，訪問矢量要素時默認(rèn)獲取最新的一條數(shù)據(jù)記錄，即最新版本的要素信息.

從邏輯視圖上看，地表覆蓋矢量要素在數(shù)據(jù)表中首先按照行政區(qū)分區(qū)存儲，在同一行政區(qū)內(nèi)再根據(jù)分類碼分片存儲，在同一分類下按FID字典序排列，同一要素的記錄按時間版本從大到小排序.

根據(jù)HBase物理模型，同屬于一個column family的column存儲在同一文件上，因此，為了減少磁盤訪問次數(shù)，將邏輯上相關(guān)聯(lián)的數(shù)據(jù)存儲在同一column family下. 本文在數(shù)據(jù)表中設(shè)計了2個column family：

(1) COLUMNFAMILY_GEOMETRY，包含列g(shù)eometry，用于存放矢量要素實體信息，包括位置坐標(biāo)和幾何信息.

(2) COLUMNFAMILY_PROPERTY，存儲矢量要素屬性信息，包含CC、要素標(biāo)題(caption)、要素長度(length)和要素面積(area)等列.

基于HBase的數(shù)據(jù)模型物理結(jié)構(gòu)如圖 2所示.

圖2 HBase數(shù)據(jù)模型物理結(jié)構(gòu)Fig.2 Physical structure of HBase data model

2.2 空間索引設(shè)計

2.2.1 多級格網(wǎng)索引的邏輯結(jié)構(gòu)

為了將地表覆蓋數(shù)據(jù)劃入不同的數(shù)據(jù)子集以進(jìn)行空間查詢的過濾操作，本文引入靜態(tài)多級格網(wǎng)結(jié)構(gòu)，并結(jié)合四叉樹索引的層級剖分思想設(shè)計了地表覆蓋空間索引. 如圖3所示，多級格網(wǎng)索引的層次結(jié)構(gòu)與四叉樹索引類似，每一個格網(wǎng)在下一層級中劃分為4個子格網(wǎng)，不同點在于多級格網(wǎng)是預(yù)先定義好的層級固定的靜態(tài)格網(wǎng)結(jié)構(gòu)，多個層級的格網(wǎng)共同構(gòu)成了一個格網(wǎng)金字塔，在插入數(shù)據(jù)時，格網(wǎng)不會動態(tài)分裂，并且空間對象只存儲在能完全包含其mbr的最小格網(wǎng)中.

圖3 多級格網(wǎng)索引結(jié)構(gòu)Fig.3 Multi-level grid index structure

靜態(tài)多級格網(wǎng)索引中的每一個格網(wǎng)都有固定的層級(L)、行號(R)和列號(C)，(L,R,C)三元組能唯一確定多級格網(wǎng)金字塔中的一個格網(wǎng). 多級格網(wǎng)索引結(jié)構(gòu)由起始層級(SL)和終止層級(EL)共同決定. 為了滿足所有地表覆蓋數(shù)據(jù)的索引需求，起始層級的格網(wǎng)應(yīng)完全覆蓋所有地表覆蓋對象. 終止層級越大，底層格網(wǎng)劃分得越精細(xì)，對應(yīng)的空間范圍就越小，空間查詢時過濾的格網(wǎng)數(shù)就越多，精煉的空間對象相對變少，但層級并不是越多越好，層級過深時，過濾操作將耗費(fèi)大量時間，精煉的數(shù)據(jù)量并不會顯著變少，因此，實際應(yīng)用時，需根據(jù)數(shù)據(jù)分布情況確定EL，本文實驗部分有詳細(xì)分析.

相較于傳統(tǒng)的空間索引，靜態(tài)多級格網(wǎng)索引更適應(yīng)地表覆蓋數(shù)據(jù)的特征，原因如下：

(1) 預(yù)定義的靜態(tài)索引結(jié)構(gòu)不隨數(shù)據(jù)的插入和刪除而改變，索引構(gòu)建效率高，更適合頻繁大規(guī)模更新的數(shù)據(jù)索引；

(2) 適合存儲分布不均勻的空間對象，不會因索引層級過深而降低檢索效率，結(jié)合有效的查詢算法能規(guī)避數(shù)據(jù)分布不均衡帶來的影響；

(3) 分層次分塊的索引結(jié)構(gòu)，有效地將空間對象劃入不同尺度的空間子區(qū)域中，可以利用格網(wǎng)的空間關(guān)系進(jìn)行空間區(qū)域粗過濾，快速定位空間對象所屬區(qū)域，從而減輕數(shù)據(jù)精煉的壓力；

(4) 每個空間對象只映射到一個格網(wǎng)，避免了數(shù)據(jù)冗余，同時在數(shù)據(jù)插入過程中，不同格網(wǎng)內(nèi)存儲的對象互不干擾，格網(wǎng)間互相獨(dú)立. 而構(gòu)建并行R-樹時，子樹的結(jié)點分裂將影響整棵樹的結(jié)構(gòu)，子樹間依賴程度高，因此多級格網(wǎng)索引更適合并行構(gòu)建.

假設(shè)在全球空間范圍內(nèi)建立靜態(tài)多級格網(wǎng)，則起始層級的格網(wǎng)是一個大小為360×360的矩形. 若格網(wǎng)行列號從左上角起算，則空間任一點P在層級L中所處的格網(wǎng)行列號為

(1)

(2)

(3)

其中，gs表示在層級L中格網(wǎng)的大小，lon和lat分別表示P的經(jīng)度和緯度.

由式(1)～(3)，可計算全球多級格網(wǎng)中各個層級內(nèi)所有格網(wǎng)的大小、行列號和頂點經(jīng)緯度. 獲取地表覆蓋要素集的覆蓋范圍后，計算其mbr的頂點坐標(biāo). 從全球起始層級開始，向下逐級檢查與該mbr相交的格網(wǎng)個數(shù). 當(dāng)格網(wǎng)個數(shù)為1且下一級相交的格網(wǎng)個數(shù)大于1時，則認(rèn)為當(dāng)前層級的該格網(wǎng)完全容納地表覆蓋要素集的最小格網(wǎng)，該格網(wǎng)即為地表覆蓋空間索引的起始搜索格網(wǎng)G，該層級即為索引的起始層級SL. 算法1為獲取多級格網(wǎng)索引的起始層級和搜索格網(wǎng)的算法.

算法1獲取起始搜索格網(wǎng)和起始層級

輸入要素集mbr.

輸出起始搜索格網(wǎng)G，起始層級SL.

GetOriginGrid (mbr)

1L←0

2 SL←0

3G←NIL

4 while(true)

5 dogridcount←

GetIntersectGridCount(L,MBR)

6ifgridcount = 1

7thenL←L+1

8G←GetIntersectGrid (L,MBR)

9else ifgridcount > 1

10thenSL=L-1

11return(G,SL)

2.2.2 多級格網(wǎng)索引表設(shè)計

多級格網(wǎng)索引表存儲格網(wǎng)與空間對象間一對多的對應(yīng)關(guān)系，是為將索引持久化到HBase表中，滿足一次構(gòu)建、多次使用而設(shè)計的. 索引表row key標(biāo)識索引結(jié)構(gòu)中的一個格網(wǎng)(GID, Grid ID)，由格網(wǎng)的層級、行號和列號共同編碼確定. 本文利用Z曲線[20]對格網(wǎng)的行號和列號進(jìn)行降維編碼，借助Z曲線的空間聚類特性，保證同一層級相鄰的格網(wǎng)在物理存儲上也是連續(xù)的. 索引表row key編碼方式如圖 4所示. 最高位是符號位，次高5位是格網(wǎng)層級，可表示的層級有0～31級. 低58位存儲格網(wǎng)行列號的Z曲線編碼值，該Z曲線有29階，行列號通過二進(jìn)制位交叉運(yùn)算轉(zhuǎn)化為Morton碼，每一層級最多能存儲229×229個格網(wǎng). 采用該編碼方式，索引表中的記錄首先從起始層級開始按照層級排序，同一層級的格網(wǎng)存儲位置相鄰，然后按照行列號的Z值排序. 該編碼方式既能保證同一層級格網(wǎng)的聚集性和連續(xù)性，又可避免編碼值重復(fù).

圖4 索引表行鍵編碼方式Fig.4 The coding mode of indexTable row key

多級格網(wǎng)索引表的列用于存儲該格網(wǎng)覆蓋范圍內(nèi)所有矢量要素的OID，即矢量要素在數(shù)據(jù)存儲表中的row key值. 為了將矢量要素分類存儲，本文按照矢量要素的分類碼CC劃分了column family，每一個CC碼對應(yīng)一個column family，column family中的cell存儲相應(yīng)分類下的所有矢量要素OID. 同一時間版本的矢量要素數(shù)據(jù)用time stamp標(biāo)識，與數(shù)據(jù)存儲表的time stamp保持一致. 多級格網(wǎng)索引表的邏輯結(jié)構(gòu)如圖5所示.

圖5 多級格網(wǎng)索引表邏輯結(jié)構(gòu)
Fig.5 Logical structure of multilevel grid index

2.2.3 基于MapReduce的多級格網(wǎng)索引構(gòu)建

由圖 5可知，多級格網(wǎng)索引表的一條記錄關(guān)聯(lián)一個格網(wǎng)內(nèi)的所有空間對象. 為了減少空間索引表的數(shù)據(jù)插入次數(shù)，提高索引構(gòu)建速度，本文設(shè)計了基于MapReduce并行構(gòu)建多級格網(wǎng)索引的算法.

(1)在Map階段，并行地從數(shù)據(jù)存儲表中讀取記錄，將空間對象映射到所屬格網(wǎng)，同時，記錄其CC碼和時間戳T，數(shù)據(jù)輸入輸出形式為Map： Row→list

(2) 在Reduce階段，以格網(wǎng)GID值為key，空間對象的(OID,CC,T) 作為value輸入，將與key相同的value組裝成一條索引表的記錄寫入索引表，即Reduce： 〈GID, list(OID, CC,T)〉→Row.

Map階段最關(guān)鍵的步驟在于從多級格網(wǎng)金字塔中找出能夠完全容納空間對象的最小格網(wǎng). 本文采用自頂向下的方式逐級檢查與空間對象mbr相交的格網(wǎng)個數(shù)，當(dāng)格網(wǎng)個數(shù)為1且下一級相交的格網(wǎng)個數(shù)大于1時，則認(rèn)為當(dāng)前層級的格網(wǎng)可以完全容納空間對象的最小格網(wǎng). 算法2為在多級格網(wǎng)索引中找到能夠完全容納空間對象最小格網(wǎng)的算法.

算法2查找空間對象所屬格網(wǎng)

輸入空間對象幾何信息geo，多級格網(wǎng)索引起始層級SL，終止層級EL.

輸出該要素在多級格網(wǎng)結(jié)構(gòu)中所屬格網(wǎng)G.

GetGrid (geo,SL,EL)

1L←SL

2G←NIL

3 ?根據(jù)要素幾何信息獲取其mbr

4 mbr←Get mbr (geo)

5whileL≤EL

6 ?將mbr頂點坐標(biāo)代入式(1)～式(3)，可以得到與其相交的格網(wǎng)列表

7dogridcount←

GetIntersectGridCount(L,mbr)

8ifgridcount = 1

9thenL←L+1

10G←GetIntersectGrid (L,mbr)

11else ifgridcount > 1

12returnG

Reduce階段的主要任務(wù)是生成索引表記錄，并將記錄插入索引表中. 每一條記錄代表不同時間版本下與某一格網(wǎng)關(guān)聯(lián)的所有空間對象. 經(jīng)過Map階段后，屬于同一格網(wǎng)的空間對象通過相同的GID關(guān)聯(lián)在一起，以Map輸出的GID為索引表記錄的row key，根據(jù)CC值將空間對象歸類到對應(yīng)的column family，然后按照時間戳T將OID填充入cell中. 當(dāng)所有空間對象的OID填充完畢后，將索引表記錄插入到索引表中. 算法3為生成索引表記錄算法.

算法3生成索引表記錄

輸入Map階段輸出的〈GID,list(OID,CC,T)〉，空索引表IndexTable.

輸出索引表記錄row.

Generateindexrow(〈GID,list(OID,CC,T)〉,indextable)

1 row←createrow(indextable,GID)

2foreach(OID,CC,T)inlist(OID,CC,T)

3docolumn family←

getcolumnfamily(cc,row)

4 addcellvalue(Row,column family,OID,T)

5returnRow

2.3 范圍查詢算法

空間范圍查詢是指任意給定一個多邊形，查詢在該多邊形邊界內(nèi)或與邊界相交的空間對象集合. 范圍查詢是最基本的空間數(shù)據(jù)檢索方式之一，也是地表覆蓋數(shù)據(jù)最常見的應(yīng)用需求，如結(jié)合地圖的要素繪制功能將用戶自定義區(qū)域內(nèi)的植被覆蓋情況實時展示在地圖上.

與其他空間查詢一樣，范圍查詢也分為“過濾”和“精煉”2個步驟. 在過濾階段，自頂向下逐級判斷多邊形與當(dāng)前層級格網(wǎng)的空間關(guān)系，篩選出需要進(jìn)一步精煉的格網(wǎng). 根據(jù)GIS空間對象拓?fù)潢P(guān)系[21]，可將多邊形與格網(wǎng)的空間關(guān)系歸納為以下3種： (1) 包含(contain)關(guān)系，即格網(wǎng)完全在多邊形內(nèi)部；(2) 交疊(overlap)關(guān)系，即格網(wǎng)部分在多邊形內(nèi)部；(3) 相離(disjoint)關(guān)系，即格網(wǎng)不在多邊形內(nèi)部，如圖6所示. 當(dāng)多邊形與格網(wǎng)為包含關(guān)系時，多邊形與該格網(wǎng)及其下級子格網(wǎng)中的空間對象均為包含關(guān)系，不需要進(jìn)一步精煉；當(dāng)多邊形與格網(wǎng)為交疊關(guān)系時，則該格網(wǎng)需要進(jìn)一步精煉，其下級子格網(wǎng)需進(jìn)一步判斷與多邊形的關(guān)系；當(dāng)多邊形與格網(wǎng)為相離關(guān)系時，該格網(wǎng)及其子格網(wǎng)均被過濾掉.

圖6 多邊形與格網(wǎng)的空間關(guān)系Fig.6 The topological relations of polygon and grid

算法4是為了從多級格網(wǎng)索引中獲取與多邊形為包含或交疊關(guān)系格網(wǎng)的過濾算法.

算法4范圍查詢格網(wǎng)過濾

輸入自定義多邊形P，起始搜索格網(wǎng)G，終止搜索層級EL.

輸出與P為包含關(guān)系的格網(wǎng)的集合Q,

與P為交疊關(guān)系的格網(wǎng)的集合R.

SpatialFilter(P,G,EL)

1Q←?

2R←?

3 SL←GetLevel(G)

4ifSL > EL

5then return(Q,R)

6 ?如果P與G為包含關(guān)系，則將G插入Q；如為交疊關(guān)系，則將G插入R并遞歸其下一級子格網(wǎng)

7else ifContain(P,G)

8.thenInsert(Q,G)

9else ifOverlap(P,G)

10thenInsert(R,G)

11 children←GetChildren(G)

12.foreachgridinchildren

13do(q,r)←SpatialFilter (P,grid,EL)

14 Insert(Q,q)

15 Insert(Q,r)

16return(Q,R)

在精煉階段，將集合Q中格網(wǎng)覆蓋范圍內(nèi)的所有空間對象直接作為結(jié)果集的一部分，集合R中格網(wǎng)包含的空間對象需要與多邊形做進(jìn)一步的空間關(guān)系判斷，將與多邊形相交的空間對象也插入結(jié)果集中. 算法5為根據(jù)篩選出的格網(wǎng)獲取查詢結(jié)果要素集的數(shù)據(jù)精煉算法.

算法5范圍查詢數(shù)據(jù)精煉

輸入自定義多邊形P，與P為包含關(guān)系的格網(wǎng)的集合Q，與P為交疊關(guān)系的格網(wǎng)的集合R，數(shù)據(jù)時間版本T.

輸出查詢結(jié)果要素集S.

SpatialRefinement(P,Q,R,T)

1S←?

2 ?分別獲取格網(wǎng)集合Q和R內(nèi)所有空間對象在數(shù)據(jù)存儲表中的row key集合

3 NRF←GetOIDFromGrid(Q,T)

4 RF←GetOIDFromGrid(R,T)

5 ?NR對應(yīng)空間對象可全部直接插入S中，RF中對象需與P再作相交運(yùn)算

6 Insert(S,BatchGet (NRF))

7 Insert(S, BatchGetWithRefinement(RF,P))

8ReturnS

如圖7所示，假設(shè)建立了0～3級格網(wǎng)，起始格網(wǎng)(0,0,0)，終止層級EL=3，給出一個多邊形P、要素分類碼CC和時間版本T進(jìn)行范圍查詢.

圖7 范圍查詢示例Fig.7 An example of range query

首先，進(jìn)行SpatialFilter操作.P完全在(0,0,0)內(nèi)，對(0,0,0)的4個子格網(wǎng)依次SpatialFilter直到終止層級，得到格網(wǎng)集合(Q,R). 其次對(Q,R)進(jìn)行SpatialRefinement. 對Q和R內(nèi)所有格網(wǎng)按照2.2.2節(jié)的方式編碼，以該編碼為row key值，以CC為column family，T為time stamp，掃描索引表，獲取候選空間對象的OID集合NRF和RF. 然后,以NRF和RF為row key, 繼續(xù)掃描數(shù)據(jù)存儲表獲取空間對象集合，NRF的掃描結(jié)果可以直接插入結(jié)果要素集中，RF的掃描結(jié)果則需要與P繼續(xù)求交.

3 實驗與分析

3.1 實驗環(huán)境

3.1.1 軟硬件環(huán)境

本實驗運(yùn)行于一個部署了Hadoop2.7.0，HBase 0.98.15的小型集群上，集群內(nèi)由千兆交換機(jī)連接了3臺服務(wù)器. 每臺服務(wù)器配有32 GB內(nèi)存、12個2.6 GHz的Intel(R) Xeon(R) CPU核、1TB硬盤與SUSE Linux Enterprise Server 11 (x86-64)操作系統(tǒng).

3.1.2 測試數(shù)據(jù)

實驗數(shù)據(jù)為高精度地表覆蓋數(shù)據(jù)，覆蓋浙江省90個縣級行政區(qū)，要素總量接近千萬，將數(shù)據(jù)轉(zhuǎn)換成WKT格式后大小約為16 GB.

3.2 測試內(nèi)容

3.2.1 索引構(gòu)建效率

本實驗對4組不同規(guī)模的地表覆蓋數(shù)據(jù)分別建立R-樹、四叉樹,與多級格網(wǎng)索引比較其索引構(gòu)建效率. 為了具有可比性，所有構(gòu)建過程都在單線程環(huán)境下進(jìn)行. 其中，R-樹索引采用STR算法[22]批量構(gòu)建，四叉樹與多級格網(wǎng)索引均采用插入方式構(gòu)建，多級格網(wǎng)索引建立于HBase表中，SL=6，EL=14. 測試結(jié)果如圖8所示.

圖8 不同空間索引的構(gòu)建效率對比Fig.8 Construction efficiency comparison of different spatial indexes

由4組不同規(guī)模的數(shù)據(jù)集索引構(gòu)建時間可知，相比四叉樹與R-樹索引，多級格網(wǎng)索引具有更高的構(gòu)建效率. 隨著數(shù)據(jù)集要素量的等比增加，R-樹與四叉樹構(gòu)建時間明顯上升，而多級格網(wǎng)索引構(gòu)建時間上升相對平緩. 這是因為多級格網(wǎng)索引采用預(yù)先定義格網(wǎng)層級的方式構(gòu)建，在數(shù)據(jù)插入過程中無需進(jìn)行平衡樹結(jié)構(gòu)與結(jié)點分裂等耗時操作.

此外，由于多級格網(wǎng)索引是預(yù)先定義好的靜態(tài)結(jié)構(gòu)，格網(wǎng)之間是相對獨(dú)立的，能夠很好地適應(yīng)并行范式. 為了驗證MapReduce對索引構(gòu)建效率的提升效果，本文提取了4組百萬數(shù)量級的地表覆蓋數(shù)據(jù)測試并行構(gòu)建效率. 其中，MapReduce中Map的數(shù)量為6，多級格網(wǎng)索引SL=6，EL=14. 測試結(jié)果如圖9所示，隨著要素量的增大，并行構(gòu)建索引的執(zhí)行時間上升平緩，具有較好的擴(kuò)展性.

圖9 基于MapReduce的多級格網(wǎng)索引并行構(gòu)建效率對比Fig.9 Efficiency comparison of building multigrid index in parallel based on MapReduce

3.2.2 層級對檢索效率的影響

在多級格網(wǎng)索引中，起始層級和終止層級的設(shè)定會對空間檢索效率產(chǎn)生影響. 當(dāng)層級數(shù)越多時，在空間檢索的過濾階段淘汰掉的要素越多，需要精煉的要素越少. 索引的起始層級是由地表覆蓋數(shù)據(jù)的覆蓋范圍確定的，因此終止層級才是決定索引效率的關(guān)鍵. 圖10展示了在不同終止層級條件下,基于2.3節(jié)的空間范圍查詢算法SpatialFilter與SpatialRefinement在檢索中的執(zhí)行時間對比.

圖10 不同終止層級條件下，SpatialFilter與SpatialRefinement在檢索中的執(zhí)行時間對比Fig.10 Execution time comparison between SpatialFilter and SpatialRefinement in different end level

當(dāng)終止層級為11～13時，由于格網(wǎng)劃分粒度大，需要過濾的格網(wǎng)較少，SpatialFilter成本可以忽略不計，此時每一個格網(wǎng)中包含的要素量較多，因此SpatialRefinement的時間成本較高，且隨著層級的增加而降低. 隨著層級增加，格網(wǎng)劃分變密，SpatialFilter成本逐漸增大，而SpatialRefinement的成本始終維持在穩(wěn)定狀態(tài)，這是因為更精細(xì)的格網(wǎng)劃分未能減少需要精煉的要素量，格網(wǎng)劃分已達(dá)飽和狀態(tài). 因此，以剛達(dá)到飽和狀態(tài)的格網(wǎng)層級作為終止層級是可取的，此時總時間成本最小. 一般來說，格網(wǎng)劃分達(dá)到飽和狀態(tài)，是指該層級下的格網(wǎng)包含的要素量剛好趨于穩(wěn)定，不再隨格網(wǎng)分裂顯著減少，此時，繼續(xù)劃分格網(wǎng)不再有過濾作用，因此該層級下的SpatialRefinement成本剛好達(dá)到穩(wěn)定狀態(tài)，此時檢索效率最佳.

3.2.3 范圍查詢效率

為了進(jìn)一步對比不同空間索引下的空間查詢效率，本文自定義了3個空間覆蓋范圍不同的多邊形，分別在R-樹、四叉樹與基于HBase實現(xiàn)的靜態(tài)多級格網(wǎng)索引上檢索與這些多邊形為包含或交疊關(guān)系的地表覆蓋要素集合. 測試結(jié)果如圖 11所示，當(dāng)檢索范圍較小時，3種空間索引的范圍查詢效率差別不大；隨著檢索范圍不斷擴(kuò)大，靜態(tài)多級格網(wǎng)索引體現(xiàn)出較好的性能優(yōu)勢. 這是因為地表覆蓋要素是空間全覆蓋的，而同類要素有空間聚集性，查詢范圍小時，要素種類差異不大，分布相對較均勻. 查詢范圍越大，要素種類越多，要素間差異越大，分布越不均勻. 本實驗說明面對十分密集且不均勻的空間對象時，靜態(tài)多級格網(wǎng)索引表現(xiàn)出更好的數(shù)據(jù)劃分和過濾能力.

圖11 R樹、四叉樹與多級格網(wǎng)索引的范圍查詢效率對比Fig.11 Efficiency comparison among R tree,Quadtree and multigrid index in range query

4 結(jié) 語

針對地表覆蓋數(shù)據(jù)體量龐大、要素分布密集、更新頻繁的特點，設(shè)計了一種基于HBase的靜態(tài)多級格網(wǎng)索引. 與傳統(tǒng)的四叉樹、R-樹索引不同，多級格網(wǎng)索引預(yù)先確定格網(wǎng)結(jié)構(gòu)，數(shù)據(jù)插入時不存在結(jié)點動態(tài)分裂和索引結(jié)構(gòu)調(diào)整等操作，結(jié)合MapReduce的索引并行構(gòu)建算法，能顯著縮短大規(guī)模地表覆蓋數(shù)據(jù)集空間索引的構(gòu)建時間. 此外，還設(shè)計了一種基于靜態(tài)多級格網(wǎng)索引的空間范圍查詢方法，通過多級過濾的方式，顯著提高了地表覆蓋數(shù)據(jù)空間搜索的效率. 目前，基于HBase與靜態(tài)多級格網(wǎng)索引的地表覆蓋數(shù)據(jù)空間檢索方法已應(yīng)用于浙江省地理國情數(shù)據(jù)發(fā)布系統(tǒng). 實驗與實踐結(jié)果均表明，該方法能夠快速完成大規(guī)模密集分布的地表覆蓋數(shù)據(jù)的空間索引構(gòu)建，提升空間檢索的性能，并具有很好的擴(kuò)展性.