High-performance quadtree constructions on large-scale geospatial rasters using GPGPU parallel primitives

References

• Aboulnaga, A. and Aref, W.G., 2001. Window query processing in linear quadtrees. Distributed and Parallel Databases, 10 (2), 111–126.
   Web of Science ®Google Scholar
• Ali, M.H., Saad, A.A., and Ismail, M.A., 2005. The PN-tree: a parallel and distributed multidimensional index. Distributed and Parallel Databases, 17 (2), 111–133.
   Web of Science ®Google Scholar
• Akdogan, A., et al., 2010. Voronoi-based geospatial query processing with MapReduce. Proceedings of the IEEE second international conference on cloud computing technology and science (CloudCom’10), Indianapolis, IN, USA, Nov. 30 2010-Dec. 3 2010. Washington DC: IEEE Press, 9–16.
   Google Scholar
• Armstrong, M.P., Pavlik, C.E.,, and Marciano, R., 1994. Parallel-processing of spatial statistics. Computers and Geosciences, 20 (2), 91–104.
   Google Scholar
• Bell, N. and Hoberock, J., 2011. Thrust: a productivity-oriented library for CUDA. In: W.-M.W. Hwu, ed. GPU computing gems. Jade edition. Burlington, MA: Morgan Kaufmann.
   Google Scholar
• Cary, A., 2009. Experiences on processing spatial data with MapReduce. In: M. Winslett, ed. Proceedings of the 21st international conference on scientific and statistical database management (SSDBM’09), News Orleans, USA, June 2–4 2009. New York: Springer, 302–319.
   Google Scholar
• Chan, Y.K. and Chang, C.C., 2004. Block image retrieval based on a compressed linear quadtree. Image and Vision Computing, 22 (5), 391–397.
   Web of Science ®Google Scholar
• Chung, K.L., Liu, Y.W., and Yan, W.M., 2006. A hybrid gray image representation using spatial- and DCT-based approach with application to moment computation. Journal of Visual Communication and Image Representation, 17 (6), 1209–1226.
   Web of Science ®Google Scholar
• Cignoni, P., et al., 1997. Speeding up isosurface extraction using interval trees. IEEE Transactions on Computer Graphics, 3 (2), 158–170.
   Web of Science ®Google Scholar
• Clematis, A., Mineter M., and Marciano, R., 2003. High performance computing with geographical data. Parallel Computing, 29 (10), 1275–1279.
   Web of Science ®Google Scholar
• Dean, J. and Ghemawat S., 2010. MapReduce: a flexible data processing tool. Communications of the ACM, 53 (1), 72–77.
   Web of Science ®Google Scholar
• Gaede, V. and Gunther, O., 1998. Multidimensional access methods. ACM Computing Surveys, 30 (2), 170–231.
   Web of Science ®Google Scholar
• Garland, M. and Kirk, D.B., 2010. Understanding throughput-oriented architectures. Communications of the ACM, 53 (11), 58–66.
   Google Scholar
• Gress, A. and Klein, R., 2004. Efficient representation and extraction of 2-manifold isosurfaces using kd-trees. Graphical Models, 66 (6), 370–397.
   Web of Science ®Google Scholar
• Guan, Q. and Clarke, K., 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.
   Web of Science ®Google Scholar
• Han, S. H., et al., 2009. Parallel processing method for airborne laser scanning data using a PC cluster and a virtual grid. Sensors, 9 (4), 2555–2573.
   PubMed Web of Science ®Google Scholar
• Hennessy, J.L. and Patterson, D.A., 2011. Computer architecture: a quantitative approach 5th ed. Waltham, MA: Morgan Kaufmann.
   Google Scholar
• Hoel, E.G. and Samet, H., 2003. Data-parallel polygonization. Parallel Computing, 29 (10), 1381–1401.
   Web of Science ®Google Scholar
• Hong, S., et al., 2011. Accelerating CUDA graph algorithms at maximum warp. Proceedings of the 16th ACM symposium on Principles and practice of parallel programming (PPoPP ‘11), San Antonio, TX, USA, February 12–16 2011. New York: ACM Press, 267–276.
   Google Scholar
• Hwu, W.-M.W., eds., 2011a. GPU computing gems. Emerald edition. Waltham, MA: Morgan Kaufmann.
   Google Scholar
• Hwu, W.-M.W., eds., 2011b. GPU computing gems. Jade edition. Waltham, MA: Morgan Kaufmann.
   Google Scholar
• Kamel, I. and Faloutsos, C., 1992. Parallel r-trees. Proceedings of the ACM SIGMOD international conference on management of data (SIGMOD’92), San Diego, CA, USA, June 2–5 1992. New York: ACM Press, 195–204.
   Google Scholar
• Lin, T.W., 1997. Compressed quadtree representations for storing similar images. Image and Vision Computing, 15 (11), 833–843.
   Web of Science ®Google Scholar
• Liu, Y., et al., 2010. A MapReduce approach to Gi*(d) spatial statistic. Proceedings of the ACM SIGSPATIAL international workshop on high performance and distributed geographic information systems (HPDGIS’10), 11–18.
   Google Scholar
• Luo, L., Wong, M.D.F., and Leong, L., 2011. Parallel implementation of R-trees on the GPU. Proceedings of the 17th Asia and South Pacific design automation conference (ASP-DAC), Sydney, Australia, Jan. 30–Feb. 2 2012. Washington DC: IEEE, 353–358.
   Google Scholar
• Manolopoulos, Y., et al., 2001. A generalized comparison of linear representations of thematic layers. Data & Knowledge Engineering, 37 (1), 1–23.
   Web of Science ®Google Scholar
• Manouvrier, M., 2002. Quadtree representations for storage and manipulation of clusters of images. Image and Vision Computing, 20 (7), 513–527.
   Web of Science ®Google Scholar
• McCool, M., Reinders, J., and Reinders, J., 2012. Structured parallel programming: patterns for efficient computation. Waltham, MA: Morgan Kaufmann.
   Google Scholar
• Mineter, M., 2003. A software framework to create vector-topology in parallel GIS operations. International Journal of Geographical Information Science, 17 (3), 203–222.
   Web of Science ®Google Scholar
• Molnár, F., et al., 2010. Air pollution modelling using a graphics processing unit with CUDA. Computer Physics Communications, 181 (1), 105–112.
   Web of Science ®Google Scholar
• Morton, G.M., 1966. A computer-oriented geodetic data base and a new technique in file sequencing. Ottawa: IBM Technical report.
   Google Scholar
• Ortega, L. and Rueda, A., 2010. Parallel drainage network computation on CUDA. Computers and Geosciences, 36 (2), 171–178.
   Web of Science ®Google Scholar
• Oryspayev, D., et al., 2012. LiDAR data reduction using vertex decimation and processing with GPGPU and multicore CPU technology. Computers and Geosciences, 43, 118–125.
   Web of Science ®Google Scholar
• Patel, J.M. and DeWitt, D.J., 2000. Clone join and shadow join: two parallel spatial join algorithms. Proceedings of the 8th ACM international symposium on advances in geographic information systems (GIS’00), McLean, VA, USA, November 6–11 2000, New York: ACM Press, 54–61.
   Google Scholar
• Qin C.-Z. and Zhan, L., 2012. Parallelizing flow-accumulation calculations on graphics processing units: from iterative DEM preprocessing algorithm to recursive multiple-flow-direction algorithm. Computers & Geosciences, 43, 7–16.
   Web of Science ®Google Scholar
• Raman, R. and Wise, D.S., 2008. Converting to and from dilated integers. IEEE Transactions on Computers, 57 (4), 567–573.
   Web of Science ®Google Scholar
• Samet, H., 1984. The quadtree and related hierarchical data structures. ACM Computing Surveys, 16 (2), 187–260.
   Web of Science ®Google Scholar
• Samet, H. 1985. Data-structures for quadtree approximation and compression. Communications of the ACM, 28 (9), 973–993.
   Web of Science ®Google Scholar
• Samet, H., 2005. Foundations of multidimensional and metric data structures. San Francisco, CA: Morgan Kaufmann Publishers Inc.
   Google Scholar
• Schmit, T.J., et al., 2009. High-spectral- and high-temporal resolution infrared measurements from geostationary orbit. Journal of Atmospheric and Oceanic Technology, 26 (11), 2273–2292.
   Web of Science ®Google Scholar
• Steinbach, M. and Hemmerling, R., 2012. Accelerating batch processing of spatial raster analysis using GPU. Computers and Geosciences, 45, 212–220.
   Web of Science ®Google Scholar
• Theobald, D.M., 2005. GIS concepts and ArcGIS methods. 2nd ed. Fort Collins, CO: Conservation Planning Technologies, Inc.
   Google Scholar
• Tzouramanis, T., Vassilakopoulos, M., and Manolopoulos, Y., 1998. Overlapping linear quadtrees: a spatio-temporal access method. Proceedings of the 6th ACM international symposium on advances in geographic information systems (GIS’98), Washington, DC, USA, November 2–7 1998. New York: ACM Press, 1–7.
   Google Scholar
• Wang, C. and Chiang Y.J., 2009. Isosurface extraction and view-dependent filtering from time-varying fields using persistent time-octree (PTOT). IEEE Transaction on Computer Graphics, 5 (6), 1367–1374.
   Google Scholar
• Wang, S.W. and Armstrong, M.P., 2003. A quadtree approach to domain decomposition for spatial interpolation in grid computing environments. Parallel Computing, 29 (10), 1481–1504
   Web of Science ®Google Scholar
• Wang, S.W., Cowles, M.K., and Armstrong, M.P., 2008. Grid computing of spatial statistics, using the TeraGrid for Gi*(d) analysis. Concurrency and Computation: Practice and Experience, 20 (14), 1697–1720.
   Web of Science ®Google Scholar
• Wang, S.W. and Liu, Y., 2009. TeraGrid GIScience gateway: bridging cyberinfrastructure and GIScience. International Journal of Geographical Information Sciences, 23 (5) 631–656.
   Web of Science ®Google Scholar
• Wilhelms, J. and Vangelder, A., 1992. Octrees for faster isosurface generation. ACM Transactions on Graphics, 11 (3), 201–227.
   Web of Science ®Google Scholar
• Xu, X.W., Jager, J., and Kriegel, H.P, 1999. A fast parallel clustering algorithm for large spatial databases. Data Mining and Knowledge Discovery, 3 (3), 263–290.
   Web of Science ®Google Scholar
• Yang, C.W., et al., 2011. Spatial cloud computing: how can the geospatial sciences use and help shape cloud computing. International Journal of Digital Earth, 4 (4), 305–329.
   Web of Science ®Google Scholar
• Yang, C.W., Raskin, R., and Goodchild, M.A., 2010. Geospatial cyberinfrastructure: past, present and future. Computers, Environment and Urban Systems, 34 (4), 264–277.
   Web of Science ®Google Scholar
• You, S. and Zhang, J., 2012. Constructing natural neighbor interpolation based grid DEM using CUDA. Proceedings of the 3rd international conference on computing for geospatial research and applications (COM.Geo ‘12), Reston, VA, USA, July 1–3 2012. New York: ACM Press, Article#28, 6 pages.
   Google Scholar
• Zhang, J., 2010. Towards personal high-performance geospatial computing (HPC-G): perspectives and a case study. Proceedings of the ACM SIGSPATIAL international workshop on high performance and distributed geographic information systems (HPDGIS’10), San Jose, CA, USA, November 3–5 2010. New York: ACM Press, 3–10.
   Google Scholar
• Zhang, J., 2011. Speeding up large-scale geospatial polygon rasterization on GPGPUs. Proceedings of the ACM SIGSPATIAL international workshop on high performance and distributed geographic information systems (HPDGIS’11), Chicago, IL, USA, November 1–4 2011. New York: ACM Press, 10–17.
   Google Scholar
• Zhang, J., 2012. A high-performance web-based information system for publishing large-scale species range maps in support of biodiversity studies. Ecological Informatics, 8, 68–77.
   Web of Science ®Google Scholar
• Zhang, J, Gertz, M., and Gruenwald, 2009a. Efficiently managing large-scale raster species distribution data in PostgreSQL. Proceedings of the 17th ACM international symposium on advances in geographic information systems (GIS’09), Seattle, WA, USA, November 4–6 2009. New York: ACM Press, 316–325.
   Google Scholar
• Zhang, S., et al., 2009b. SJMR: Parallelizing spatial join with MapReduce on clusters. Proceedings of the IEEE international conference on cluster computing workshops (CLUSTER ‘09), Heidelberg, Germany, June 30–July 2 2010. Heidelberg: Springer, 1–8.
   Google Scholar
• Zhang, J. and You, S., 2010a. Supporting web-based visual exploration of large-scale raster geospatial data using binned min-max quadtree. Proceedings of the 22nd international conference on scientific and statistical database management conference (SSDBM’10), Heidelberg, Germany, June 30–July 2 2010. Heidelberg: Springer, 379–396.
   Google Scholar
• Zhang, J. and You, S., 2010b. Dynamic tiled map services: supporting query-based visualization of large-scale raster geospatial data. Proceedings of the 1st international conference on computing for geospatial research & application (COM.Geo’10), Bethesda, MD, USA, June 21–23 2010. New York: ACM Press, Article #19, 8 pages.
   Google Scholar
• Zhang, J. and You, S., 2012. Speeding up large-scale point-in-polygon test based spatial join on GPUs. Proceedings of the 1st ACM SIGSPATIAL international workshop on analytics for big geospatial data (BigSpatial’12), Redondo Beach, CA, USA, November 7–9 2012. New York: ACM Press, 23–32.
   Google Scholar
• Zhang, J., You, S., and Gruenwald, L., 2010. Indexing large-scale raster geospatial data using massively parallel GPGPU computing. Proceedings of the 18th ACM international symposium on Advances in Geographic Information Systems (GIS’10), San Jose, CA, USA, November 3–5 2010. New York: ACM Press, 450–453.
   Google Scholar
• Zhang, J., You, S., and Gruenwald, L., 2011. Parallel quadtree coding of large-scale raster geospatial data on GPGPUs. Proceedings of the 19th ACM international symposium on advances in geographic information systems (GIS’11), Chicago, IL, USA, November 1–4 2011. New York: ACM Press, 457–460.
   Google Scholar
• Zhang, J., You, S., and Gruenwald, L., 2012a. U2STRA: high-performance data management of ubiquitous urban sensing trajectories on GPGPUs. Proceedings of the 2012. ACM workshop on city data management workshop (CDMW’12), Maui, HI, USA, October 29 – November 2 2012. New York: ACM Press, 5–12.
   Google Scholar
• Zhang, J., You, S., and Gruenwald, L., 2012b. High-performance online spatial and temporal aggregations on multi-core CPUs and many-core GPUs. Proceedings of the fifteenth international workshop on Data warehousing and OLAP (DOLAP’12), Maui, HI, USA, October 29 – November 2 2012. New York: ACM Press, 89–96.
   Google Scholar
• Zhou, X., Abel, D.J., and Truffet, D., 1998. Data partitioning for parallel spatial join processing. GeoInformatica, 2 (2), 175–204.
   Google Scholar