A quad-tree-based fast and adaptive Kernel Density Estimation algorithm for heat-map generation

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
• Baddeley, A., Rubak, E., and Turner, R., 2015. Spatial point patterns: methodology and applications with R. New York: Chapman and Hall/CRC.
   Google Scholar
• Bailey, T.C. and Gatrell, A.C., 1995. Interactive spatial data analysis. Harlow: Longman.
   Google Scholar
• Bowman, A.W., 1984. An alternative method of cross-validation for the smoothing of density estimates. Biometrika, 71 (2), 353–360. doi:10.2307/2336252
   Web of Science ®Google Scholar
• Breiman, L., Meisel, W., and Purcell, E., 1977. Variable kernel estimates of multivariate densities. Technometrics : A Journal of Statistics for the Physical, Chemical, and Engineering Sciences, 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 and Geosciences, 21 (7), 877–894. doi:10.1016/0098-3004(95)00020-9
   Web of Science ®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 (1), 39. doi:10.1186/1476-072X-9-39
   PubMedGoogle Scholar
• Chacón, J.E. and Duong, T., 2018. Multivariate kernel smoothing and its applications. New York: Chapman & Hall/CRC.
   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. doi:10.2307/2347366
   Web of Science ®Google Scholar
• Donaldson, C., Gregory, I.N., and Murrieta-Flores, P., 2015. Mapping ‘Wordsworthshire’: A GIS study of literary tourism in Victorian Lakeland. Journal of Victorian Culture, 20 (3), 287–307. doi:10.1080/13555502.2015.1058089
   Web of Science ®Google Scholar
• Donaldson, C., Gregory, I.N., and Taylor, J.E., 2017. Locating the beautiful, picturesque, sublime and majestic: spatially analysing the application of aesthetic terminology in descriptions of the English Lake District. Journal of Historical Geography, 56, 43–60. doi:10.1016/j.jhg.2017.01.006
   Web of Science ®Google Scholar
• Duchowski, A.T., et al., 2012. Aggregate gaze visualization with real-time heatmaps. Symposium on Eye Tracking Research and Applications, 13–20. doi:10.1145/2168556.2168558.
   Google Scholar
• Duong, T., 2007. ks: Kernel Density Estimation and kernel discriminant analysis for multivariate data in R. Journal of Statistical Software, 21 (7), 1–16. doi:10.18637/jss.v021.i07
   Web of Science ®Google Scholar
• Duong, T., 2018. ks (kernel smoothing). [online]. http://www.mvstat.net/tduong/software/
   Google Scholar
• Eck, J.E., et al., 2005. Mapping crime: understanding hot spots. USA: National Institute of Justice (NIJ).
   Google Scholar
• Elgammal, A., Duraiswami, R., and Davis, L.S., 2003. Efficient Kernel Density Estimation using the fast gauss transform with applications to color modeling and tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25 (11), 1499–1504. doi:10.1109/TPAMI.2003.1240123
   Web of Science ®Google Scholar
• Fan, J. and Marron, J.S., 1993. Fast implementations of nonparametric curve estimators. Journal of Computational and Graphical Statistics, 3 (1), 35–56. doi:10.2307/1390794
   Google Scholar
• Gan, E. and Bailis, P., 2017. Scalable kernel density classification via threshold-based pruning. 2017 ACM International Conference on Management of Data, 945–959. doi:10.1145/3035918.3064035.
   Google Scholar
• Goldenshluger, A. and Lepski, O., 2011. Bandwidth selection in kernel density estimation: oracle inequalities and adaptive minimax optimality. The Annals of Statistics, 39 (3), 1608–1632. doi:10.1214/11-aos883
   Web of Science ®Google Scholar
• Goodchild, M.F., 2007. Citizens as sensors: the world of volunteered geography. Geo Journal, 69 (4), 211–221. doi:10.1007/s10708-007-9111-y
   Google Scholar
• Gramacki, A., 2018. Nonparametric kernel density estimation and its computational aspects. Springer International Publishing. doi:10.1007/978-3-319-71688-6
   Google Scholar
• Gramacki, A. and Gramacki, J., 2017a. FFT-based fast computation of multivariate kernel density estimators with unconstrained bandwidth matrices. Journal of Computational and Graphical Statistics, 26 (2), 459–462. doi:10.1080/10618600.2016.1182918
   Web of Science ®Google Scholar
• Gramacki, A. and Gramacki, J., 2017b. FFT-based fast bandwidth selector for multivariate kernel density estimation. Computational Statistics & Data Analysis, 106, 27–45. doi:10.1016/j.csda.2016.09.001
   Web of Science ®Google Scholar
