2. 浙江大学 地理信息科学研究所, 浙江 杭州 310027;
3. 中国土地勘测规划院, 北京 100035
2. Department of Geographic Information Science, Zhejiang University, Hangzhou 310027, China;
3. Chinese Land Surveying and Planning Institute, Beijing 100035, China
地表覆盖数据是地理国情监测的重要数据源[1]，是指通过对地形、水域、植被、荒漠与裸露地、人工表面等地表对象进行动态化、定量化和空间化监测而得到的一个全区域覆盖的地表面状要素集.每一要素直接反映某一地块的基础地理信息，包括几何信息与地物分类信息.这些信息为水土流失评价、森林覆盖率统计、土地利用评估等提供了可靠的数据源.高效、可靠的地表覆盖数据检索方法是挖掘地表覆盖数据潜在价值的前提.
地理国情普查中的地表覆盖数据采集以县级行政区为单位，图 1所示为某县地表覆盖数据要素分类图层.与一般的空间矢量数据相比，地表覆盖数据有以下特点：(1)要素分布密集、数据量庞大，以浙江省为例，仅德清县地表覆盖数据要素量就有15万左右(与地物分布情况及区域面积有关)，全省要素总量更可达千万级别；(2)要素形状复杂多变、面积差异大；(3)要素空间分布不均匀，河流、湖泊跨越地理范围大、分布稀疏，而人工建筑物范围小、分布密集；(4)数据定期批量更新，主要包括几何信息的修改和属性信息的更新.随着多期普查成果的录入，地表覆盖数据量将进一步增大，这为实时的空间检索与数据分析带来了严峻的挑战.
|
图 1 某县级行政区地表覆盖数据 Fig. 1 Land cover data of a county-level administrative region |
传统的关系型数据库结合空间数据引擎的空间数据检索方法，存在扩展困难、检索能力不足的弊端，无法满足海量地表覆盖数据的高效管理与检索需求[2].随着云计算技术的蓬勃发展，NoSQL数据库因其良好的扩展性、伸缩性以及强大的并行检索能力，已在多个领域得到广泛应用[3]. HBase是一种十分流行的NoSQL数据库，能为Hadoop、Spark等分布式计算平台提供无缝的数据集成.为了提高海量地表覆盖数据的空间检索效率，本文提出了一种基于HBase与静态多级格网索引的地表覆盖数据空间检索方法，该方法通过MapReduce并行构建面向地表覆盖数据特征的静态多级格网索引，通过多级过滤的方式提高空间范围查询效率，为实现海量地表覆盖数据的高效空间检索提供了新思路.
1 相关研究 1.1 HBase概述HBase是Apache Hadoop的一个子项目，是Google云计算技术BigTable[4]的开源实现. HBase是依托HDFS文件存储系统的一个面向列、可伸缩、随机实时读写访问的分布式存储系统，能存储十亿级别的结构化数据[5].
HBase表是一种稀疏的、多维的、有序的索引表.如表 1所示，HBase定义了一个四维概念模型，由行键(row key)、列簇(column family)、列修饰符(column qualifier)和时间戳(time stamp)组成.表的每一行代表一个数据对象，由row key唯一标识并按其字典序排序，所以row key的设计非常重要，设计目标是将相关联的数据相邻存储以提高数据检索的速度.一行记录由若干column family构成，代表表中数据的信息类别，在定义表前需创建好column family.每个column family可拥有任意数量的列成员，通过column qualifier识别，定义为column family：column qualifier.列的定义是动态和可变的，因此，每一列可能不同.通过行和列确定的存储单元称为单元格(cell).每个cell都保存着同一个数据对象的多个版本，版本通过time stamp索引按降序排列，读表时优先取得最新值. cell内的值由键(row key, column family：column qualifier, time stamp)唯一映射，不分类型，全部以字节码的形式存储.在物理上，HBase将行分割，按照column family存储数据，每个column family存储在HDFS的一个单独文件中.一个空cell无与键关联的值，不存储在HBase中，但在概念表中是存在的，HBase以这种方式适应稀疏行.
|
表 1 HBase数据逻辑模型 Table 1 Data logical model of HBase |
空间对象的选择查询方式主要包括空间点查询(spatial point query)、空间范围查询(spatial range query)、邻近查询(kNN, k nearest neighbor query)和空间连接(spatial join)等.由于空间实体形态和拓扑关系复杂，空间查询属于计算密集型操作，具有较高的空间和时间复杂度.空间索引是指通过建立数据逻辑与物理记录间的对应关系来描述空间数据在存储介质上位置的一种数据结构，可大大加快空间数据的访问速度.通常情况下，空间索引中存储有空间对象的最小外包矩形(mbr, minimum bounding rectangles)和唯一编码值.一次空间查询过程可以概括为“过滤”(filter)和“精炼”(refinement)[6]2个步骤. “过滤”是指从空间索引中快速筛选出其mbr满足空间查询要求的空间对象候选集. “精炼”用于确定候选集中的元素是否真的符合查询条件，其中涉及大量耗时的空间关系运算，因此，过滤阶段过滤掉的空间对象越多，查询速度就越快.
目前，针对面状地理实体的空间索引主要有R-树[7]和四叉树[8]索引以及它们的变种. R-树是一种高度平衡树，当叶子结点存储空间已满时，插入数据后会自动分裂，且向根结点传播，使整棵树结构进行动态调整直至再度达到平衡，因此数据插入效率较低，结点相互影响，不适合索引并行构建.同时，R-树兄弟结点对应的空间区域互相重叠，易导致搜索路径不唯一，当数据分布密集时，其搜索性能会大大降低，甚至降低至与线性搜索的性能一样. R+-树的空间区域无重叠，减少了无效查询，但插入和删除操作效率极低，存在跨区域空间数据冗余存储. R*-树优化了树结点分裂算法，索引结构优于R-树，但仍无法有效降低空间重叠度.在传统的四叉树索引中，空间实体只能存储在叶子结点里，当地理实体对象分布不均时，易形成深度过大的不平衡四叉树，且跨越叶子结点对应空间的空间数据重复存储，造成存储空间浪费和查询效率低下.
随着空间数据量的不断增大，人们开始在分布式环境下构建空间索引，主要围绕R-树的并行索引构建展开研究. KAMEL等[9]最早提出了基于R-树的并行查询机制，在单处理器、多磁盘的硬件环境中，采用multiplexed R-树结构，应用proximity index、最小交叉等指标优化树结构，并证明该索引结构在空间数据分布均匀时具有较优的并行查询性能. SCHNITZER等[10]提出了M-R树和MC-R树，均采用主从模式将所有非叶子结点存储在主节点上，叶子结点和空间对象直接存储在从节点上，在每个节点内构造独立索引，然后合并成总的R-树索引，这样的索引结构紧凑、存储空间利用率高，但仍未解决数据分布不均时查询效率低下的问题. ELDAWY等[11]基于Hadoop实现了空间数据处理框架SptialHadoop，采用分层设计的思想，在主节点上建立全局索引，从而将数据划分入从节点，在从节点上独立构建基于格网或R-树结构的局部索引，并利用MapReduce实现数据并行查询. CRAY等[12]基于MapReduce的R-树并行构建算法，采用Z曲线和K-means聚类方法划分空间，并行构建局部索引，但索引质量随分区数量的增加而下降.类似地，其余并行R-树索引机制[13-15]主要采用2层或多层索引结构，利用基于Hilbert曲线或Z曲线等空间聚类方法分割空间数据，在子空间区域内独立构建局部索引，在索引结构顶层合并为总索引.然而，上述索引构建算法仍无法摆脱R-树结构本身带来的索引构建效率低下和多路径查询等问题，无法提高实际应用中的数据检索速度.除此之外，人们还设计了多种R-树批量加载技术[16]，在保证查询性能的前提下，对现有静态数据进行预处理，以压缩R-树结构，提高结点空间的利用率，从而在一定程度上提升索引构建速度.较为典型的有packed R-树、Hilbert packed-R树和STR压缩算法等，但是压缩R-树无法动态插入和删除数据，故无法应用于定期更新的数据索引.
随着分布式数据库的广泛应用，不少学者提出了基于HBase的空间数据索引方案.范建永等[17]根据不同比例尺和图层创建了不同的矢量数据存储表，每个存储表对应一套按特定规则划分的格网，格网索引的row key值由Hilbert空间曲线编码确定，并利用MapReduce提高索引构建速度，但将空间数据分开存储不利于数据组织，且规则格网不适合分布不均的数据索引. HAN等[18]提出了HGrid数据模型——一种结合四叉树和规则格网的混合索引，先将空间数据按四叉树结构划分，再将四叉树格网规则划分，实验表明，在range query和kNN操作上，该模型总体性能优于四叉树索引，不如规则格网索引.张榆等[19]提出了一种空间文本数据索引结构SK-HBase，即将空间文本对象的文本信息和空间信息经Z曲线编码后作为索引表行键，并提出了2种基于SK-HBase的空间关键字查询算法. ZRA算法：将空间查询范围转化为Z曲线编码值后扫描索引表，然后在HBase服务器端进一步过滤. kd-ZRA算法：在ZRA基础上利用k-d树将Z曲线编码值划分为多个，以提高大范围空间下的扫描效率.由于没有预先将空间数据进行有效划分，仅靠Z曲线的聚类能力，过滤阶段粗滤掉的数据量是非常有限的.
地表覆盖对象不同于一般的面状空间实体，其要素形态不规整、数据体量庞大、分布极不均匀.传统的面状对象空间索引是动态建立的，面对海量空间数据，插入数据时因频繁进行索引结点分裂和索引结构调整等操作，其索引构建效率低下，且形成深层级结构，从而影响数据存取速度.同时，在数据大批量更新时，需重构索引，不适合构建基于多期数据的持久化索引.基于地表覆盖数据的特性，本文引入了支持并发构建的静态多级格网索引，将空间数据有效地划入子集，依托HBase强大的数据随机访问能力，在索引中快速定位空间对象候选集，减轻数据精炼的压力，从而提高空间数据搜索的效率.
2 地表覆盖数据空间检索设计 2.1 数据存储模型地表覆盖数据存储于HBase表中，每一条记录对应一个矢量要素、存储要素的实体和属性信息，便于以完整的地理空间实体为基本单位进行访问、添加、修改和删除操作，每一个空间对象应有唯一的编码标识和定位，这个编码就是数据表row key. HBase数据模型不能提供类似关系型数据库的关系查询功能，仅能依据row key进行数据的直接访问(get)或范围扫描(scan)，因此，row key是影响HBase数据访问和存取速度的关键，应与实际应用需求紧密结合.在地理国情普查中，地表覆盖数据采集以县级行政区为单位，分区独立编码，合并存储时会出现编码重复问题.此外，查询某一行政区划内某一地理国情分类下的要素是最常见的地表覆盖数据检索操作.为了保证同一行政区、同一分类的矢量要素在数据表中聚集存储，本文采用RegionCode+CC+FID编码方式作为矢量要素唯一编码(OID, Object ID)，并将其作为HBase数据存储表的row key.其中，Regioncode为12位行政区划编码，CC为4位地理国情分类码，FID为8位矢量要素编码.为了应对数据的批量更新操作，记录的每一条time stamp定义为不同批次数据的时间版本，访问矢量要素时默认获取最新的一条数据记录，即最新版本的要素信息.
从逻辑视图上看，地表覆盖矢量要素在数据表中首先按照行政区分区存储，在同一行政区内再根据分类码分片存储，在同一分类下按FID字典序排列，同一要素的记录按时间版本从大到小排序.
根据HBase物理模型，同属于一个column family的column存储在同一文件上，因此，为了减少磁盘访问次数，将逻辑上相关联的数据存储在同一column family下.本文在数据表中设计了2个column family：
(1) COLUMNFAMILY_GEOMETRY，包含列geometry，用于存放矢量要素实体信息，包括位置坐标和几何信息.
(2) COLUMNFAMILY_PROPERTY，存储矢量要素属性信息，包含CC、要素标题(caption)、要素长度(length)和要素面积(area)等列.
基于HBase的数据模型物理结构如图 2所示.
|
图 2 HBase数据模型物理结构 Fig. 2 Physical structure of HBase data model |
为了将地表覆盖数据划入不同的数据子集以进行空间查询的过滤操作，本文引入静态多级格网结构，并结合四叉树索引的层级剖分思想设计了地表覆盖空间索引.如图 3所示，多级格网索引的层次结构与四叉树索引类似，每一个格网在下一层级中划分为4个子格网，不同点在于多级格网是预先定义好的层级固定的静态格网结构，多个层级的格网共同构成了一个格网金字塔，在插入数据时，格网不会动态分裂，并且空间对象只存储在能完全包含其mbr的最小格网中.
|
图 3 多级格网索引结构 Fig. 3 Multi-level grid index structure |
静态多级格网索引中的每一个格网都有固定的层级(L)、行号(R)和列号(C)，(L, R, C)三元组能唯一确定多级格网金字塔中的一个格网.多级格网索引结构由起始层级(SL)和终止层级(EL)共同决定.为了满足所有地表覆盖数据的索引需求，起始层级的格网应完全覆盖所有地表覆盖对象.终止层级越大，底层格网划分得越精细，对应的空间范围就越小，空间查询时过滤的格网数就越多，精炼的空间对象相对变少，但层级并不是越多越好，层级过深时，过滤操作将耗费大量时间，精炼的数据量并不会显著变少，因此，实际应用时，需根据数据分布情况确定EL，本文实验部分有详细分析.
相较于传统的空间索引，静态多级格网索引更适应地表覆盖数据的特征，原因如下：
(1) 预定义的静态索引结构不随数据的插入和删除而改变，索引构建效率高，更适合频繁大规模更新的数据索引；
(2) 适合存储分布不均匀的空间对象，不会因索引层级过深而降低检索效率，结合有效的查询算法能规避数据分布不均衡带来的影响；
(3) 分层次分块的索引结构，有效地将空间对象划入不同尺度的空间子区域中，可以利用格网的空间关系进行空间区域粗过滤，快速定位空间对象所属区域，从而减轻数据精炼的压力；
(4) 每个空间对象只映射到一个格网，避免了数据冗余，同时在数据插入过程中，不同格网内存储的对象互不干扰，格网间互相独立.而构建并行R-树时，子树的结点分裂将影响整棵树的结构，子树间依赖程度高，因此多级格网索引更适合并行构建.
假设在全球空间范围内建立静态多级格网，则起始层级的格网是一个大小为360×360的矩形.若格网行列号从左上角起算，则空间任一点P在层级L中所处的格网行列号为
| $ gs = \frac{{360}}{{2L}}, $ | (1) |
| $ C = \frac{{{\rm{lon}}}}{{gs}}, $ | (2) |
| $ R = \frac{{180 - {\rm{lat}}}}{g}, $ | (3) |
其中，gs表示在层级L中格网的大小，lon和lat分别表示P的经度和纬度.
由式(1)~(3)，可计算全球多级格网中各个层级内所有格网的大小、行列号和顶点经纬度.获取地表覆盖要素集的覆盖范围后，计算其mbr的顶点坐标.从全球起始层级开始，向下逐级检查与该mbr相交的格网个数.当格网个数为1且下一级相交的格网个数大于1时，则认为当前层级的该格网完全容纳地表覆盖要素集的最小格网，该格网即为地表覆盖空间索引的起始搜索格网G，该层级即为索引的起始层级SL.算法1为获取多级格网索引的起始层级和搜索格网的算法.
算法1 获取起始搜索格网和起始层级
输入 要素集mbr.
输出 起始搜索格网G，起始层级SL.
GetOriginGrid (mbr)
1 L←0
2 SL←0
3 G←NIL
4 while(true)
5 do gridcount←
GetIntersectGridCount(L, MBR)
6 if gridcount = 1
7 then L ←L+1
8 G←GetIntersectGrid (L, MBR)
9 else if gridcount > 1
10 then SL=L-1
11 return(G, SL)
2.2.2 多级格网索引表设计多级格网索引表存储格网与空间对象间一对多的对应关系，是为将索引持久化到HBase表中，满足一次构建、多次使用而设计的.索引表row key标识索引结构中的一个格网(GID, Grid ID)，由格网的层级、行号和列号共同编码确定.本文利用Z曲线[20]对格网的行号和列号进行降维编码，借助Z曲线的空间聚类特性，保证同一层级相邻的格网在物理存储上也是连续的.索引表row key编码方式如图 4所示.最高位是符号位，次高5位是格网层级，可表示的层级有0~31级.低58位存储格网行列号的Z曲线编码值，该Z曲线有29阶，行列号通过二进制位交叉运算转化为Morton码，每一层级最多能存储229×229个格网.采用该编码方式，索引表中的记录首先从起始层级开始按照层级排序，同一层级的格网存储位置相邻，然后按照行列号的Z值排序.该编码方式既能保证同一层级格网的聚集性和连续性，又可避免编码值重复.
|
图 4 索引表行键编码方式 Fig. 4 The coding mode of index table row key |
多级格网索引表的列用于存储该格网覆盖范围内所有矢量要素的OID，即矢量要素在数据存储表中的row key值.为了将矢量要素分类存储，本文按照矢量要素的分类码CC划分了column family，每一个CC码对应一个column family，column family中的cell存储相应分类下的所有矢量要素OID.同一时间版本的矢量要素数据用time stamp标识，与数据存储表的time stamp保持一致.多级格网索引表的逻辑结构如图 5所示.
|
图 5 多级格网索引表逻辑结构 Fig. 5 Logical structure of multilevel grid index |
由图 5可知，多级格网索引表的一条记录关联一个格网内的所有空间对象.为了减少空间索引表的数据插入次数，提高索引构建速度，本文设计了基于MapReduce并行构建多级格网索引的算法.
(1) 在Map阶段，并行地从数据存储表中读取记录，将空间对象映射到所属格网，同时，记录其CC码和时间戳T，数据输入输出形式为Map：Row→list＜GID, (OID, CC, T)；
(2) 在Reduce阶段，以格网GID值为key，空间对象的(OID, CC, T)作为value输入，将与key相同的value组装成一条索引表的记录写入索引表，即Reduce：〈GID, list(OID, CC, T)〉→Row.
Map阶段最关键的步骤在于从多级格网金字塔中找出能够完全容纳空间对象的最小格网.本文采用自顶向下的方式逐级检查与空间对象mbr相交的格网个数，当格网个数为1且下一级相交的格网个数大于1时，则认为当前层级的格网可以完全容纳空间对象的最小格网.算法2为在多级格网索引中找到能够完全容纳空间对象最小格网的算法.
算法2 查找空间对象所属格网
输入 空间对象几何信息geo，多级格网索引起始层级SL，终止层级EL.
输出 该要素在多级格网结构中所属格网G.
GetGrid (geo, SL, EL)
1 L←SL
2 G←NIL
3 ▷根据要素几何信息获取其mbr
4 mbr←Get mbr (geo)
5 while L≤EL
6 ▷将mbr顶点坐标代入式(1)~式(3)，可以得到与其相交的格网列表
7 do gridcount←
GetIntersectGridCount(L, mbr)
8 if gridcount = 1
9 then L←L+1
10 G←GetIntersectGrid (L, mbr)
11 else if gridcount > 1
12 return G
Reduce阶段的主要任务是生成索引表记录，并将记录插入索引表中.每一条记录代表不同时间版本下与某一格网关联的所有空间对象.经过Map阶段后，属于同一格网的空间对象通过相同的GID关联在一起，以Map输出的GID为索引表记录的row key，根据CC值将空间对象归类到对应的column family，然后按照时间戳T将OID填充入cell中.当所有空间对象的OID填充完毕后，将索引表记录插入到索引表中.算法3为生成索引表记录算法.
算法3 生成索引表记录
输入 Map阶段输出的〈GID, list(OID, CC, T)〉，空索引表IndexTable.
输出 索引表记录row.
Generateindexrow(〈GID, list(OID, CC, T)〉, indextable)
1 row←createrow(indextable, GID)
2 foreach (OID, CC, T) in list(OID, CC, T)
3 do column family←
getcolumnfamily(cc, row)
4 addcellvalue(Row, column family, OID, T)
5 return Row
2.3 范围查询算法空间范围查询是指任意给定一个多边形，查询在该多边形边界内或与边界相交的空间对象集合.范围查询是最基本的空间数据检索方式之一，也是地表覆盖数据最常见的应用需求，如结合地图的要素绘制功能将用户自定义区域内的植被覆盖情况实时展示在地图上.
与其他空间查询一样，范围查询也分为“过滤”和“精炼”2个步骤.在过滤阶段，自顶向下逐级判断多边形与当前层级格网的空间关系，筛选出需要进一步精炼的格网.根据GIS空间对象拓扑关系[21]，可将多边形与格网的空间关系归纳为以下3种：(1)包含(contain)关系，即格网完全在多边形内部；(2)交叠(overlap)关系，即格网部分在多边形内部；(3)相离(disjoint)关系，即格网不在多边形内部，如图 6所示.当多边形与格网为包含关系时，多边形与该格网及其下级子格网中的空间对象均为包含关系，不需要进一步精炼；当多边形与格网为交叠关系时，则该格网需要进一步精炼，其下级子格网需进一步判断与多边形的关系；当多边形与格网为相离关系时，该格网及其子格网均被过滤掉.
|
图 6 多边形与格网的空间关系 Fig. 6 The topological relations of polygon and grid |
算法4是为了从多级格网索引中获取与多边形为包含或交叠关系格网的过滤算法.
算法4 范围查询格网过滤
输入 自定义多边形P，起始搜索格网G，终止搜索层级EL.
输出 与P为包含关系的格网的集合Q,
与P为交叠关系的格网的集合R.
SpatialFilter(P, G, EL)
1 Q←Ø
2 R←Ø
3 SL←GetLevel(G)
4 if SL＞EL
5 then return (Q, R)
6 ▷如果P与G为包含关系，则将G插入Q；如为交叠关系，则将G插入R并递归其下一级子格网
7 else if Contain(P, G)
8. then Insert(Q, G)
9 else if Overlap(P, G)
10 then Insert(R, G)
11 children←GetChildren(G)
12. foreach grid in children
13 do (q, r)←SpatialFilter (P, grid, EL)
14 Insert(Q, q)
15 Insert(Q, r)
16 return (Q, R)
在精炼阶段，将集合Q中格网覆盖范围内的所有空间对象直接作为结果集的一部分，集合R中格网包含的空间对象需要与多边形做进一步的空间关系判断，将与多边形相交的空间对象也插入结果集中.算法5为根据筛选出的格网获取查询结果要素集的数据精炼算法.
算法5 范围查询数据精炼
输入 自定义多边形P，与P为包含关系的格网的集合Q，与P为交叠关系的格网的集合R，数据时间版本T.
输出 查询结果要素集S.
SpatialRefinement(P, Q, R, T)
1 S←Ø
2 ▷分别获取格网集合Q和R内所有空间对象在数据存储表中的row key集合
3 NRF←GetOIDFromGrid(Q, T)
4 RF←GetOIDFromGrid(R, T)
5 ▷NR对应空间对象可全部直接插入S中，RF中对象需与P再作相交运算
6 Insert(S, BatchGet (NRF))
7 Insert(S, BatchGetWithRefinement(RF, P))
8 Return S
如图 7所示，假设建立了0~3级格网，起始格网(0, 0, 0)，终止层级EL=3，给出一个多边形P、要素分类码CC和时间版本T进行范围查询.
|
图 7 范围查询示例 Fig. 7 An example of range query |
首先，进行SpatialFilter操作. P完全在(0, 0, 0)内，对(0, 0, 0)的4个子格网依次SpatialFilter直到终止层级，得到格网集合(Q, R).其次对(Q, R)进行SpatialRefinement.对Q和R内所有格网按照2.2.2节的方式编码，以该编码为row key值，以CC为column family，T为time stamp，扫描索引表，获取候选空间对象的OID集合NRF和RF.然后, 以NRF和RF为row key, 继续扫描数据存储表获取空间对象集合，NRF的扫描结果可以直接插入结果要素集中，RF的扫描结果则需要与P继续求交.
3 实验与分析 3.1 实验环境 3.1.1 软硬件环境本实验运行于一个部署了Hadoop2.7.0，HBase 0.98.15的小型集群上，集群内由千兆交换机连接了3台服务器.每台服务器配有32 GB内存、12个2.6 GHz的Intel(R) Xeon(R) CPU核、1TB硬盘与SUSE Linux Enterprise Server 11 (x86-64)操作系统.
3.1.2 测试数据实验数据为高精度地表覆盖数据，覆盖浙江省90个县级行政区，要素总量接近千万，将数据转换成WKT格式后大小约为16 GB.
3.2 测试内容 3.2.1 索引构建效率本实验对4组不同规模的地表覆盖数据分别建立R-树、四叉树, 与多级格网索引比较其索引构建效率.为了具有可比性，所有构建过程都在单线程环境下进行.其中，R-树索引采用STR算法[22]批量构建，四叉树与多级格网索引均采用插入方式构建，多级格网索引建立于HBase表中，SL=6，EL=14.测试结果如图 8所示.
|
图 8 不同空间索引的构建效率对比 Fig. 8 Construction efficiency comparison of different spatial indexes |
由4组不同规模的数据集索引构建时间可知，相比四叉树与R-树索引，多级格网索引具有更高的构建效率.随着数据集要素量的等比增加，R-树与四叉树构建时间明显上升，而多级格网索引构建时间上升相对平缓.这是因为多级格网索引采用预先定义格网层级的方式构建，在数据插入过程中无需进行平衡树结构与结点分裂等耗时操作.
此外，由于多级格网索引是预先定义好的静态结构，格网之间是相对独立的，能够很好地适应并行范式.为了验证MapReduce对索引构建效率的提升效果，本文提取了4组百万数量级的地表覆盖数据测试并行构建效率.其中，MapReduce中Map的数量为6，多级格网索引SL=6，EL=14.测试结果如图 9所示，随着要素量的增大，并行构建索引的执行时间上升平缓，具有较好的扩展性.
|
图 9 基于MapReduce的多级格网索引并行构建效率对比 Fig. 9 Efficiency comparison of building multigrid index in parallel based on MapReduce |
在多级格网索引中，起始层级和终止层级的设定会对空间检索效率产生影响.当层级数越多时，在空间检索的过滤阶段淘汰掉的要素越多，需要精炼的要素越少.索引的起始层级是由地表覆盖数据的覆盖范围确定的，因此终止层级才是决定索引效率的关键. 图 10展示了在不同终止层级条件下, 基于2.3节的空间范围查询算法SpatialFilter与SpatialRefinement在检索中的执行时间对比.
|
图 10 不同终止层级条件下，SpatialFilter与SpatialRefinement在检索中的执行时间对比 Fig. 10 Execution time comparison between SpatialFilter and SpatialRefinement in different end level |
当终止层级为11~13时，由于格网划分粒度大，需要过滤的格网较少，SpatialFilter成本可以忽略不计，此时每一个格网中包含的要素量较多，因此SpatialRefinement的时间成本较高，且随着层级的增加而降低.随着层级增加，格网划分变密，SpatialFilter成本逐渐增大，而SpatialRefinement的成本始终维持在稳定状态，这是因为更精细的格网划分未能减少需要精炼的要素量，格网划分已达饱和状态.因此，以刚达到饱和状态的格网层级作为终止层级是可取的，此时总时间成本最小.一般来说，格网划分达到饱和状态，是指该层级下的格网包含的要素量刚好趋于稳定，不再随格网分裂显著减少，此时，继续划分格网不再有过滤作用，因此该层级下的SpatialRefinement成本刚好达到稳定状态，此时检索效率最佳.
3.2.3 范围查询效率为了进一步对比不同空间索引下的空间查询效率，本文自定义了3个空间覆盖范围不同的多边形，分别在R-树、四叉树与基于HBase实现的静态多级格网索引上检索与这些多边形为包含或交叠关系的地表覆盖要素集合.测试结果如图 11所示，当检索范围较小时，3种空间索引的范围查询效率差别不大；随着检索范围不断扩大，静态多级格网索引体现出较好的性能优势.这是因为地表覆盖要素是空间全覆盖的，而同类要素有空间聚集性，查询范围小时，要素种类差异不大，分布相对较均匀.查询范围越大，要素种类越多，要素间差异越大，分布越不均匀.本实验说明面对十分密集且不均匀的空间对象时，静态多级格网索引表现出更好的数据划分和过滤能力.
|
图 11 R树、四叉树与多级格网索引的范围查询效率对比 Fig. 11 Efficiency comparison among R tree, Quadtree and multigrid index in range query |
针对地表覆盖数据体量庞大、要素分布密集、更新频繁的特点，设计了一种基于HBase的静态多级格网索引.与传统的四叉树、R-树索引不同，多级格网索引预先确定格网结构，数据插入时不存在结点动态分裂和索引结构调整等操作，结合MapReduce的索引并行构建算法，能显著缩短大规模地表覆盖数据集空间索引的构建时间.此外，还设计了一种基于静态多级格网索引的空间范围查询方法，通过多级过滤的方式，显著提高了地表覆盖数据空间搜索的效率.目前，基于HBase与静态多级格网索引的地表覆盖数据空间检索方法已应用于浙江省地理国情数据发布系统.实验与实践结果均表明，该方法能够快速完成大规模密集分布的地表覆盖数据的空间索引构建，提升空间检索的性能，并具有很好的扩展性.
| [1] |
李德仁, 眭海刚, 单杰. 论地理国情监测的技术支撑[J].
武汉大学学报信息科学版, 2012, 37(5): 505–512.
LI D R, SUI H G, SHAN J. Discussion on key technologies of geographic national conditions monitoring[J]. Geomatics and Information Science of Wuhan University, 2012, 37(5): 505–512. |
| [2] | NISHIMURA S, DAS S, AGRAWAL D, et al. MD-HBase:A scalable multi-dimensional data infrastructure for location aware services[J]. IEEE International Conference on Mobile Data Management, 2011, 1(4): 7–16. |
| [3] |
申德荣, 于戈, 王习特, 等. 支持大数据管理的NoSQL系统研究综述[J].
软件学报, 2013(8): 1786–1803.
SHEN D R, YU G, WANG X T, et al. Survey on NoSQL for management of big data[J]. Journal of Software, 2013(8): 1786–1803. |
| [4] | CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable:A distributed storage system for structured data[J]. ACM Transactions on Computer Systems, 2008, 26(2): 205–218. |
| [5] | GEORGE L. HBase:The definitive guide[J]. Andre, 2011, 12(1): 1–4. |
| [6] | MANOLOPOULO Y, THEODORIDIS Y, TSOTRAS V J. Spatial Indexing Techniques[M]. New York: Springer, 2009: 2702-2707. |
| [7] | GUTTMAN A. R-trees:A dynamic index structure for spatial searching[J]. ACM SIGMOD Record, 1984, 14(2): 47–57. DOI:10.1145/971697 |
| [8] | FINKEL R A, BENTLEY J L. Quad trees:A data structure for retrieval on composite keys[J]. Acta Informatica, 1974, 4(1): 1–9. DOI:10.1007/BF00288933 |
| [9] | KAMEL I, FALOUTSOS C. Parallel R-trees[J]. ACM SIGMOD Record, 1992, 21(2): 195–204. DOI:10.1145/141484 |
| [10] | SCHNITZER B, LEUTENEGGER S T. Master-client R-trees: A new parallel R-tree architecture[C]//Statistical and Scientific Database Management. Denver: University of Denver, 1999: 68-77. http://dl.acm.org/citation.cfm?id=831524 |
| [11] | ELDAWY A, MOKBEL M F. SpatialHadoop: A MapReduce framework for spatial data[C]//IEEE International Conference on Data Engineering. Seoul: IEEE Computer Society, 2015: 1352-1363. SpatialHadoop: A MapReduce framework for spatial data |
| [12] | CARY A, SUN Z, HRISTIDIS V, et al. Experiences on processing spatial data with MapReduce[J]. International Conference on Scientific & Statistical Database Management, 2009, 5566: 302–319. |
| [13] |
赵园春, 李成名, 赵春宇. 基于R树的分布式并行空间索引机制研究[J].
地理与地理信息科学, 2007, 23(6): 38–41.
ZHAO Y C, LI C M, ZHAO C Y. Research on the distributed parallel spatial indexing schema based on R-tree[J]. Geography and Geo-Information Science, 2007, 23(6): 38–41. DOI:10.3969/j.issn.1672-0504.2007.06.009 |
| [14] |
付仲良, 刘思远, 田宗舜, 等. 基于多级R-tree的分布式空间索引及其查询验证方法研究[J].
测绘通报, 2012(11): 42–46.
FU Z L, LIU S Y, TIAN Z S, et al. Research on the distributed spatial index based on hierarchical R-tree with query verification method[J]. Bulletin of Surveying and Mapping, 2012(11): 42–46. |
| [15] |
刘义. 大规模空间数据的高性能查询处理关键技术研究[D]. 长沙: 国防科学技术大学, 2013.
LIU Y. Research on Key Technologies of High Performance Spatial Query Processing for Large Scale Spatial Data[D]. Changsha: National University of Defense Technology, 2013. http://cdmd.cnki.com.cn/Article/CDMD-90002-1015959054.htm |
| [16] |
张明波, 陆锋, 申排伟, 等. R树家族的演变和发展[J].
计算机学报, 2005, 28(3): 289–300.
ZHANG M B, LU F, SHEN P W, et al. The evolvement and process of R-tree family[J]. Chinese Journal of Computers, 2005, 28(3): 289–300. DOI:10.3321/j.issn:0254-4164.2005.03.001 |
| [17] |
范建永, 龙明, 熊伟. 基于HBase的矢量空间数据分布式存储研究[J].
地理与地理信息科学, 2012, 28(5): 39–42.
FAN J Y, LONG M, XIONG W. Research of vector spatail data distributed storage based on HBase[J]. Geography and Geo-Information Science, 2012, 28(5): 39–42. |
| [18] | HAN D, STROULIA E. HGrid:A data model for large geospatial data sets in HBase[J]. IEEE Sixth International Conference on Cloud Computing, 2013, 8201: 910–917. |
| [19] |
张榆, 马友忠, 孟小峰. 一种基于HBase的高效空间关键字查询策略[J].
小型微型计算机系统, 2012(10): 2141–2146.
ZHANG Y, MA Y Z, MENG X F. Efficient processing of spatial keyword queries on HBase[J]. Journal of Chinese Computer Systems, 2012(10): 2141–2146. DOI:10.3969/j.issn.1000-1220.2012.10.005 |
| [20] | ASANO T, RANJAN D, ROOS T, et al. Space-filling curves and their use in the design of geometric data structures[J]. Theoretical Computer Science, 1995, 181(1): 3–15. |
| [21] | EGENHOFER M J, HERRING J R. A mathematical framework for the definition of topological relationships[C]//BRASSEL K, KISHIMOTO H. Proceeding of the Fourth International Symposium on Spatial Data Handling. Zurich: JGU, 1990: 803-813. https://www.researchgate.net/publication/239595718_A_mathematical_framework_for_the_definition_of_topological_relationships |
| [22] | LEUTENGGER S T, EDGINGTON J M, LOPEZ M A. STR: A simple and efficient algorithm for R-tree packing[C]//International Conference on Data Engineering. Birmingham: IEEE, 1997: 497-506. http://dl.acm.org/citation.cfm?id=653437 |