{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:36:22Z","timestamp":1714782982210},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>Network Kernel Density Visualization (NKDV) has often been used in a wide range of applications, e.g., criminology, transportation science, and urban planning. However, NKDV is computationally expensive, which cannot be scalable to large-scale datasets and high resolution sizes. Although a recent work, called aggregate distance augmentation (ADA), has been developed for improving the efficiency to generate NKDV, this method is still slow and does not take the resolution size into account for optimizing the efficiency. In this paper, we develop a new solution, called LION, which can reduce the worst-case time complexity for generating high-resolution NKDV, without increasing the space complexity. Experiment results on four large-scale location datasets verify that LION can achieve 2.86x to 35.36x speedup compared with the state-of-the-art ADA method.<\/jats:p>","DOI":"10.14778\/3648160.3648168","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T21:52:53Z","timestamp":1714773173000},"page":"1255-1268","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["LION: Fast and High-Resolution Network Kernel Density Visualization"],"prefix":"10.14778","volume":"17","author":[{"given":"Tsz Nam","family":"Chan","sequence":"first","affiliation":[{"name":"Shenzhen University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Zang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojian","family":"Zhu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leong Hou","family":"U","sequence":"additional","affiliation":[{"name":"University of Macau"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dingming","family":"Wu","sequence":"additional","affiliation":[{"name":"Shenzhen University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2024. ArcGIS. https:\/\/www.arcgis.com\/index.html."},{"key":"e_1_2_1_2_1","unstructured":"2024. Chicago Data Portal. https:\/\/data.cityofchicago.org\/Transportation\/Traffic-Crashes-Crashes\/85ca-t3if."},{"key":"e_1_2_1_3_1","unstructured":"2024. City of Detroit Open Data Portal. https:\/\/data.detroitmi.gov\/datasets\/detroitmi::911-calls-for-service\/about."},{"key":"e_1_2_1_4_1","unstructured":"2024. Gainesville's Open Data Portal. https:\/\/data.cityofgainesville.org\/Public-Safety\/Crime-Responses\/gvua-xt9q\/data."},{"key":"e_1_2_1_5_1","unstructured":"2024. Road Safety Data. https:\/\/data.gov.uk\/dataset\/cb7ae6f0-4be6-4935-9277-47e5ce24a11f\/road-safety-data."},{"key":"e_1_2_1_6_1","unstructured":"2024. SANET. http:\/\/sanet.csis.u-tokyo.ac.jp\/."},{"key":"e_1_2_1_7_1","unstructured":"2024. Seattle Open Data. https:\/\/data.seattle.gov\/Transportation\/SDOT-GIS-Datasets\/jyjy-n3ap."},{"key":"e_1_2_1_8_1","unstructured":"2024. spNetwork (nkde: Network Kernel density estimate). https:\/\/www.rdocumentation.org\/packages\/spNetwork\/versions\/0.4.3.2\/topics\/nkde."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2894140"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904121.2904125"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD. 349--360. 10.1145\/2463676.2465315","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2020.100458"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2020.100435"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2017.05.004"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aap.2017.11.008"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"105252","DOI":"10.1016\/j.aap.2019.07.028","article-title":"Spatial analysis of traffic accidents near and between road intersections in a directed linear network","volume":"132","author":"Briz-Red\u00f3n \u00c1lvaro","year":"2019","unstructured":"\u00c1lvaro Briz-Red\u00f3n, Francisco Mart\u00ednez-Ruiz, and Francisco Montes. 2019. Spatial analysis of traffic accidents near and between road intersections in a directed linear network. Accident Analysis & Prevention 132 (2019), 105252.","journal-title":"Accident Analysis & Prevention"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aap.2013.03.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380561"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494135"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503591"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476312"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554855"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461540"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3018376"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517823"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM58254.2023.00046"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Tsz Nam Chan Leong Hou U Byron Choi Jianliang Xu and Reynold Cheng. 2023. Large-scale Geospatial Analytics: Problems Challenges and Opportunities. In SIGMOD Companion. ACM 21--29. 10.1145\/3555041.3589401","DOI":"10.1145\/3555041.3589401"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551836"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00055"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589711"},{"key":"e_1_2_1_31_1","volume-title":"LION: Fast and High-Resolution Network Kernel Density Visualization (Technical Report). https:\/\/github.com\/edisonchan2013928\/LION\/blob\/main\/LION_TR.pdf.","author":"Chan Tsz Nam","year":"2024","unstructured":"Tsz Nam Chan, Rui Zang, Bojian Zhu, Leong Hou U, Dingming Wu, and Jianliang Xu. 2024. LION: Fast and High-Resolution Network Kernel Density Visualization (Technical Report). https:\/\/github.com\/edisonchan2013928\/LION\/blob\/main\/LION_TR.pdf."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00661-w"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2018.02.001"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367925"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-017-0444-2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2015.2477837"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_39_1","article-title":"spNetwork: A Package for Network Kernel Density Estimation","volume":"13","author":"Gelb Jeremy","year":"2021","unstructured":"Jeremy Gelb. 2021. spNetwork: A Package for Network Kernel Density Estimation. R Journal 13, 2 (2021).","journal-title":"R Journal"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aap.2016.08.015"},{"key":"e_1_2_1_41_1","volume-title":"Dik Lun Lee, and Victor C. S. Lee","author":"Hu Haibo","year":"2006","unstructured":"Haibo Hu, Dik Lun Lee, and Victor C. S. Lee. 2006. Distance Indexing on Road Networks. In VLDB. 894--905. http:\/\/dl.acm.org\/citation.cfm?id=1164204"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3557915.3560963"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aap.2021.106062"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00758-w"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Lei Li Mengxuan Zhang Wen Hua and Xiaofang Zhou. 2020. Fast Query Decomposition for Batch Shortest Path Processing in Road Networks. In ICDE. 1189--1200. 10.1109\/ICDE48307.2020.00107","DOI":"10.1109\/ICDE48307.2020.00107"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2010.07.003"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00032"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","unstructured":"Siqiang Luo Yifeng Luo Shuigeng Zhou Gao Cong and Jihong Guan. 2014. Distributed Spatial Keyword Querying on Road Networks. In EDBT. OpenProceedings.org 235--246. 10.5441\/002\/edbt.2014.23","DOI":"10.5441\/002\/edbt.2014.23"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2803821"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2017.1360782"},{"key":"e_1_2_1_53_1","volume-title":"International journal of environmental research and public health 13, 8","author":"Ni Jianhua","year":"2016","unstructured":"Jianhua Ni, Tianlu Qian, Changbai Xi, Yikang Rui, and Jiechen Wang. 2016. Spatial distribution characteristics of healthcare facilities in Nanjing: Network point pattern analysis and correlation analysis. International journal of environmental research and public health 13, 8 (2016), 833."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"A. Okabe and K. Sugihara. 2012. Spatial Analysis Along Networks: Statistical and Computational Methods. Wiley. https:\/\/books.google.com.hk\/books?id=48GRqj51_W8C","DOI":"10.1002\/9781119967101"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","unstructured":"Dian Ouyang Dong Wen Lu Qin Lijun Chang Ying Zhang and Xuemin Lin. 2020. Progressive Top-K Nearest Neighbors Search in Large Road Networks. In SIGMOD. ACM 1781--1795. 10.1145\/3318464.3389746","DOI":"10.1145\/3318464.3389746"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","unstructured":"Dimitris Papadias Jun Zhang Nikos Mamoulis and Yufei Tao. 2003. Query Processing in Spatial Network Databases. In VLDB. Morgan Kaufmann 802--813. 10.1016\/B978-012722442-8\/50076-8","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","unstructured":"Jeff M. Phillips. 2013. \u2208-Samples for Kernels. In SODA. 1622--1632. 10.1137\/1.9781611973105.116","DOI":"10.1137\/1.9781611973105.116"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.173"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.66"},{"key":"e_1_2_1_60_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"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v090.i01"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921074"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","unstructured":"Jo\u00e3o B. Rocha-Junior Akrivi Vlachou Christos Doulkeridis and Kjetil N\u00f8rv\u00e5g. 2011. Efficient execution plans for distributed skyline query processing. In EDBT. ACM 271--282. 10.1145\/1951365.1951399","DOI":"10.1145\/1951365.1951399"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10940-016-9321-x"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2015.1080829"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567276"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi9110683"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","unstructured":"Bilong Shen Ying Zhao Guoliang Li Weimin Zheng Yue Qin Bo Yuan and Yongming Rao. 2017. V-Tree: Efficient kNN Search on Moving Objects with Road-Network Constraints. In ICDE. 609--620. 10.1109\/ICDE.2017.115","DOI":"10.1109\/ICDE.2017.115"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2330836"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2015.1119279"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213872"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2018.04.005"},{"key":"e_1_2_1_74_1","volume-title":"Geo-spatial Information Science","author":"Wu Yuying","year":"2022","unstructured":"Yuying Wu and Yijing Li. 2022. \"Hot street\" of crime detection in London borough and lockdown impacts. Geo-spatial Information Science (2022), 1--17."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2008.05.001"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2013.05.009"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00583-8"},{"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.1371\/journal.pone.0017381"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00091"},{"key":"e_1_2_1_81_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.","DOI":"10.1145\/2463676.2465319"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783357"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399306"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","unstructured":"Andy Diwen Zhu Hui Ma Xiaokui Xiao Siqiang Luo Youze Tang and Shuigeng Zhou. 2013. Shortest path and distance queries on road networks: towards bridging theory and practice. In SIGMOD. 857--868. 10.1145\/2463676.2465277","DOI":"10.1145\/2463676.2465277"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3648160.3648168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T21:57:31Z","timestamp":1714773451000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3648160.3648168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2]]},"references-count":84,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.14778\/3648160.3648168"],"URL":"https:\/\/doi.org\/10.14778\/3648160.3648168","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,2]]},"assertion":[{"value":"2024-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}