• Gramacki, A., Sawerwain, M., and Gramacki, J., 2016. FPGA-based bandwidth selection for kernel density estimation using high level synthesis approach. Bulletin of the Polish Academy of Sciences Technical Sciences, 64 (4), 821–829. doi:10.1515/bpasts-2016-0091
   Web of Science ®Google Scholar
• Gray, A.G. and Moore, A.W., 2003. Nonparametric density estimation: toward computational tractability. SIAM International Conference on Data Mining, 203–211. doi:10.1137/1.9781611972733.19.
   Google Scholar
• Hall, P., Marron, J.S., and Park, B.U., 1992. Smoothed cross-validation. Probability Theory and Related Fields, 92 (1), 1–20. doi:10.1007/BF01205233
   Web of Science ®Google Scholar
• Hamada, N., et al., 2015. Population synthesis via k-nearest neighbor crossover kernel. 2015 IEEE International Conference on Data Mining, 763–768. doi:10.1109/icdm.2015.65.
   Google Scholar
• Han, D., et al., 2005. Assessing spatio-temporal variability of risk surfaces using residential history data in a case control study of breast cancer. International Journal of Health Geographics, 4 (1), 9. doi:10.1186/1476-072X-4-9
   PubMedGoogle Scholar
• Horová, I., Koláček, J., and Zelinka, J., 2012. Kernel smoothing in Matlab: theory and practice of kernel smoothing. World Scientific Publishing. doi:10.1142/8468
   Google Scholar
• Hu, Y.-C. and Chang, -C.-C., 1999. Variable rate vector quantization scheme based on quadtree segmentation. IEEE Transactions on Consumer Electronics, 45 (2), 310–317. doi:10.1109/30.793414
   Web of Science ®Google Scholar
• Lampe, O.D. and Hauser, H., 2011. Interactive visualization of streaming data with Kernel Density Estimation. 2011 IEEE Pacific Visualization Symposium. IEEE, 171–178. doi:10.1109/PACIFICVIS.2011.5742387.
   Google Scholar
• Li, C., Baciu, G., and Han, Y., 2014. Interactive visualization of high density streaming points with heat-map. 2014 International Conference on Smart Computing, 145–149. doi:10.1109/SMARTCOMP.2014.7043852.
   Google Scholar
• Li, F., et al., 2018. Big enterprise registration data imputation: supporting spatiotemporal analysis of industries in China. Computers Environment and Urban Systems, 70, 9–23. doi:10.1016/j.compenvurbsys.2018.01.010
   Web of Science ®Google Scholar
• Łukasik, S., 2007. Parallel computing of Kernel Density Estimates with MPI. International Conference on Computational Science - ICCS 2007. Berlin, Heidelberg: Springer, 726–733. doi:10.1007/978-3-540-72588-6_120.
   Google Scholar
• Mugdadi, A.R. and Ahmad, I.A., 2014. A bandwidth selection for kernel density estimation of functions of random variables. Computational Statistics & Data Analysis, 47 (1), 49–62. doi:10.1016/j.csda.2003.10.013
   Google Scholar
• Murrieta-Flores, P., 2012. Understanding human movement through spatial technologies. The role of natural areas of transit in the late prehistory of South-western Iberia. Trabajos De Prehistoria, 69 (1), 103–122. doi:10.3989/tp.2012.12082
   Web of Science ®Google Scholar
• Orava, J., 2011. K-Nearest neighbour kernel density estimation, the choice of optimal k. Tatra Mountains Mathematical Publications, 50 (1), 39–50. doi:10.2478/v10127-011-0035-z
   Google Scholar
• Park, B.U. and Marron, J.S., 1990. Comparison of data-driven bandwidth selectors. Publications of the American Statistical Association, 85 (409), 66–72. doi:10.1080/01621459.1990.10475307
   Google Scholar
• Park, K., 2018. A hierarchical binary quadtree index for spatial queries. Wireless Networks. doi:10.1007/s11276-018-1661-z
   Web of Science ®Google Scholar
• Ratcliffe, J., 2010. Crime mapping: spatial and temporal challenges. In: A. Piquero and D. Weisburd, eds. Handbook of quantitative criminology. New York, NY: Springer, 5–24. doi:10.1007/978-0-387-77650-7_2
   Google Scholar
• Rudemo, M., 1982. Empirical choice of histograms and kernel density esimators. Scandinavian Journal of Statistics, 9 (2), 65–78.
   Web of Science ®Google Scholar
• Samet, H., 1984. The quadtree and related hierarchical data structures. ACM Computing Surveys, 16 (2), 187–260. doi:10.1145/356924.356930
   Web of Science ®Google Scholar
