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

doi:10.3969/j.issn.1006-2475.2016.11.003

计算机与现代化 ›› 2016, Vol. 0 ›› Issue (11): 12-19,24.doi: 10.3969/j.issn.1006-2475.2016.11.003

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

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. 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

摘要/Abstract

摘要： 针对矩形空间数据对象，以传统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

中图分类号:

TP301.6

徐欢1,冯钧1,张鹏程1,唐志贤2,刘艺1,陈志飞1,张立霞1. 基于Hadoop的分布式CIF四叉树索引方法[J]. 计算机与现代化, 2016, 0(11): 12-19,24.

XU Huan1, FENG Jun1, ZHANG Peng-cheng1, TANG Zhi-xian2, LIU Yi1, CHEN Zhi-fei1, ZHANG Li-xia1. Distributed CIF Quadtree Indexing Method Based on Hadoop[J]. Computer and Modernization, 2016, 0(11): 12-19,24.

参考文献

［1］郭薇,郭菁,胡志勇. 空间数据库索引技术［M］. 上海:上海交通大学出版社, 2006.
［2］ Bentley J L. Multidimensional binary search trees used for associative searching［J］. Communications of the ACM, 1975,18(9):509-517.
［3］ Robinson J T. The K-D-B-tree: A search structure for large multidimensional dynamic indexes［C］// Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data. 1981:10-18.
［4］ Beckmann N， Kriegel H P， Schneider R, et al. The R*-tree: An efficient and robust access method for points and rectangles［C］// Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. 1990:322-331.
［5］ Sellis T K, Roussopoulos N, Faloutsos C. The R+-Tree: A dynamic index for multi-dimensional objects［C］// Proceedings of the 13th International Conference on Very Large Data. 1987:507-518.
［6］ Guttman A. R-trees: A dynamic index structure for spatial searching［C］// Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. 1984:47-57.
［7］ Nievergelt J, Hinterberger H, Sevcik K C. The grid file: An adaptable, symmetric multikey file structure［J］. ACM Transactions on Database Systems, 1984,9(1):38-71.
［8］ Hutflesz A, Six H W, Widmayer P. The R-File: An efficient access structure for proximity queries［C］// Proceedings of the 6th International Conference on Data Engineering. 1990:372-379.
［9］ Kamel I, Faloutsos C. Hilbert R-tree: An improved R-tree using fractals［C］// Proceedings of the 20th International Conference on Very Large Data Bases. 1994:500-509.
［10］Zhang Chong, Xiao Weidong, Tang Daquan, et al. P2P-based multidimensional indexing methods: A survey［J］. Journal of Systems & Software, 2011,84(12):2348-2362.
［11］Koudas N， Faloutsos C， Kamel I. Declustering spatial databases on a multi-computer architecture［C］// Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology. 1996:592-614.
［12］Schnitzer B, Leutenegger S T. Master-client R-trees: A new parallel R-tree architecture［C］// Proceedings of the 11th International Conference on Scientific and Statistical Database Management. 1998:page 68.
［13］Mondal A, Kitsuregawa M, Ooi B C, et al. R-tree-based data migration and self-tuning strategies in shared-nothing spatial databases［C］// Proceedings of the 9th ACM International Symposium on Advances in Geographic Information Systems. 2001:28-33.
［14］Mouza C D， Litwin W， Rigaux P. SD-Rtree: A scalable distributed Rtree ［C］// Proceedings of the 23rd International Conference on Data Engineering. 2007:296-305.
［15］Mondal A， Yi Lifu， Kitsuregawa M. P2PR-tree: An R-tree-based spatial index for peer-to-peer environments［C］// Proceedings of the 2004 International Conference on Current Trends in Database Technology. 2004:516-525.
［16］Tanin E, Harwood A, Samet H. Using a distributed quadtree index in peer-to-peer networks［J］. The International Journal on Very Large Data Bases, 2007,16(2):165-178.
［17］Zhang Xiangyu, Ai Jing, Wang Zhongyuan, et al. An efficient multi-dimensional index for cloud data management［C］// Proceedings of the 1st International Workshop on Cloud Data Management. 2009:17-24.
［18］Wang Jinbao, Wu Sai, Gao Hong, et al. Indexing multi-dimensional data in a cloud system［C］// Proceedings of the 2010 International Conference on Management of Data. 2010:591-602.
［19］Stoica I， Morris R， Karger D, et al. Chord: A scalable peer-to-peer lookup serice for Internet applications［C］// Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. 2001:149-160.
［20］Liao Haojun, Han Jizhong, Fang Jinyun. Multi-dimensional index on Hadoop distributed file system［C］// Proceedings of the 2010 IEEE 5th International Conference on Networking, Architecture, and Storage. 2010:240-249.

[1]	张军, 苏文浩 . 基于LZO的Hadoop文件归档优化方法[J]. 计算机与现代化, 2023, 0(06): 1-6.
[2]	苏林萍，安然，李为，崔文超，张晓良. 基于Hadoop的电力运维审计系统的设计[J]. 计算机与现代化, 2020, 0(01): 49-.
[3]	石慧1，陈恩2. Spark平台的分布式阶段自适应关联规则挖掘算法[J]. 计算机与现代化, 2019, 0(12): 31-.
[4]	宋阳，石鸿雁. 基于MapReduce框架下的K-means聚类算法的改进[J]. 计算机与现代化, 2019, 0(08): 28-.
[5]	李航，臧洌，甘露. 负载均衡技术在并行化符号执行中的应用[J]. 计算机与现代化, 2018, 0(07): 86-.
[6]	周天绮. 基于移动通信大数据的城市人口空间分布统计[J]. 计算机与现代化, 2018, 0(05): 45-.
[7]	陈丽娟，谢伙生. 带负项值的onshelf效用项集并行挖掘算法[J]. 计算机与现代化, 2018, 0(04): 13-.
[8]	温贺平1,鲍晶晶2,柯居鑫1,刘树威1. 基于Hadoop的Lorenz超混沌加密算法设计[J]. 计算机与现代化, 2018, 0(03): 108-.
[9]	张春,周静. 动车组故障关联规则挖掘优化算法研究与应用[J]. 计算机与现代化, 2017, 0(9): 74-78.
[10]	朱珊，艾丽华. 基于Hadoop的大规模图像存储与检索[J]. 计算机与现代化, 2017, 0(6): 61-66+83.
[11]	李程，柴小丽，谢彬，唐鹏. 一种Hadoop YARN的资源调度机制[J]. 计算机与现代化, 2017, 0(11): 29-34.
[12]	张进，冯钧，陆佳民. 基于Hadoop的空间关键字索引方法[J]. 计算机与现代化, 2017, 0(11): 76-83.
[13]	冯钧，徐维纲，冯读庆，陆佳民，徐欢. 面向海量水利数据的索引方法研究[J]. 计算机与现代化, 2017, 0(10): 29-35,41.
[14]	李娜，陈正鸣，吕嘉，刘春芳. HDFS访问中间件的事务设计与实现[J]. 计算机与现代化, 2017, 0(1): 46-50.
[15]	孙立华1，胡牧1，孟庆强1，钱亚康1，王松2. 配网线损大数据高性能计算解决方案[J]. 计算机与现代化, 2016, 0(12): 42-46,50.

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

Distributed CIF Quadtree Indexing Method Based on Hadoop

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价