基于Hadoop的分布式CIF四叉树索引方法  

Distributed CIF Quadtree Indexing Method Based on Hadoop

作　　者：徐欢[1] 冯钧[1] 张鹏程[1] 唐志贤[2] 刘艺[1] 陈志飞[1] 张立霞[1] 

机构地区：[1]河海大学计算机与信息学院,江苏南京211100 [2]中国电子科技集团公司第二十八研究所,江苏南京210007

出　　处：《计算机与现代化》2016年第11期12-19,24,共9页Computer and Modernization

基　　金：国家自然科学基金面上项目(61370091);国家科技支撑计划项目(2015BAB07B00)

摘　　要：针对矩形空间数据对象,以传统CIF四叉树索引技术为基础,利用Hadoop平台与MapReduce并行编程模型,采用"分而治之"的思想,对数据空间进行划分,设计适用于分布式环境的创建索引、相交查询、区域删除的并行算法。在此基础上,通过改变数据集中矩形对象的数目与map数进行实验,分析并行创建与相交查询的效率。实验结果表明,对于大数据量的数据集与多数据集,并行创建与查询可以提高处理效率。We design some algorithms about parallel index creation, intersection query and regional remove for the rectangle ob- jects, which are suitable for the distributed environment. These algorithms rely on the methods of dividing the data space, as well as the idea of divide-and-conquer. And they are based on the CIF indexing techniques supported by the Hadoop platform and the MapReduce programming model. On this basis, we test the parallel index creation and intersection queries＇s efficiency by chan- ging the size of data sets of rectangle objects and the number of the map tasks. The experiments results show that using parallel al- gorithms of the parallel index creation and intersection queries can improve the processing efficiency for large data sets.

关 键 词：HADOOP MAPREDUCE CIF四叉树 分布式环境 并行算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]