{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,30]],"date-time":"2026-10-30T21:09:33Z","timestamp":1793394573794,"version":"4.5.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:p>Spatial-temporal kernel density visualization (STKDV) has been extensively used in a wide range of applications, e.g., disease outbreak analysis, traffic accident hotspot detection, and crime hotspot detection. While STKDV can provide accurate and comprehensive data visualization, computing STKDV is time-consuming, which is not scalable to large-scale datasets. To address this issue, we develop a new sliding-window-based solution (SWS), which theoretically reduces the time complexity for generating STKDV, without increasing the space complexity. Moreover, we incorporate SWS with the progressive visualization framework, which can continuously output partial visualization results to users (from coarse to fine), until users satisfy the visualization. Our experimental studies on five large-scale datasets show that SWS achieves 1.71x to 24x speedup compared with the state-of-the-art methods.<\/jats:p>","DOI":"10.14778\/3503585.3503591","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T18:18:07Z","timestamp":1649960287000},"page":"814-827","source":"Crossref","is-referenced-by-count":17,"title":["SWS"],"prefix":"10.14778","volume":"15","author":[{"given":"Tsz Nam","family":"Chan","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pak Lon","family":"Ip","sequence":"additional","affiliation":[{"name":"University of Macau SKL of Internet of Things for Smart City"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leong Hou","family":"U","sequence":"additional","affiliation":[{"name":"University of Macau SKL of Internet of Things for Smart City"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Byron","family":"Choi","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,4,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. ArcGIS. http:\/\/pro.arcgis.com\/en\/pro-app\/tool-reference\/spatial-analyst\/how-kernel-density-works.htm. [n. d.]. ArcGIS. http:\/\/pro.arcgis.com\/en\/pro-app\/tool-reference\/spatial-analyst\/how-kernel-density-works.htm."},{"key":"e_1_2_1_2_1","unstructured":"[n. d.]. CrimeStat: Spatial Statistics Program for the Analysis of Crime Incident Locations. https:\/\/nij.ojp.gov\/topics\/articles\/crimestat-spatial-statistics-program-analysis-crime-incident-locations. [n. d.]. CrimeStat: Spatial Statistics Program for the Analysis of Crime Incident Locations. https:\/\/nij.ojp.gov\/topics\/articles\/crimestat-spatial-statistics-program-analysis-crime-incident-locations."},{"key":"e_1_2_1_3_1","unstructured":"[n. d.]. Hong Kong GeoData Store. https:\/\/geodata.gov.hk\/gs\/view-dataset?uuid=d4ccd9be-3bc0-449b-bd27-9eb9b615f2db&sidx=0. [n. d.]. Hong Kong GeoData Store. https:\/\/geodata.gov.hk\/gs\/view-dataset?uuid=d4ccd9be-3bc0-449b-bd27-9eb9b615f2db&sidx=0."},{"key":"e_1_2_1_4_1","unstructured":"[n. d.]. IKCEST: Disaster Risk Reduction. http:\/\/drr.ikcest.org\/knowledge_service\/ncp.html. [n. d.]. IKCEST: Disaster Risk Reduction. http:\/\/drr.ikcest.org\/knowledge_service\/ncp.html."},{"key":"e_1_2_1_5_1","unstructured":"[n. d.]. Los Angeles Open Data. https:\/\/data.lacity.org\/A-Safe-City\/Crime-Data-from-2010-to-2019\/63jg-8b9z. [n. d.]. Los Angeles Open Data. https:\/\/data.lacity.org\/A-Safe-City\/Crime-Data-from-2010-to-2019\/63jg-8b9z."},{"key":"e_1_2_1_6_1","unstructured":"[n. d.]. NYC Open Data. https:\/\/data.cityofnewyork.us\/Public-Safety\/Motor-Vehicle-Collisions-Crashes\/h9gi-nx95. [n. d.]. NYC Open Data. https:\/\/data.cityofnewyork.us\/Public-Safety\/Motor-Vehicle-Collisions-Crashes\/h9gi-nx95."},{"key":"e_1_2_1_7_1","unstructured":"[n.d.]. NYC Yellow Taxi Trip Data. https:\/\/data.cityofnewyork.us\/Transportation\/2014-Yellow-Taxi-Trip-Data\/gkne-dk5s. [n.d.]. NYC Yellow Taxi Trip Data. https:\/\/data.cityofnewyork.us\/Transportation\/2014-Yellow-Taxi-Trip-Data\/gkne-dk5s."},{"key":"e_1_2_1_8_1","unstructured":"[n. d.]. Ontario Open Data. https:\/\/data.ontario.ca\/dataset\/confirmed-positive-cases-of-covid-19-in-ontario. [n. d.]. Ontario Open Data. https:\/\/data.ontario.ca\/dataset\/confirmed-positive-cases-of-covid-19-in-ontario."},{"key":"e_1_2_1_9_1","unstructured":"[n. d.]. QGIS. https:\/\/docs.qgis.org\/2.18\/en\/docs\/user_manual\/plugins\/plugins_heatmap.html. [n. d.]. QGIS. https:\/\/docs.qgis.org\/2.18\/en\/docs\/user_manual\/plugins\/plugins_heatmap.html."},{"key":"e_1_2_1_10_1","unstructured":"[n. d.]. Seattle Open Data. https:\/\/data.seattle.gov\/Public-Safety\/SPD-Crime-Data-2008-Present\/tazs-3rd5. [n. d.]. Seattle Open Data. https:\/\/data.seattle.gov\/Public-Safety\/SPD-Crime-Data-2008-Present\/tazs-3rd5."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2005.07.009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.sj.8350066"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380561"},{"key":"e_1_2_1_15_1","unstructured":"Tsz Nam Chan Pak Lon Ip Leong Hou U Byron Choi and Jianliang Xu. [n. d.]. SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization (Technical Report). https:\/\/github.com\/STKDV\/STKDV\/blob\/main\/SWS_STKDV_TR.pdf. Tsz Nam Chan Pak Lon Ip Leong Hou U Byron Choi and Jianliang Xu. [n. d.]. SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization (Technical Report). https:\/\/github.com\/STKDV\/STKDV\/blob\/main\/SWS_STKDV_TR.pdf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494135"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476312"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461540"},{"key":"e_1_2_1_19_1","volume-title":"Man Lung Yiu, and Shivansh Mittal","author":"Chan Tsz Nam","year":"2020","unstructured":"Tsz Nam Chan , Leong Hou U, Reynold Cheng , Man Lung Yiu, and Shivansh Mittal . 2020 . Efficient Algorithms for Kernel Aggregation Queries. IEEE Transactions on Knowledge and Data Engineering ( 2020), 1--1. Tsz Nam Chan, Leong Hou U, Reynold Cheng, Man Lung Yiu, and Shivansh Mittal. 2020. Efficient Algorithms for Kernel Aggregation Queries. IEEE Transactions on Knowledge and Data Engineering (2020), 1--1."},{"key":"e_1_2_1_20_1","volume-title":"SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization. In SIGMOD (To appear).","author":"Chan Tsz Nam","year":"2022","unstructured":"Tsz Nam Chan , Leong Hou U, Byron Choi , and Jianliang Xu . 2022 . SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization. In SIGMOD (To appear). Tsz Nam Chan, Leong Hou U, Byron Choi, and Jianliang Xu. 2022. SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization. In SIGMOD (To appear)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00055"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2015.2436897"},{"key":"e_1_2_1_23_1","volume-title":"Overmars","author":"de Berg Mark","year":"2008","unstructured":"Mark de Berg , Otfried Cheong , Marc J. van Kreveld , and Mark H . Overmars . 2008 . Computational geometry: algorithms and applications, 3 rd Edition. Springer . https:\/\/www.worldcat.org\/oclc\/227584184 Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer. https:\/\/www.worldcat.org\/oclc\/227584184","edition":"3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2013.871285"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Edward Gan and Peter Bailis. 2017. Scalable Kernel Density Classification via Threshold-Based Pruning. In ACM SIGMOD. 945--959. Edward Gan and Peter Bailis. 2017. Scalable Kernel Density Classification via Threshold-Based Pruning. In ACM SIGMOD. 945--959.","DOI":"10.1145\/3035918.3064035"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.250585"},{"key":"e_1_2_1_27_1","volume-title":"Nonparametric Kernel Density Estimation and Its Computational Aspects","author":"Gramacki A.","unstructured":"A. Gramacki . 2017. Nonparametric Kernel Density Estimation and Its Computational Aspects . Springer International Publishing . https:\/\/books.google.com.hk\/books?id=PCpEDwAAQBAJ A. Gramacki. 2017. Nonparametric Kernel Density Estimation and Its Computational Aspects. Springer International Publishing. https:\/\/books.google.com.hk\/books?id=PCpEDwAAQBAJ"},{"key":"e_1_2_1_28_1","volume-title":"Moore","author":"Gray Alexander G.","year":"2003","unstructured":"Alexander G. Gray and Andrew W . Moore . 2003 . Nonparametric Density Estimation: Toward Computational Tractability. In SDM. 203--211. Alexander G. Gray and Andrew W. Moore. 2003. Nonparametric Density Estimation: Toward Computational Tractability. In SDM. 203--211."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.3390\/s80603601"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sste.2016.05.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apgeog.2018.08.001"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0196845"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.healthplace.2010.06.016"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACIFICVIS.2011.5742387"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1287371"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066193"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aap.2020.105509"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820817"},{"key":"e_1_2_1_39_1","unstructured":"Andrew W. Moore. 2000. The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data. In UAI. 397--405. Andrew W. Moore. 2000. The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data. In UAI. 397--405."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9671.2010.01194.x"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498287"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/LDAV.2015.7348077"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.116"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.173"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.66"},{"key":"e_1_2_1_47_1","volume-title":"QGIS Geographic Information System","author":"Development Team QGIS","unstructured":"QGIS Development Team . 2009. QGIS Geographic Information System . Open Source Geospatial Foundation . http:\/\/qgis.osgeo.org QGIS Development Team. 2009. QGIS Geographic Information System. Open Source Geospatial Foundation. http:\/\/qgis.osgeo.org"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00588-3"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1198\/jcgs.2010.09046"},{"key":"e_1_2_1_50_1","unstructured":"H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2017.57"},{"key":"e_1_2_1_52_1","volume-title":"Multivariate Density Estimation: Theory, Practice, and Visualization","author":"Scott D.W.","unstructured":"D.W. Scott . 1992. Multivariate Density Estimation: Theory, Practice, and Visualization . Wiley . https:\/\/books.google.com.hk\/books?id=7crCUS_F2ocC D.W. Scott. 1992. Multivariate Density Estimation: Theory, Practice, and Visualization. Wiley. https:\/\/books.google.com.hk\/books?id=7crCUS_F2ocC"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3029770"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339499"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752940"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.48"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1201\/b17217"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2868960"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904490"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijerph15030405"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1111\/risa.12785"},{"key":"e_1_2_1_62_1","volume-title":"Davis","author":"Yang Changjiang","year":"2004","unstructured":"Changjiang Yang , Ramani Duraiswami , and Larry S . Davis . 2004 . Efficient Kernel Machines Using the Improved Fast Gauss Transform. In NIPS. 1561--1568. http:\/\/papers.nips.cc\/paper\/2550-efficient-kernel-machines-using-the-improved-fast-gauss-transform Changjiang Yang, Ramani Duraiswami, and Larry S. Davis. 2004. Efficient Kernel Machines Using the Improved Fast Gauss Transform. In NIPS. 1561--1568. http:\/\/papers.nips.cc\/paper\/2550-efficient-kernel-machines-using-the-improved-fast-gauss-transform"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-29151-2"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1324975"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0017381"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3229329.3229331"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Yan Zheng Jeffrey Jestes Jeff M. Phillips and Feifei Li. 2013. Quality and efficiency for kernel density estimates in large data. In SIGMOD. 433--444. Yan Zheng Jeffrey Jestes Jeff M. Phillips and Feifei Li. 2013. Quality and efficiency for kernel density estimates in large data. In SIGMOD. 433--444.","DOI":"10.1145\/2463676.2465319"},{"key":"e_1_2_1_68_1","volume-title":"IEEE Symposium on Visualization in Data Science (VDS '17)","author":"Zheng Yan","unstructured":"Yan Zheng , Yi Ou , Alexander Lex , and Jeff M. Phillips . 2017. Visualization of Big Spatial Data using Coresets for Kernel Density Estimates . In IEEE Symposium on Visualization in Data Science (VDS '17) , to appear. IEEE. Yan Zheng, Yi Ou, Alexander Lex, and Jeff M. Phillips. 2017. Visualization of Big Spatial Data using Coresets for Kernel Density Estimates. In IEEE Symposium on Visualization in Data Science (VDS '17), to appear. IEEE."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783357"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.10.071"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2788570"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2662236"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3503585.3503591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T04:02:34Z","timestamp":1726977754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3503585.3503591"}},"subtitle":["a complexity-optimized solution for spatial-temporal kernel density visualization"],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.14778\/3503585.3503591"],"URL":"https:\/\/doi.org\/10.14778\/3503585.3503591","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,12]]}}}