{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:24:32Z","timestamp":1786638272631,"version":"build-2736575974"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:p>\n            Network kernel density visualization, or NKDV, has been extensively used to visualize spatial data points in various domains, including traffic accident hotspot detection, crime hotspot detection, disease outbreak detection, and business and urban planning. Due to a wide range of applications for NKDV, some geographical software, e.g., ArcGIS, can also support this operation. However, computing NKDV is very time-consuming. Although NKDV has been used for more than a decade in different domains, existing algorithms are not scalable to million-sized datasets. To address this issue, we propose three efficient methods in this paper, namely aggregate distance augmentation (ADA), interval augmentation (IA), and hybrid augmentation (HA), which can significantly reduce the time complexity for computing NKDV. In our experiments, ADA, IA and HA can achieve\n            <jats:italic>at least<\/jats:italic>\n            5x to 10x speedup, compared with the state-of-the-art solutions.\n          <\/jats:p>","DOI":"10.14778\/3461535.3461540","type":"journal-article","created":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T22:22:49Z","timestamp":1634941369000},"page":"1503-1516","source":"Crossref","is-referenced-by-count":15,"title":["Fast augmentation algorithms for network kernel density visualization"],"prefix":"10.14778","volume":"14","author":[{"given":"Tsz Nam","family":"Chan","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhe","family":"Li","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leong Hou","family":"U","sequence":"additional","affiliation":[{"name":"University of Macau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"ArcGIS. http:\/\/pro.arcgis.com\/en\/pro-app\/tool-reference\/spatial-analyst\/how-kernel-density-works.htm (last accessed: 2020-10-15).  ArcGIS. http:\/\/pro.arcgis.com\/en\/pro-app\/tool-reference\/spatial-analyst\/how-kernel-density-works.htm (last accessed: 2020-10-15)."},{"key":"e_1_2_1_2_1","unstructured":"IKCEST\n  : Disaster risk reduction. http:\/\/drr.ikcest.org\/knowledge_service\/ncp.html (last accessed: 2020-10-15).  IKCEST: Disaster risk reduction. http:\/\/drr.ikcest.org\/knowledge_service\/ncp.html (last accessed: 2020-10-15)."},{"key":"e_1_2_1_3_1","unstructured":"Johns Creek open data. https:\/\/opendata.atlantaregional.com\/datasets\/JohnsCreekGA::police-calls-for-service-archive-2009-to-2018 (last accessed: 2020-10-15).  Johns Creek open data. https:\/\/opendata.atlantaregional.com\/datasets\/JohnsCreekGA::police-calls-for-service-archive-2009-to-2018 (last accessed: 2020-10-15)."},{"key":"e_1_2_1_4_1","unstructured":"Los Angeles open data. https:\/\/data.lacity.org\/A-Safe-City\/Crime-Data-from-2010-to-2019\/63jg-8b9z (last accessed: 2020-10-15).  Los Angeles open data. https:\/\/data.lacity.org\/A-Safe-City\/Crime-Data-from-2010-to-2019\/63jg-8b9z (last accessed: 2020-10-15)."},{"key":"e_1_2_1_5_1","unstructured":"NYC open data. https:\/\/data.cityofnewyork.us\/Public-Safety\/Motor-Vehicle-Collisions-Crashes\/h9gi-nx95 (last accessed: 2020-10-15).  NYC open data. https:\/\/data.cityofnewyork.us\/Public-Safety\/Motor-Vehicle-Collisions-Crashes\/h9gi-nx95 (last accessed: 2020-10-15)."},{"key":"e_1_2_1_6_1","unstructured":"Openstreetmap. https:\/\/www.openstreetmap.org\/ (last accessed: 2020-10-15).  Openstreetmap. https:\/\/www.openstreetmap.org\/ (last accessed: 2020-10-15)."},{"key":"e_1_2_1_7_1","unstructured":"QGIS. https:\/\/docs.qgis.org\/2.18\/en\/docs\/user_manual\/plugins\/plugins_heatmap.html (last accessed: 2020-10-15).  QGIS. https:\/\/docs.qgis.org\/2.18\/en\/docs\/user_manual\/plugins\/plugins_heatmap.html (last accessed: 2020-10-15)."},{"key":"e_1_2_1_8_1","unstructured":"SANET. http:\/\/sanet.csis.u-tokyo.ac.jp\/ (last accessed: 2020-10-15).  SANET. http:\/\/sanet.csis.u-tokyo.ac.jp\/ (last accessed: 2020-10-15)."},{"key":"e_1_2_1_9_1","unstructured":"Seattle open data. https:\/\/data.seattle.gov\/Public-Safety\/SPD-Crime-Data-2008-Present\/tazs-3rd5 (last accessed: 2020-10-15).  Seattle open data. https:\/\/data.seattle.gov\/Public-Safety\/SPD-Crime-Data-2008-Present\/tazs-3rd5 (last accessed: 2020-10-15)."},{"issue":"265","key":"e_1_2_1_10_1","first-page":"273","article-title":"Identification of hazardous road locations of traffic accidents by means of kernel density estimation and cluster significance evaluation","volume":"55","author":"B\u00edl M.","year":"2013","unstructured":"M. B\u00edl , R. Andr\u00e1\u0161ik , and Z. Jano\u0161ka . Identification of hazardous road locations of traffic accidents by means of kernel density estimation and cluster significance evaluation . Accident Analysis & Prevention , 55 : 265 -- 273 , 2013 . M. B\u00edl, R. Andr\u00e1\u0161ik, and Z. Jano\u0161ka. Identification of hazardous road locations of traffic accidents by means of kernel density estimation and cluster significance evaluation. Accident Analysis & Prevention, 55:265 -- 273, 2013.","journal-title":"Accident Analysis & Prevention"},{"issue":"126","key":"e_1_2_1_11_1","first-page":"139","article-title":"New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers","volume":"65","author":"Boeing G.","year":"2017","unstructured":"G. Boeing . Osmnx : New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers , Environment and Urban Systems , 65 : 126 -- 139 , 2017 . G. Boeing. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 65:126 -- 139, 2017.","journal-title":"Environment and Urban Systems"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.sj.8350066"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380561"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476312"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3018376"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00055"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2015.2436897"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939860"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2018.1541177"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498274"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064035"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3278386"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972733.19"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183738"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3193549"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2013.119"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2652454"},{"issue":"62","key":"e_1_2_1_30_1","first-page":"74","article-title":"A new integrated gis-based analysis to detect hotspots: A case study of the city of sherbrooke","volume":"130","author":"Harirforoush H.","year":"2019","unstructured":"H. Harirforoush and L. Bellalite . A new integrated gis-based analysis to detect hotspots: A case study of the city of sherbrooke . Accident Analysis & Prevention , 130 : 62 -- 74 , 2019 . Road Safety Data Considerations. H. Harirforoush and L. Bellalite. A new integrated gis-based analysis to detect hotspots: A case study of the city of sherbrooke. Accident Analysis & Prevention, 130:62 -- 74, 2019. Road Safety Data Considerations.","journal-title":"Accident Analysis & Prevention"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1108\/PIJPSM-04-2013-0039"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998204"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816720"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12061-017-9230-x"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00107"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3160587"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-016-0265-y"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2010.07.003"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052717"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.65"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2674978"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2017.1360782"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447851"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijerph13080833"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368965"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810802475491"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/2935448"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.135"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315520"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498287"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/LDAV.2015.7348077"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627933"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175477"},{"key":"e_1_2_1_56_1","first-page":"1","volume-title":"SOCG","author":"Phillips J. M.","year":"2018","unstructured":"J. M. Phillips and W. M. Tai . Near-optimal coresets of kernel density estimates . In SOCG , pages 66: 1 -- 66 :13, 2018 . J. M. Phillips and W. M. Tai. Near-optimal coresets of kernel density estimates. In SOCG, pages 66:1--66:13, 2018."},{"issue":"1","key":"e_1_2_1_57_1","first-page":"1","article-title":"Efficient code for second order analysis of events on a linear network","volume":"90","author":"Rakshit S.","year":"2019","unstructured":"S. Rakshit , A. Baddeley , and G. Nair . Efficient code for second order analysis of events on a linear network . Journal of Statistical Software, Articles , 90 ( 1 ): 1 -- 37 , 2019 . S. Rakshit, A. Baddeley, and G. Nair. Efficient code for second order analysis of events on a linear network. Journal of Statistical Software, Articles, 90(1):1--37, 2019.","journal-title":"Journal of Statistical Software, Articles"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1198\/jcgs.2010.09046"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139981"},{"issue":"569","key":"e_1_2_1_60_1","first-page":"594","article-title":"Predictive crime mapping: Arbitrary grids or street networks?","volume":"33","author":"Rosser G.","year":"2017","unstructured":"G. Rosser , T. O. Davies , K. Bowers , S. D. Johnson , and T. Cheng . Predictive crime mapping: Arbitrary grids or street networks? Journal of Quantitative Criminology , 33 : 569 -- 594 , 2017 . G. Rosser, T. O. Davies, K. Bowers, S. D. Johnson, and T. Cheng. Predictive crime mapping: Arbitrary grids or street networks? Journal of Quantitative Criminology, 33:569 -- 594, 2017.","journal-title":"Journal of Quantitative Criminology"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2015.1080829"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213859"},{"key":"e_1_2_1_63_1","volume-title":"Theory, Practice, and Visualization","author":"Scott D.","year":"1992","unstructured":"D. Scott . Multivariate Density Estimation : Theory, Practice, and Visualization . A Wiley-interscience publication. Wiley , 1992 . D. Scott. Multivariate Density Estimation: Theory, Practice, and Visualization. A Wiley-interscience publication. Wiley, 1992."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/993490"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64367-0_15"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359100"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/2721513"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213872"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1201\/b14876"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.116"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1111\/risa.12785"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2008.05.001"},{"issue":"64","key":"e_1_2_1_73_1","first-page":"71","article-title":"Detecting traffic accident clusters with network kernel density estimation and local spatial statistics: an integrated approach","volume":"31","author":"Xie Z.","year":"2013","unstructured":"Z. Xie and J. Yan . Detecting traffic accident clusters with network kernel density estimation and local spatial statistics: an integrated approach . Journal of Transport Geography , 31 : 64 -- 71 , 2013 . Z. Xie and J. Yan. Detecting traffic accident clusters with network kernel density estimation and local spatial statistics: an integrated approach. Journal of Transport Geography, 31:64 -- 71, 2013.","journal-title":"Journal of Transport Geography"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/2976040.2976236"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007619"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.87"},{"issue":"80","key":"e_1_2_1_77_1","first-page":"88","article-title":"Comparative analysis of the spatial analysis methods for hotspot identification","volume":"66","author":"Yu H.","year":"2014","unstructured":"H. Yu , P. Liu , J. Chen , and H. Wang . Comparative analysis of the spatial analysis methods for hotspot identification . Accident Analysis and Prevention , 66 : 80 -- 88 , 2014 . H. Yu, P. Liu, J. Chen, and H. Wang. Comparative analysis of the spatial analysis methods for hotspot identification. Accident Analysis and Prevention, 66:80 -- 88, 2014.","journal-title":"Accident Analysis and Prevention"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2015.04.008"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1324975"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0017381"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743025"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465319"},{"key":"e_1_2_1_83_1","volume-title":"IEEE Symposium on Visualization in Data Science (VDS '17)","author":"Zheng Y.","unstructured":"Y. Zheng , Y. Ou , A. Lex , and J. M. Phillips . Visualization of big spatial data using coresets for kernel density estimates . In IEEE Symposium on Visualization in Data Science (VDS '17) , to appear. IEEE, 2017. Y. Zheng, Y. Ou, A. Lex, and J. M. Phillips. Visualization of big spatial data using coresets for kernel density estimates. In IEEE Symposium on Visualization in Data Science (VDS '17), to appear. IEEE, 2017."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783357"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3461535.3461540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:46:25Z","timestamp":1672220785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3461535.3461540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5]]},"references-count":84,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.14778\/3461535.3461540"],"URL":"https:\/\/doi.org\/10.14778\/3461535.3461540","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,5]]}}}