计算机与现代化

• 算法设计与分析 • 上一篇    下一篇

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

  

  1. 1.河海大学计算机与信息学院,江苏南京211100;2.中国电子科技集团公司第二十八研究所,江苏南京210007
  • 收稿日期:2016-05-06 出版日期:2016-11-15 发布日期:2016-11-23
  • 作者简介:徐欢(1992-),女,江苏高邮人,河海大学计算机与信息学院硕士研究生,研究方向:时空数据管理,数据挖掘; 冯钧(1969-),女,教授,博士,研究方向:时空间数据管理,智能数据处理与数据挖掘,水利信息化; 张鹏程(1981-),男,副教授,博士,研究方向:软件工程,数据挖掘,水利信息化; 唐志贤(1981-),男,博士,研究方向:时空数据管理; 刘艺(1992-),男,硕士研究生,研究方向:信息检索; 陈志飞(1993-),女,硕士研究生,研究方向:数据挖掘; 张立霞(1990-),女,硕士研究生,研究方向:数据索引。
  • 基金资助:
    国家自然科学基金面上项目(61370091); 国家科技支撑计划项目(2015BAB07B00)

Distributed CIF Quadtree Indexing Method Based on Hadoop

  1. 1. College of Computer and Information, Hohai University, Nanjing 211100, China;
    2. The 28th Research Institute of China Electronics Technology Group Corporation, Nanjing 210007, China
  • Received:2016-05-06 Online:2016-11-15 Published:2016-11-23

摘要: 针对矩形空间数据对象,以传统CIF四叉树索引技术为基础,利用Hadoop平台与MapReduce并行编程模型,采用“分而治之”的思想,对数据空间进行划分,设计适用于分布式环境的创建索引、相交查询、区域删除的并行算法。在此基础上,通过改变数据集中矩形对象的数目与map数进行实验,分析并行创建与相交查询的效率。实验结果表明,对于大数据量的数据集与多数据集,并行创建与查询可以提高处理效率。

关键词: Hadoop, MapReduce, CIF四叉树, 分布式环境, 并行算法

Abstract:  We design some algorithms about parallel index creation, intersection query and regional remove for the rectangle objects, 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 changing the size of data sets of rectangle objects and the number of the map tasks. The experiments results show that using parallel algorithms of the parallel index creation and intersection queries can improve the processing efficiency for large data sets.

Key words:  , Hadoop;MapReduce; CIF quadtree; distributed environment; parallel algorithm

中图分类号: