A GPU-accelerated adaptive kernel density estimation approach for efficient point pattern analysis on spatial big data

References

• Abramson, I.S., 1982. On bandwidth variation in kernel estimates-a square root law. The Annals of Statistics, 10 (4), 1217–1223. doi:10.1214/aos/1176345986.
   Web of Science ®Google Scholar
• Aji, A., et al., 2013. Hadoop GIS: a high performance spatial data warehousing system over MapReduce. Proceedings of the VLDB Endowment, 6 (11), 1009–1020. doi:10.14778/2536222.2536227.
   Google Scholar
• Andrzejewski, W., Gramacki, A., and Gramacki, J., 2013. Graphics processing units in acceleration of bandwidth selection for kernel density estimation. International Journal of Applied Mathematics and Computer Science, 23 (4), 869–885. doi:10.2478/amcs-2013-0065.
   Web of Science ®Google Scholar
• Baddeley, A., Rubak, E., and Turner, R., 2015. Spatial point patterns: methodology and applications with R. London: Chapman and Hall/CRC Press. 86, 19-941 doi:10.2307/1403548
   Google Scholar
• Bentley, J.L. and Friedman, J.H., 1979. Data structures for range searching. ACM Computer Surveys, 11 (4), 397–409. doi:10.1145/356789.356797.
   Web of Science ®Google Scholar
• Breiman, L., Meisel, W., and Purcell, E., 1977. Variable kernel estimates of multivariate densities. Technometrics, 19 (2), 135–144. doi:10.1080/00401706.1977.10489521.
   Web of Science ®Google Scholar
• Brunsdon, C., 1995. Estimating probability surfaces for geographical point data: an adaptive kernel algorithm. Computers & Geosciences, 21 (7), 877–894. doi:10.1016/0098-3004(95)00020-9.
   Web of Science ®Google Scholar
• Burt, J.E., Barber, G.M., and Rigby, D.L., 2009. Elementary statistics for geographers. New York: Guilford Press.
   Google Scholar
• Carlos, H.A., et al., 2010. Density estimation and adaptive bandwidths: a primer for public health practitioners. International Journal of Health Geographics, 9, 39. doi:10.1186/1476-072X-9-39.
   PubMed Web of Science ®Google Scholar
• Diggle, P., 1985. A Kernel method for smoothing point process data. Journal of the Royal Statistical Society. Series C (Applied Statistics), 34 (2), 138–147.
   Web of Science ®Google Scholar
• eBrid, 2016. eBird reference dataset. Available from: http://www.ccs.neu.edu/home/mirek/papers/ebird-ref-data.pdf
   Google Scholar
• Epanechnikov, V., 1969. Non-parametric estimation of a multivariate probability density. Theory of Probability & Its Applications, 14 (1), 153–158. doi:10.1137/1114019.
   Web of Science ®Google Scholar
• Evans, M.R., 2013. Enabling spatial big data via CyberGIS: challenges and opportunities. In: S. Wang, et al., eds. CyberGIS: fostering a new wave of geospatial innovation and discovery. New York: Springer Book.
   Google Scholar
• Fotheringham, A.S., Brunsdon, C., and Charlton, M., 2000. Quantitative geography: perspectives on spatial data analysis. Thousand Oaks, CA: Sage.
   Google Scholar
• Gatrell, A.C., et al., 1996. Spatial point pattern analysis and its application in geographical epidemiology. Transactions of the Institute of British Geographers, 21 (1), 256–274. doi:10.2307/622936.
   Web of Science ®Google Scholar
• Goodchild, M.F., 2007. Citizens as sensors: the world of volunteered geography. Geojournal, 69 (4), 211–221. doi:10.1007/s10708-007-9111-y.
   Google Scholar
• Guan, Q., et al., 2016. A hybrid parallel cellular automata model for urban growth simulation over GPU/CPU heterogeneous architectures. International Journal of Geographical Information Science, 30 (3), 494–514. doi:10.1080/13658816.2015.1039538.
   Web of Science ®Google Scholar
• Guan, Q. and Clarke, K.C., 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
• Hooke, R. and Jeeves, T.A., 1961. “Direct Search” solution of numerical and statistical problems. J. Acm, 8 (2), 212–229. doi:10.1145/321062.321069.
   Google Scholar
• Huang, Q. and Wong, D.W.S., 2015. Modeling and visualizing regular human mobility patterns with uncertainty : an example using twitter data modeling and visualizing regular human mobility patterns with uncertainty : an example using twitter data. Annals of the Association of American Geographers, 105 (6), 1179–1197. doi:10.1080/00045608.2015.1081120.
   Web of Science ®Google Scholar
• Jones, M., 1990. Variable kernel density estimates and variable kernel density estimates. Australian Journal of Statistics, 32 (March), 361–371. doi:10.1111/j.1467-842X.1990.tb01031.x.
   Google Scholar