• Scott, D.W. and Terrell, G.R., 1987. Biased and unbiased cross-validation in density estimation. Publications of the American Statistical Association, 82 (400), 1131–1146. doi:10.2307/2289391
   Google Scholar
• Sheather, S.J. and Jones, M.C., 1991. A reliable aata-based bandwidth selection method for Kernel Density Estimation. Journal of the Royal Statistical Society, 53 (3), 683–690.
   Google Scholar
• Shekhar, S., et al., 2012. Spatial big-data challenges intersecting mobility and cloud computing. Eleventh ACM International Workshop on Data Engineering for Wireless and Mobile Access, 1–6. doi:10.1145/2258056.2258058.
   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
• Silverman, B., 1986. Density estimation for statistic and data analysis. London, UK: Chapman and Hall.
   Google Scholar
• Smith, J.R. and Chang, S.-F., 1994. Quad-tree segmentation for texture-based image query. ACM 2nd International Conference on Multimedia, 279–286. doi:10.1145/192593.192676.
   Google Scholar
• Spann, M. and Wilson, R., 1985. A quad-tree approach to image segmentation which combines statistical and spatial information. Pattern Recognition, 18 (3–4), 257–269. doi:10.1016/0031-3203(85)90051-2
   Web of Science ®Google Scholar
• Steiner, R.L., 1998. Traditional shopping centers. University of California Transportation Center Working Papers, 1, p. 12.
   Google Scholar
• Tang, L., et al., 2015. A network Kernel Density Estimation for linear features in space–time analysis of big trace data. International Journal of Geographical Information Science, 30 (9), 1–21. doi:10.1080/13658816.2015.1119279
   Web of Science ®Google Scholar
• Tobler, W.R., 1979. Smooth pycnophylactic interpolation for geographical regions. Journal of the American Statistical Association, 74 (367), 519–530. doi:10.2307/2286968
   PubMed Web of Science ®Google Scholar
• Wand, M.P., 1994. Fast computation of multivariate kernel estimators. Journal of Computational and Graphical Statistics, 3 (4), 433–445. doi:10.2307/1390904
   Google Scholar
• Wand, M.P. and Jones, M.C., 1994. Kernel smoothing. Chapman and Hall/CRC. doi:10.1201/b14876
   Google Scholar
• Wilkinson, L. and Friendly, M., 2009. The history of the cluster heat map. The American Statistician, 63 (2), 179–184. doi:10.1198/tas.2009.0033
   Web of Science ®Google Scholar
• Woodroofe, M., 1970. On choosing a delta-sequence. The Annals of Mathematical Statistics, 41 (5), 1665–1671. doi:10.1214/aoms/1177696810
   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, X., et al., 2017. Analyzing space-time variation of urban human stay using Kernel Density Estimation by considering spatial distribution of mobile phone towers. Geomatics and Information Science of Wuhan University, 42 (1), 49–55. doi:10.13203/j.whugis20150646
   Google Scholar
• Yang, X., Zhao, Z., and Lu, S., 2016. Exploring spatial-temporal patterns of urban human mobility hotspots. Sustainability, 8 (7), 674. doi:10.3390/su8070674
   Web of Science ®Google Scholar
• Ye, J., 2011. Cosine similarity measures for intuitionistic fuzzy sets and their applications. Mathematical and Computer Modelling, 53 (1), 91–97. doi:10.1016/j.mcm.2010.07.022
   Google Scholar
• Yu, W., et al., 2015b. Network kernel density estimation for the analysis of facility poi hotspots. Acta Geodaetica Et Cartographica Sinica, 44 (12), 1378–1383and 1400. doi:10.11947/j.AGCS.2015.20140538
   Google Scholar
• Yu, W., Ai, T., and Shao, S., 2015a. The analysis and delimitation of Central Business District using network kernel density estimation. Journal of Transport Geography, 45, 32–47. doi:10.1016/j.jtrangeo.2015.04.008
   Web of Science ®Google Scholar
• Zhang, D. and Lu, G., 2003. Evaluation of similarity measurement for image retrieval. International Conference on Neural Networks and Signal Processing, 928–931. doi:10.1109/ICNNSP.2003.1280752.
   Google Scholar
• Zhang, G., Zhu, A., and Huang, Q., 2017. A GPU-accelerated adaptive kernel density estimation approach for efficient point pattern analysis on spatial big data. International Journal of Geographical Information Science, 31 (10), 2068–2097. doi:10.1080/13658816.2017.1324975
   Web of Science ®Google Scholar