A k-d tree-based algorithm to parallelize Kriging interpolation of big spatial data

References

• Abel, D. J., and D. M. Mark. 1990. “A Comparative Analysis of Some Two-Dimensional Orderings.” International Journal of Geographical Information Systems 4 (1): 21–31. doi:10.1080/02693799008941526.
   Google Scholar
• Abugov, D. 2004. Oracle Spatial Partitioning: Best Practices (an Oracle White Paper). Redwood Shores, CA: Oracle Inc.
   Google Scholar
• Al-Furajh, I., S. Aluru, S. Goil, and S. Ranka. 2000. “Parallel Construction of Multidimensional Binary Search Trees.” IEEE Transactions on Parallel and Distributed Systems 11 (2): 136–148. doi:10.1109/71.841750.
   Web of Science ®Google Scholar
• Armstrong, M. P. 2000. “Geography and Computational Science.” Annals of the Association of American Geographers 90 (1): 146–156. doi:10.1111/0004-5608.00190.
   Web of Science ®Google Scholar
• Arpaci-Dusseau, R. H., and A. C. Arpaci-Dusseau. 2012. “Scheduling Introduction.” In Operating Systems: Three Easy Pieces, Arpaci-Dusseau Books, 7–8, University of Wisconsin: Madison.
   Google Scholar
• Bentley, J. L. 1975. “Multidimensional Binary Search Trees Used for Associative Searching.” Communications of the ACM 18 (9): 509–517. doi:10.1145/361002.361007.
   Web of Science ®Google Scholar
• Brinkhoff, T., H. P. Kriegel, and B. Seeger. 1996. “Parallel Processing of Spatial Joins Using R-Trees.” In Proceedings of the Twelfth International Conference on Data Engineering, February 258–265. New Orleans, LA: IEEE.
   Google Scholar
• Burrough, P. A. 1986. Principles of Geographical Information Systems for Land Resources Assessment, 193. Oxford: Oxford University Press.
   Google Scholar
• Chai, T., and R. R. Draxler. 2014. “Root Mean Square Error (RMSE) or Mean Absolute Error (MAE)?-Arguments Against Avoiding RMSE in the Literature.” Geoscientific Model Development 7: 1247–1250. doi:10.5194/gmd-7-1247-2014.
   Web of Science ®Google Scholar
• Cheng, T. 2013. “Accelerating Universal Kriging Interpolation Algorithm Using CUDA-Enabled GPU.” Computers & Geosciences 54: 178–183. doi:10.1016/j.cageo.2012.11.013.
   Web of Science ®Google Scholar
• Choi, B., R. Komuravelli, V. Lu, H. Sung, R. L. Bocchino, S. V. Adve, and J. C. Hart. 2010. “Parallel SAH K-D Tree Construction.” In Proceedings of the Conference on High Performance Graphics, Switzerland, June 77–86.
   Google Scholar
• Clematis, A., M. Mineter, and R. Marciano. 2003. “High Performance Computing with Geographical Data.” Parallel Computing 29 (10): 1275–1279. doi:10.1016/j.parco.2003.07.001.
   Web of Science ®Google Scholar
• Dobre, C., and F. Xhafa. 2013. “Parallel Programming Paradigms and Frameworks in Big Data Era.” International Journal of Parallel Programming 42 (5): 701–738. doi:10.1007/s10766-013-0272-7.
   Web of Science ®Google Scholar
• Farber, R. 2012. “Data and Task Parallelism.” In CUDA Application Design and Development, Robyn Day, 18–19, San Francisco: Morgan Kaufmann.
   Google Scholar
• Filippi, A. M., B. L. Bhaduri, T. Naughton, A. L. King, S. L. Scott, and I. Güneralp. 2012. “Hyperspectral Aquatic Radiative Transfer Modeling Using a High-Performance Cluster Computing-Based Approach.” GIScience & Remote Sensing 49 (2): 275–298. doi:10.2747/1548-1603.49.2.275.
   Web of Science ®Google Scholar
• Guan, Q., and K. C. Clarke. 2010. “A General-Purpose Parallel Raster Processing Programming Library Test Application Using a Geographic Cellular Automata Model.” International Journal of Geographical Information Science 24 (5): 695–722. doi:10.1080/13658810902984228.
   Web of Science ®Google Scholar
• Guan, Q., P. C. Kyriakidis, and M. F. Goodchild. 2011. “A Parallel Computing Approach to Fast Geostatistical Areal Interpolation.” International Journal of Geographical Information Science 25 (8): 1241–1267. doi:10.1080/13658816.2011.563744.
   Web of Science ®Google Scholar
• Hawick, K. A., P. D. Coddington, and H. A. James. 2003. “Distributed Frameworks and Parallel Algorithms for Processing Large-Scale Geographic Data.” Parallel Computing 29 (10): 1297–1333. doi:10.1016/j.parco.2003.04.001.
   Web of Science ®Google Scholar
