{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,7]],"date-time":"2026-09-07T14:29:20Z","timestamp":1788791360166,"version":"build-2803163510"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>\n                    Network\n                    <jats:italic>K<\/jats:italic>\n                    -function has been the de facto operation for analyzing point patterns in spatial networks, which is widely used in many communities, including geography, ecology, transportation science, social science, and criminology. To analyze a location dataset, domain experts need to generate a network\n                    <jats:italic>K<\/jats:italic>\n                    -function plot that involves computing multiple network\n                    <jats:italic>K<\/jats:italic>\n                    -functions. However, network\n                    <jats:italic>K<\/jats:italic>\n                    -function is a computationally expensive operation that is not feasible to support large-scale datasets, let alone to generate a network\n                    <jats:italic>K<\/jats:italic>\n                    -function plot. To handle this issue, we develop two efficient algorithms, namely count augmentation (CA) and neighbor sharing (NS), which can reduce the worst-case time complexity for computing network\n                    <jats:italic>K<\/jats:italic>\n                    -functions. In addition, we incorporate the advanced shortest path sharing (ASPS) approach into these two methods to further lower the worst-case time complexity for generating network\n                    <jats:italic>K<\/jats:italic>\n                    -function plots. Experiment results on four large-scale location datasets (up to 7.33 million data points) show that our methods can achieve up to 165.85x speedup compared with the state-of-the-art methods.\n                  <\/jats:p>","DOI":"10.14778\/3551793.3551836","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T18:25:03Z","timestamp":1664475903000},"page":"2853-2866","source":"Crossref","is-referenced-by-count":15,"title":["Fast network k-function-based spatial analysis"],"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":"Leong Hou","family":"U","sequence":"additional","affiliation":[{"name":"University of Macau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yun","family":"Peng","sequence":"additional","affiliation":[{"name":"Guangzhou University"}],"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,9,29]]},"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","volume-title":"Chicago Data Portal (last accessed: 3rd","year":"2021","unstructured":"[n.d.]. Chicago Data Portal (last accessed: 3rd December 2021 ). https:\/\/data.cityofchicago.org\/Public-Safety\/Crimes-2001-to-Present\/ijzp-q8t2. [n.d.]. Chicago Data Portal (last accessed: 3rd December 2021). https:\/\/data.cityofchicago.org\/Public-Safety\/Crimes-2001-to-Present\/ijzp-q8t2."},{"key":"e_1_2_1_3_1","volume-title":"d.]. City of Detroit Open Data Portal (last accessed: 3rd","year":"2021","unstructured":"[n. d.]. City of Detroit Open Data Portal (last accessed: 3rd December 2021 ). https:\/\/data.detroitmi.gov\/datasets\/detroitmi::911-calls-for-service\/about. [n. d.]. City of Detroit Open Data Portal (last accessed: 3rd December 2021). https:\/\/data.detroitmi.gov\/datasets\/detroitmi::911-calls-for-service\/about."},{"key":"e_1_2_1_4_1","volume-title":"d.]. OpenStreetMap (last accessed: 3rd","year":"2021","unstructured":"[n. d.]. OpenStreetMap (last accessed: 3rd December 2021 ). https:\/\/www.openstreetmap.org\/. [n. d.]. OpenStreetMap (last accessed: 3rd December 2021). https:\/\/www.openstreetmap.org\/."},{"key":"e_1_2_1_5_1","volume-title":"d.]. Road Safety Data (last accessed: 3rd","year":"2021","unstructured":"[n. d.]. Road Safety Data (last accessed: 3rd December 2021 ). https:\/\/data.gov.uk\/dataset\/cb7ae6f0-4be6-4935-9277-47e5ce24a11f\/road-safety-data. [n. d.]. Road Safety Data (last accessed: 3rd December 2021). https:\/\/data.gov.uk\/dataset\/cb7ae6f0-4be6-4935-9277-47e5ce24a11f\/road-safety-data."},{"key":"e_1_2_1_6_1","volume-title":"d.]. San Francisco Open Data (last accessed: 3rd","year":"2021","unstructured":"[n. d.]. San Francisco Open Data (last accessed: 3rd December 2021 ). https:\/\/data.sfgov.org\/City-Infrastructure\/311-Cases\/vw6y-z8j6. [n. d.]. San Francisco Open Data (last accessed: 3rd December 2021). https:\/\/data.sfgov.org\/City-Infrastructure\/311-Cases\/vw6y-z8j6."},{"key":"e_1_2_1_7_1","unstructured":"[n. d.]. SANET. http:\/\/sanet.csis.u-tokyo.ac.jp\/.  [n. d.]. SANET. http:\/\/sanet.csis.u-tokyo.ac.jp\/."},{"key":"e_1_2_1_8_1","unstructured":"[n. d.]. spNetwork: Spatial Analysis on Network - R Project. https:\/\/cran.r-project.org\/web\/packages\/spNetwork\/spNetwork.pdf.  [n. d.]. spNetwork: Spatial Analysis on Network - R Project. https:\/\/cran.r-project.org\/web\/packages\/spNetwork\/spNetwork.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2020.100458"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9469.2011.00752.x"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2020.100435"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2017.05.004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/gean.12155"},{"key":"e_1_2_1_15_1","unstructured":"Daniele Calandriello and Lorenzo Rosasco. 2018. Statistical and Computational Trade-Offs in Kernel K-Means. In NeurIPS. 9379--9389.  Daniele Calandriello and Lorenzo Rosasco. 2018. Statistical and Computational Trade-Offs in Kernel K-Means. In NeurIPS. 9379--9389."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380561"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494135"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503591"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476312"},{"key":"e_1_2_1_20_1","volume-title":"Kaiyan Zhao, Leong Hou U, Byron Choi, and Jianliang Xu.","author":"Chan Tsz Nam","year":"2022","unstructured":"Tsz Nam Chan , Pak Lon Ip , Kaiyan Zhao, Leong Hou U, Byron Choi, and Jianliang Xu. 2022 . LIBKDV : A Versatile Kernel Density Visualization Library for Geospatial Analytics . Proc. VLDB Endow. (To appear) (2022). Tsz Nam Chan, Pak Lon Ip, Kaiyan Zhao, Leong Hou U, Byron Choi, and Jianliang Xu. 2022. LIBKDV: A Versatile Kernel Density Visualization Library for Geospatial Analytics. Proc. VLDB Endow. (To appear) (2022)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461540"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3018376"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517823"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Tsz Nam Chan Leong Hou U Yun Peng Byron Choi and Jianliang Xu. 2022. Fast Network K-function-based Spatial Analysis. https:\/\/www.comp.hkbu.edu.hk\/~edisonchan\/publication\/network_K_function_TR.pdf.  Tsz Nam Chan Leong Hou U Yun Peng Byron Choi and Jianliang Xu. 2022. Fast Network K-function-based Spatial Analysis. https:\/\/www.comp.hkbu.edu.hk\/~edisonchan\/publication\/network_K_function_TR.pdf.","DOI":"10.14778\/3551793.3551836"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00055"},{"key":"e_1_2_1_26_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms , 3 rd Edition. MIT Press . http:\/\/mitpress.mit.edu\/books\/introduction-algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press. http:\/\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2017.1391695"},{"key":"e_1_2_1_28_1","unstructured":"Martin Ester Hans-Peter Kriegel J\u00f6rg Sander and Xiaowei Xu. 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD. 226--231. http:\/\/www.aaai.org\/Library\/KDD\/1996\/kdd96-037.php  Martin Ester Hans-Peter Kriegel J\u00f6rg Sander and Xiaowei Xu. 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD. 226--231. http:\/\/www.aaai.org\/Library\/KDD\/1996\/kdd96-037.php"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0195093"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/02723638.2013.778655"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113369"},{"key":"e_1_2_1_33_1","volume-title":"Spatiotemporal point pattern analysis using Ripley's K function. Geospatial Data Science Techniques and Applications","author":"Hohl Alexander","year":"2017","unstructured":"Alexander Hohl , Minrui Zheng , Wenwu Tang , Eric Delmelle , and Irene Casas . 2017. Spatiotemporal point pattern analysis using Ripley's K function. Geospatial Data Science Techniques and Applications ( 2017 ), 155--175. Alexander Hohl, Minrui Zheng, Wenwu Tang, Eric Delmelle, and Irene Casas. 2017. Spatiotemporal point pattern analysis using Ripley's K function. Geospatial Data Science Techniques and Applications (2017), 155--175."},{"key":"e_1_2_1_34_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 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_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1111\/tgis.12157"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00107"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00032"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ssresearch.2006.05.003"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trf.2015.07.002"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijerph13080833"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.0016-7363.2005.00674.x"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9671.2006.01011.x"},{"key":"e_1_2_1_46_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  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_47_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.2001.tb00448.x"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.watres.2021.116934"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.116"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.173"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.66"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v090.i01"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spasta.2017.10.002"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921074"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2015.1080829"},{"key":"e_1_2_1_57_1","volume-title":"Spatial Analysis of Roadside Acacia Populations on a Road Network using the Network K-Function. Landscape Ecology 19 (07","author":"Spooner Peter","year":"2004","unstructured":"Peter Spooner , Ian Lunt , Atsu Okabe , and Shino Shiode . 2004. Spatial Analysis of Roadside Acacia Populations on a Road Network using the Network K-Function. Landscape Ecology 19 (07 2004 ), 491--499. Peter Spooner, Ian Lunt, Atsu Okabe, and Shino Shiode. 2004. Spatial Analysis of Roadside Acacia Populations on a Road Network using the Network K-Function. Landscape Ecology 19 (07 2004), 491--499."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2330836"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213872"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.171"},{"key":"e_1_2_1_61_1","article-title":"Scalable Kernel K-Means Clustering with Nystrom Approximation","volume":"20","author":"Wang Shusen","year":"2019","unstructured":"Shusen Wang , Alex Gittens , and Michael W. Mahoney . 2019 . Scalable Kernel K-Means Clustering with Nystrom Approximation : Relative-Error Bounds. Journal of Machine Learning Research 20 (2019), 12:1--12:49. http:\/\/jmlr.org\/papers\/v20\/17-517.html Shusen Wang, Alex Gittens, and Michael W. Mahoney. 2019. Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds. Journal of Machine Learning Research 20 (2019), 12:1--12:49. http:\/\/jmlr.org\/papers\/v20\/17-517.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2018.04.005"},{"key":"e_1_2_1_63_1","article-title":"Measuring Spatial Patterns of Health Care Facilities and Their Relationships with Hypertension Inpatients in a Network-Constrained Urban System","volume":"16","author":"Wang Zhensheng","year":"2019","unstructured":"Zhensheng Wang and Ke Nie . 2019 . Measuring Spatial Patterns of Health Care Facilities and Their Relationships with Hypertension Inpatients in a Network-Constrained Urban System . International Journal of Environmental Research and Public Health 16 , 17 (2019). https:\/\/www.mdpi.com\/1660-4601\/16\/17\/3204 Zhensheng Wang and Ke Nie. 2019. Measuring Spatial Patterns of Health Care Facilities and Their Relationships with Hypertension Inpatients in a Network-Constrained Urban System. International Journal of Environmental Research and Public Health 16, 17 (2019). https:\/\/www.mdpi.com\/1660-4601\/16\/17\/3204","journal-title":"International Journal of Environmental Research and Public Health"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2003.10.006"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.2007.00704.x"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007619"},{"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","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2913655"},{"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.1109\/TKDE.2015.2399306"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","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\/3551793.3551836","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:42:30Z","timestamp":1672206150000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551836"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":71,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551836"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551836","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}