• Jones, M.C., Marron, J.S., and Sheather, S.J., 1996. Progress in data-based bandwidth selection for kernel density estimation. Computational Statistics, 11 (3), 337–381.
   Web of Science ®Google Scholar
• Kakde, H.M., 2005. Range searching using Kd tree [online]. Florida State University. Available from: http://ti.twiki.di.uniroma1.it/pub/Estrinfo/Materiale/kdtree.pdf [Accessed 4 October 2016].
   Google Scholar
• Kirk, D.B. and Hwu, W.W., 2012. Programming massively parallel processors: a hands-on approach. 2nd ed.Amsterdam: Elsevier/Morgan Kaufmann.
   Google Scholar
• Law, R., et al., 2009. Ecological information from spatial patterns of plants: insights from point process theory. Journal of Ecology, 97 (4), 616–628. doi:10.1111/j.1365-2745.2009.01510.x.
   Web of Science ®Google Scholar
• Longley, P.A. and Adnan, M., 2016. Geo-temporal Twitter demographics. International Journal of Geographical Information Science, 30 (2), 369–389. doi:10.1080/13658816.2015.1089441.
   Web of Science ®Google Scholar
• Luebke, D., 2008. CUDA: scalable parallel programming for high-performance scientific computing. 2008 5th IEEE international symposium on biomedical imaging: from nano to macro, 14–17 May, Paris, 836–838.
   Google Scholar
• Michailidis, P.D. and Margaritis, K.G., 2013. Accelerating kernel density estimation on the GPU using the CUDA framework. Applied Mathematical Sciences, 7 (30), 1447–1476. doi:10.12988/ams.2013.13133.
   Google Scholar
• Miecznikowski, J.C., Wang, D., and Hutson, A., 2010. Bootstrap MISE estimators to obtain bandwidth for kernel density estimation. Communications in Statistics - Simulation and Computation, 39 (1986), 1455–1469. doi:10.1080/03610918.2010.500108.
   Web of Science ®Google Scholar
• Nickolls, J., et al., 2008. Scalable parallel programming with CUDA. Queue, 6 (2), 40–53. doi:10.1145/1365490.1365500.
   Google Scholar
• NVIDIA, 2016. CUDA C programming guide [online]. NVIDIA Corporation. Available from: http://docs.nvidia.com/cuda/cuda-c-programming-guide [Accessed 1 August 2015].
   Google Scholar
• Osterman, A., Benedičič, L., and Ritoša, P., 2014. An IO-efficient parallel implementation of an R2 viewshed algorithm for large terrain maps on a CUDA GPU. International Journal of Geographical Information Science, 28 (11), 2304–2327. doi:10.1080/13658816.2014.918319.
   Web of Science ®Google Scholar
• Pijanowski, B.C., et al., 2014. A big data urban growth simulation at a national scale: configuring the GIS and neural network based Land Transformation Model to run in a High Performance Computing (HPC) environment. Environmental Modelling & Software, 51, 250–268. doi:10.1016/j.envsoft.2013.09.015.
   Web of Science ®Google Scholar
• Qin, C.-Z., et al., 2014. A strategy for raster-based geocomputation under different parallel computing platforms. International Journal of Geographical Information Science, 28 (11), 2127–2144. doi:10.1080/13658816.2014.911300.
   Web of Science ®Google Scholar
• Sain, S.R., et al., 1996. On locally adaptive density estimation. Journal of the American Statistical Association, 91 (436), 1525–1534. doi:10.1080/01621459.1996.10476720.
   Web of Science ®Google Scholar
• Schadt, E.E. et al., 2010, Computational solutions to large-scale data management and analysis. Nature Reviews. Genetics, 11 (9), 647–657.
   PubMed Web of Science ®Google Scholar
• Shekhar, S. et al., 2012. 8. Spatial big-data challenges intersecting mobility and cloud computing. In Proceedings of the eleventh ACM international workshop on data engineering for wireless and mobile access, SIGMOD/PODS ’12 international conference on management of data Scottsdale, AZ, USA — May 20–24, 2012. New York: ACM, 1–6.
   Google Scholar
• Shi, X., 2010. Selection of bandwidth type and adjustment side in kernel density estimation over inhomogeneous backgrounds. International Journal of Geographical Information Science, 24 (5), 643–660. doi:10.1080/13658810902950625.
   Web of Science ®Google Scholar
• Shi, X. et al., 2014, Geocomputation over the emerging heterogeneous computing infrastructure. Transactions In Gis, 18 (S1), 3–24.
   Web of Science ®Google Scholar
• Silverman, B.W., 1986. Density estimation for statistics and data analysis. London, UK: Chapman and Hall.
   Google Scholar
• Sullivan, B.L., et al., 2009. eBird: a citizen-based bird observation network in the biological sciences. Biological Conservation, 142 (10), 2282–2292. doi:10.1016/j.biocon.2009.05.006.
   Web of Science ®Google Scholar
