Abstract

The widespread of geospatial services produces massive volumes of spatial data. Cloud computing is a necessity for big data management. Efficient retrieval algorithms of such data are a prerequisite. In this paper, we evaluate the efficiency of spatial indexing for huge datasets at cloud computing environment. Two of the most common data structures are selected for this study namely the R-Tree and the priority R-tree (PR-Tree). R-Tree is one of the most common access methods for spatial data. Priority R-tree is an optimal variation of the R-tree and more efficient for extreme datasets. We implemented the two data structures then we deployed them on various cloud instances with different resources. We evaluated the performance of running these applications with different spatial datasets. The query response time is also measured for both data structures. We reported the results which can be useful in retrieving huge datasets on the cloud.

References

• Leimbach T. et al. , "Potential and impacts of cloud computing services and social network websites," Science and Technology Options Assessment, 2014.
• Balasubramanian L. and Sugumaran M. , "A State-of-Art in R-Tree Variants for Spatial Indexing," International Journal of Computer Applications, vol. 42, no. 20, 2012.
• Wang Y. , Wang S. , and Zhou D. , "Retrieving and Indexing Spatial Data in the Cloud Computing Environment," in the First International Conference on Cloud Computing, Springer-Verlag, 2009.
• Dai J. , Huang J. , Huang, B. Huang S. , and Liu Y. , "HiTune: Dataflow-Based Performance Analysis for BigData Cloud," in USENIX annual technical conference, 2011.
• Yang Y. , Wu L. , Guo J. , and and Shanjunliu, "Research on Distributed Hilbert R tree Spatial Index Based on BIRCH Clustering," IEEE, 2012.
• Moreau M. and Osborn W. , "mqr-tree: A 2-dimensional Spatial Access Method," Journal Of Computer Science And Engineering, vol. 15, no. 2, 2012.
• Sharifzadeh M. and Shabani C. , "VoR-tree: R-tree with Voronoi Diagrams for Efficient Processing of Nearest Neighbour Queries," Proc. VLDB Endowment, vol. 3, no. 1, 2010.
• Manolopoulos Y. , Nanopoulos A. , and Papadopoulos N. , "R-Trees: Theory and Applications," London: Springer, 1st Edition, 2006.
• Arge L. , deBerg M. , Haverkort H. J. , and Yi K. , "The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree," in Proceedings of ACM SIGMOD Conference on Management of Data, 2004.
• Gannon D. and Reed D. A. , Parallelism and the cloud, The Fourth Paradigm ed. , 2009.
• Yang C. et al. , "Spatial cloud computing: how can the geospatial sciences use and help shape cloud computing?," International Journal of Digital Earth, 2011.
• Fielder A. , Brown I. , Frank A. , Kara S. , and Weber V. , "Cloud Computing Study," European Parliament's Committee, Internal Market and Consumer Protection 2012.
• Office of the privacy Commissioner of Canada. (2014, March ) Introduction to Cloud Computing. [Online]. http://www. priv. gc. ca/resource/fs-fi/02_05_d_51_cc_e. pdf
• Wang G. and Ng TSE, "The impact of virtualization on network performance of amazon ec2 data center," Proceedings IEEE, 2010.
• (2014, February ) R-Tree in Java with storage capabilities and an api. [Online]. https://github. com/moubarak/spatial-index
• (2014, February ) PRTree, a Priority R-Tree, a spatial index for java code. [Online]. http://www. khelekore. org/prtree/
• (2014, July ) Amazon EC2 Instances. [Online]. http://aws. amazon. com/ec2/instance-types/