M-Quadtree索引:一种基于改进四叉树编码方法的云存储环境下空间索引方法
2016-12-07付仲良胡玉龙翁宝凤
付仲良,胡玉龙,翁宝凤,彭 瑞
1. 武汉大学遥感信息工程学院,湖北 武汉 430079; 2. 浙江省地理信息中心,浙江 杭州 310012
M-Quadtree索引:一种基于改进四叉树编码方法的云存储环境下空间索引方法
付仲良1,胡玉龙1,翁宝凤1,彭 瑞2
1. 武汉大学遥感信息工程学院,湖北 武汉 430079; 2. 浙江省地理信息中心,浙江 杭州 310012
为了解决基于“键-值”模型的云存储环境仅支持简单的关键字查询,不支持多维空间查询的问题,提出了一种新的分布式空间索引方法——M-Quadtree索引。在索引构建过程中,设计了一种基于改进四叉树的空间数据划分方法,该方法规定了叶节点区域的最小数据量,通过四叉树叶节点的再合并,解决了划分后各子区域间存储量不平衡的问题,并且满足了MapReduce并行化要求。给出了MapReduce框架下M-Quadtree索引的快速构建、查询与更新算法,并在搭建的Hadoop平台进行了关键参数对索引效率的影响以及不同规模数据下索引的创建、查询和更新试验。与现有分布式空间索引的对比试验及分析结果表明,M-Quadtree索引在数据存储量负载均衡、算法并行化和空间查询效率等方面表现得更好。
云存储;MapReduce;空间数据管理;空间索引;空间数据划分
地理信息科学在21世纪遇到了数据密集、计算密集、并发访问密集和时空密集的挑战[1]。近年来在IT领域飞速发展的云计算技术的超大规模、虚拟化、高性能、高可靠性等特点给大规模空间数据处理提供了机遇[2-6]。云存储是在云计算环境下针对数据存储发展出来的一个新概念,是指通过计算机集群的应用、分布式文件系统或网格技术等,把网络中各种类型的存储设备在应用软件协助下集合起来,共同为用户提供透明的数据存储服务[7]。……
