Distributed CIF Quadtree Indexing Method Based on Hadoop

doi:10.3969/j.issn.1006-2475.2016.11.003

Abstract

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

CLC Number:

TP301.6

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, doi: 10.3969/j.issn.1006-2475.2016.11.003.

References

［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]	FU Hong-lin, ZHANG Tai-hong, YANG Ya-ting, Aizimaiti Aiwanier, MA Bo. Scenes Text Modification Network for Uyghur Based on Generative Adversarial Network [J]. Computer and Modernization, 2024, 0(01): 41-46.
[2]	LI Xiang, ZHUANG Yi. Critical Fault Point Identification Method for Routing Algorithms Using XGBoost [J]. Computer and Modernization, 2023, 0(11): 75-81.
[3]	LI Shi-yue, MENG Jia-na, YU Yu-hai, LI Xue-ying, XU Ying-ao. Aspect Based Sentiment Analysis Model Based on Knowledge Enhancement [J]. Computer and Modernization, 2023, 0(10): 1-8.
[4]	LIU Rui-xue, LI Wen, LIU Fang, DU Shou-guo. Prediction of Time Series with Missing Value Based on Tensor Autoregressive Completion [J]. Computer and Modernization, 2023, 0(09): 51-58.
[5]	TANG Yu-lin, HUANG Deng-shan, CHEN Shu-lu, CHEN Peng-ming. SFIM Image Fusion Method Combining IHS and Adaptive Filtering [J]. Computer and Modernization, 2023, 0(09): 70-76.
[6]	MAO Ming-yang, XU Sheng-chao. Continuous Attribute Discretization Algorithm of Rough Sets for BP Neural Networks Based on Particle Swarm Optimization#br# [J]. Computer and Modernization, 2023, 0(09): 115-119.
[7]	LIU Xian-zhuo, DENG Wei-si, XIE En-yan. Adaptive Protection System for Distribution Network Considering Grid Connection of Distributed Generation [J]. Computer and Modernization, 2023, 0(09): 120-126.
[8]	WANG Jia-chen, ZHANG Hong-xin, LIU Qing-hua, . CT Image Generation of Pneumonia Based on Generative Adversarial Network [J]. Computer and Modernization, 2023, 0(07): 20-24.
[9]	ZHANG Jun, SU Wen-hao. Optimization Method of Hadoop File Archiving Based on LZO [J]. Computer and Modernization, 2023, 0(06): 1-6.
[10]	SU Jin-ku, GUI Zhi-ming. Prediction of Short-term Taxi Flow Based on Spatio-temporal Characteristics [J]. Computer and Modernization, 2023, 0(05): 32-38.
[11]	PENG Sui, XU Liang, ZHANG Zhi-qiang, LOU Yuan-yuan, YU Hao, QIN Xiao-hui. Probabilistic Voltage Stability Evaluation Algorithm Based on Mixed Vine Copula and ILHS [J]. Computer and Modernization, 2022, 0(12): 6-12.
[12]	WANG Ying-ying, ZHUANG Yi, SUN Yi-fan. Reliability Evaluation Model of BP Neural Network Based on Particle Swarm Optimization [J]. Computer and Modernization, 2022, 0(12): 42-49.
[13]	WEN Zi-xin, LI Shao-ying, WANG Bin-cheng, LIU Bo, . Face Clustering Method Based on Nearest Neighborhood Aggregation [J]. Computer and Modernization, 2022, 0(12): 81-87.
[14]	GAO Feng, ZHUANG Yi, LIU Xiao. A Trusted Transmission Scheme of SDN Based on Path Tracking Feedback [J]. Computer and Modernization, 2022, 0(12): 102-110.
[15]	MIAO Zi-jing, MEI Xin. Chinese Event Detection Based on Multi-lexicon Feature Augmentation [J]. Computer and Modernization, 2022, 0(09): 13-18.