• Healy, M. J. R. 1984. “The Use of R2 as a Measure of Goodness of Fit.” Journal of the Royal Statistical Society 147 (4): 608–609. doi:10.2307/2981848.
   Google Scholar
• Henrich, A., H. W. Six, F. Hagen, and P. Widmayer. 1989. “The LSD-Tree: Spatial Access to Multidimensional Point and Non-Point Objects.” In Proceedings of the 15th International Conference on Very Large Data Bases, San Francisco, July 45–53.
   Google Scholar
• Kamel, I., and C. Faloutsos. 1994. “Hilbert R-tree: An Improved R-Tree Using Fractals.” In Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, September 500–509.
   Google Scholar
• Madsen, K., H. B. Nielsen, and O. Tingleff. 2004. “The Levenberg–Marquardt Method.” In Methods for Non-Linear Least Squares Problems, 24–29. Lyngby: Informatics and Mathematical Modelling. Technical University of Denmark.
   Google Scholar
• Oliver, M. A., and R. Webster. 1990. “Kriging: A Method of Interpolation for Geographical Information Systems.” International Journal of Geographical Information Systems 4 (3): 313–332. doi:10.1080/02693799008941549.
   Google Scholar
• Pesquer, L., A. Cortés, and X. Pons. 2011. “Parallel Ordinary Kriging Interpolation Incorporating Automatic Variogram Fitting.” Computers & Geosciences 37 (4): 464–473. doi:10.1016/j.cageo.2010.10.010.
   Web of Science ®Google Scholar
• Samet, H. 1980. “Region Representation: Quadtrees from Binary Arrays.” Computer Graphics and Image Processing 13 (1): 88–93. doi:10.1016/0146-664X(80)90118-5.
   Google Scholar
• Samet, H. 1982. “Neighbor Finding Techniques for Images Represented by Quadtrees.” Computer Graphics and Image Processing 18 (1): 37–57. doi:10.1016/0146-664X(82)90098-3.
   Google Scholar
• Shi, X., M. Huang, H. You, C. Lai, and Z. Chen. 2014. “Unsupervised Image Classification over Supercomputers Kraken, Keeneland and Beacon.” GIScience & Remote Sensing 51 (3): 321–338. doi:10.1080/15481603.2014.920229.
   Web of Science ®Google Scholar
• Shi, X., and F. Ye. 2013. “Kriging Interpolation over Heterogeneous Computer Architectures and Systems.” GIScience & Remote Sensing 50 (2): 196–211. doi:10.1080/15481603.2013.793480.
   Web of Science ®Google Scholar
• Tahmasebi, P., M. Sahimi, G. Mariethoz, and A. Hezarkhani. 2012. “Accelerating Geostatistical Simulations Using Graphics Processing Units (GPU).” Computers & Geosciences 46: 51–59. doi:10.1016/j.cageo.2012.03.028.
   Web of Science ®Google Scholar
• Turton, I., and S. Openshaw. 1998. “High-Performance Computing and Geography: Developments, Issues, and Case Studies.” Environment and Planning A 30 (10): 1839–1856. doi:10.1068/a301839.
   Web of Science ®Google Scholar
• Wald, I., and V. Havran. 2006. “On Building Fast KD-Trees for Ray Tracing, and on Doing That in O (N log N).” In IEEE Symposium on Interactive Ray Tracing, Salt Lake City, September 61–69. doi:10.1109/RT.2006.280216.
   Google Scholar
• Wang, S., and M. P. Armstrong. 2003. “A Quadtree Approach to Domain Decomposition for Spatial Interpolation in Grid Computing Environments.” Parallel Computing 29 (10): 1481–1504. doi:10.1016/j.parco.2003.04.003.
   Web of Science ®Google Scholar
• Wu, W., Y. Rui, F. Su, L. Cheng, and J. Wang. 2014. “Novel Parallel Algorithm for Constructing Delaunay Triangulation Based on a Twofold-Divide-and-Conquer Scheme.” GIScience & Remote Sensing 51 (5): 537–554. doi:10.1080/15481603.2014.946666.
   Web of Science ®Google Scholar
• Yin, L., S.-L Shaw, D. Wang, E. A. Carr, M. W. Berry, L. J. Gross, and E. J. Comiskey. 2012. “A Framework of Integrating GIS and Parallel Computing for Spatial Control Problems - a Case Study of Wildfire Control.” International Journal of Geographical Information Science 26 (4): 621–641. doi:10.1080/13658816.2011.609487.
   Web of Science ®Google Scholar
• Zhou, Y., Q. Zhu, and Y. T. Zhang. 2007. “A Spatial Data Partitioning Algorithm Based on Spatial Hierarchical Decomposition Method of Hilbert Space-Filling Curve.” Geography and Geo-Information Science 4 5. doi:10.11834/jig.20131016.
   Google Scholar