• Tang, W., 2013. Parallel construction of large circular cartograms using graphics processing units. International Journal of Geographical Information Science, 27 (11), 2182–2206. doi:10.1080/13658816.2013.778413.
   Web of Science ®Google Scholar
• Tang, W., Feng, W., and Jia, M., 2015. Massively parallel spatial point pattern analysis: Ripley’s K function accelerated using graphics processing units. International Journal of Geographical Information Science, 29 (3), 412–439. doi:10.1080/13658816.2014.976569.
   Web of Science ®Google Scholar
• Torrellas, J., Lam, M.S., and Hennessy, J.L., 1994. False sharing and spatial locality in multiprocessor caches. IEEE Transactions on Computers, 43 (6), 651–663. doi:10.1109/12.286299.
   Web of Science ®Google Scholar
• Wang, S., 2010. A CyberGIS framework for the synthesis of cyberinfrastructure, GIS, and spatial analysis. Annals of the Association of American Geographers, 100 (February 2015), 535–557. doi:10.1080/00045601003791243.
   Web of Science ®Google Scholar
• Wang, S., 2013. CyberGIS: blueprint for integrated and scalable geospatial software ecosystems. International Journal of Geographical Information Science, 27 (11), 2119–2121. doi:10.1080/13658816.2013.841318.
   Web of Science ®Google Scholar
• Wood, C., et al., 2011. eBird: engaging birders in science and conservation. Plos Biology, 9 (12), e1001220. doi:10.1371/journal.pbio.1001220.
   PubMed Web of Science ®Google Scholar
• Worton, B.J., 1989. Kernel methods for estimating the utilization distribution in home-range studies. Ecology, 70 (1), 164. doi:10.2307/1938423.
   Web of Science ®Google Scholar
• Wright, D.J. and Wang, S., 2011. The emergence of spatial cyberinfrastructure. Proceedings of the National Academy of Sciences of the United States of America, 108 (14), 5488–5491. doi:10.1073/pnas.1103051108.
   PubMed Web of Science ®Google Scholar
• Wu, H., Zhang, T., and Gong, J., 2014. GeoComputation for geospatial big data. Transactions in GIS, 18 (S1), 1–2. doi:10.1111/tgis.2014.18.issue-s1.
   Google Scholar
• Xie, Z. and Yan, J., 2008. Kernel density estimation of traffic accidents in a network space. Computers, Environment and Urban Systems, 32 (5), 396–406. doi:10.1016/j.compenvurbsys.2008.05.001.
   Web of Science ®Google Scholar
• Yang, C., et al., 2010. Geospatial cyberinfrastructure: past, present and future. Computers, Environment and Urban Systems, 34 (4), 264–277. doi:10.1016/j.compenvurbsys.2010.04.001.
   Web of Science ®Google Scholar
• Yang, C., et al., 2011. Spatial cloud computing: how can the geospatial sciences use and help shape cloud computing? International Journal of Digital Earth, 4 (February 2015), 305–329. doi:10.1080/17538947.2011.587547.
   Web of Science ®Google Scholar
• Yang, C., et al., 2017a. Big data and cloud computing: innovation opportunities and challenges. International Journal Of Digital Earth, 10 (1), 13–53.
   Web of Science ®Google Scholar
• Yang, C.P., 2017b. Geospatial cloud computing and big data. Computers, Environment And Urban Systems, 61, 119. doi:10.1016/j.compenvurbsys.2016.05.001
   Web of Science ®Google Scholar
• Zhang, G., et al., 2016. Enabling point pattern analysis on spatial big data using cloud computing: optimizing and accelerating Ripley’s K function. International Journal of Geographical Information Science, 30 (11), 2230–2252. doi:10.1080/13658816.2016.1170836.
   Web of Science ®Google Scholar
• Zhang, J. and You, S., 2013. High-performance quadtree constructions on large-scale geospatial rasters using GPGPU parallel primitives. International Journal of Geographical Information Science, 27 (11), 2207–2226. doi:10.1080/13658816.2013.828840.
   Web of Science ®Google Scholar
• Zhao, Y., Padmanabhan, A., and Wang, S., 2013. A parallel computing approach to viewshed analysis of large terrain data using graphics processing units. International Journal of Geographical Information Science, 27 (2), 363–384. doi:10.1080/13658816.2012.692372.
   Web of Science ®Google Scholar
• Zhou, C., et al., 2016. A parallel scheme for large-scale polygon rasterization on CUDA-enabled GPUs. Transactions in GIS, doi:10.1111/tgis.12213.
   PubMed Web of Science ®Google Scholar
• Zhu, A.X., et al., 2015. A citizen data-based approach to predictive mapping of spatial variation of natural phenomena. International Journal Of Geographical Information Science, 29 (10), 1864–1886. doi: 10.1080/13658816.2015.1058387
   Web of Science ®Google Scholar