{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T12:48:56Z","timestamp":1777121336767,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation, USA","doi-asserted-by":"crossref","award":["IIS-2237348"],"award-info":[{"award-number":["IIS-2237348"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"I-GUIDE Institute","award":["2118329"],"award-info":[{"award-number":["2118329"]}]},{"name":"Google-CAHSI research"},{"name":"Microsoft unrestricted gift"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>The widespread availability of geotagged data combined with modern map services allows for the accurate attachment of data to spatial networks. Applying statistical analysis, such as hotspot detection, over spatial networks is very important for precise quantification and patterns analysis, which empowers effective decision-making in various important applications. Existing hotspot detection algorithms on spatial networks either lack sufficient statistical evidence on detected hotspots, such as clustering, or they provide statistical evidence at a prohibitive computational overhead. In this article, we propose efficient algorithms for detecting hotspots based on the network local K-function for predefined and unknown hotspot radii. The K-function is a widely adopted statistical approach for network pattern analysis that enables the understanding of the density and distribution of activities and events happening within the spatial network. However, its practical application has been limited due to the inefficiency of state-of-the-art algorithms, particularly for large-sized networks. Extensive experimental evaluation using real and synthetic datasets shows that our algorithms are up to 28 times faster than the state-of-the-art algorithms in computing hotspots with a predefined radius and up to more than four orders of magnitude faster in identifying hotspots without a predefined radius. Additionally, to address dynamic changes in the spatial network, we propose an incremental hotspot detection approach that efficiently updates hotspot computations by leveraging prior results as new events are added.<\/jats:p>\n                  <jats:p\/>","DOI":"10.1145\/3766549","type":"journal-article","created":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T11:41:16Z","timestamp":1757590876000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Progressive and Scalable Hotspot Detection through Local K-Function in Spatial Networks"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8488-201X","authenticated-orcid":false,"given":"Yunfan","family":"Kang","sequence":"first","affiliation":[{"name":"University of Illinois Urbana-Champaign","place":["Urbana, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8388-9156","authenticated-orcid":false,"given":"Yongyi","family":"Liu","sequence":"additional","affiliation":[{"name":"University of California Riverside","place":["Riverside, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4545-2270","authenticated-orcid":false,"given":"Pratham","family":"Juvekar","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign","place":["Urbana, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8886-6364","authenticated-orcid":false,"given":"Ahmed","family":"Mahmood","sequence":"additional","affiliation":[{"name":"Google Inc","place":["Madison, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5848-590X","authenticated-orcid":false,"given":"Shaowen","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign","place":["Urbana, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6345-9730","authenticated-orcid":false,"given":"Amr","family":"Magdy","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, University of California Riverside","place":["Riverside, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,25]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.4324\/9780429455391"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101090050013"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551836"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2018.1541177"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"2377","DOI":"10.1007\/s00500-013-1211-7","article-title":"Spatio-temporal hotspots and application on a disease analysis case via GIS","volume":"18","author":"Martino Ferdinando Di","year":"2014","unstructured":"Ferdinando Di Martino, Salvatore Sessa, Umberto ES Barillari, and Maria Rosaria Barillari. 2014. Spatio-temporal hotspots and application on a disease analysis case via GIS. Soft Computing 18, 12 (2014), 2377\u20132384.","journal-title":"Soft Computing"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_1_8_2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.5194\/isprs-archives-XLII-4-W18-335-2019","article-title":"An integrated network-constrained spatial analysis for car accidents: A case study of tehran city, iran","volume":"42","author":"EslamiNezhad SA","year":"2019","unstructured":"SA EslamiNezhad and MR Delavar. 2019. An integrated network-constrained spatial analysis for car accidents: A case study of tehran city, iran. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLII-4\/W18, 42 (2019), 335\u2013342.","journal-title":"The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences"},{"key":"e_1_3_1_9_2","first-page":"226","volume-title":"Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD)","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, Xiaowei Xu, et\u00a0al. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise.. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD). 226\u2013231."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.1992.tb00261.x"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1109\/ICDMW58026.2022.00135","volume-title":"Proceedings of the 2022 IEEE International Conference on Data Mining Workshops (ICDMW)","author":"Gunturi Venkata MV","year":"2022","unstructured":"Venkata MV Gunturi, Rakesh Rajeev, Vipul Bondre, Aaditya Barnwal, Samir Jain, Ashank Anshuman, and Manish Gupta. 2022. A case study on periodic spatio-temporal hotspot detection in azure traffic data. In Proceedings of the 2022 IEEE International Conference on Data Mining Workshops (ICDMW). 1037\u20131044."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apgeog.2018.08.001"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3494530"},{"key":"e_1_3_1_15_2","unstructured":"Kaggle. 2020. Seattle SDOT Collisions Data. Retrieved from https:\/\/www.kaggle.com\/datasets\/jonleon\/seattle-sdot-collisions-data. (2020)."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.envpol.2007.06.012"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12061-017-9230-x"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3423457.3429368"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.5604\/01.3001.0014.2970"},{"issue":"2","key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1080\/19475683.2015.1008572","article-title":"Disease cluster detection methods: Recent developments and public health implications","volume":"21","author":"Mclafferty Sara","year":"2015","unstructured":"Sara Mclafferty. 2015. Disease cluster detection methods: Recent developments and public health implications. Annals of GIS 21, 2 (2015), 127\u2013133.","journal-title":"Annals of GIS"},{"issue":"3","key":"e_1_3_1_21_2","doi-asserted-by":"crossref","first-page":"2662","DOI":"10.3390\/su7032662","article-title":"A network-constrained integrated method for detecting spatial cluster and risk location of traffic crash: A case study from wuhan, China","volume":"7","author":"Nie Ke","year":"2015","unstructured":"Ke Nie, Zhensheng Wang, Qingyun Du, Fu Ren, and Qin Tian. 2015. A network-constrained integrated method for detecting spatial cluster and risk location of traffic crash: A case study from wuhan, China. Sustainability 7, 3 (2015), 2662\u20132677.","journal-title":"Sustainability"},{"key":"e_1_3_1_22_2","unstructured":"NYCOpenData. 2023. New York City Motor Vehicle Collisions - Crashes. Retrieved from https:\/\/opendata.cityofnewyork.us. (2023)."},{"key":"e_1_3_1_23_2","unstructured":"City of Detroit Open Data Portal. 2023. Detroit 911 Calls For Service. Retrieved from https:\/\/data.detroitmi.gov. (2023)."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.0016-7363.2005.00674.x"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781119967101"},{"key":"e_1_3_1_26_2","unstructured":"OSMnx library 2020. Python OSMnx Library User reference. Retrieved from https:\/\/osmnx.readthedocs.io\/en\/stable\/osmnx.html. (2020)."},{"key":"e_1_3_1_27_2","unstructured":"Chicago Data Portal. 2023. Chicago Crime Data. Retrieved from https:\/\/data.cityofchicago.org\/. (2023)."},{"key":"e_1_3_1_28_2","first-page":"1","article-title":"Identification and characterization of spatio-temporal hotspots of forest fires in south asia","volume":"191","author":"Reddy C Sudhakar","year":"2019","unstructured":"C Sudhakar Reddy, Natalia Grace Bird, S Sreelakshmi, T Maya Manikandan, Mahbooba Asra, P Hari Krishna, CS Jha, PVN Rao, and PG Diwakar. 2019. Identification and characterization of spatio-temporal hotspots of forest fires in south asia. Environmental Monitoring and Assessment 191, Suppl 3 (2019), 1\u201317.","journal-title":"Environmental Monitoring and Assessment"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms6347"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139981"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/3172929"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2021.1990301"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658810801949843"},{"key":"e_1_3_1_35_2","doi-asserted-by":"crossref","DOI":"10.1002\/9781119528203","volume-title":"Epidemiology and Geography: Principles, Methods and Tools of Spatial Analysis","author":"Souris Marc","year":"2019","unstructured":"Marc Souris. 2019. Epidemiology and Geography: Principles, Methods and Tools of Spatial Analysis. John Wiley & Sons."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2009.08.005"},{"issue":"4","key":"e_1_3_1_37_2","doi-asserted-by":"crossref","first-page":"e0215434","DOI":"10.1371\/journal.pone.0215434","article-title":"Detecting spatio-temporal hotspots of scarlet fever in taiwan with spatio-temporal gi* statistic","volume":"14","author":"Tang Jia-Hong","year":"2019","unstructured":"Jia-Hong Tang, Tzu-Jung Tseng, and Ta-Chien Chan. 2019. Detecting spatio-temporal hotspots of scarlet fever in taiwan with spatio-temporal gi* statistic. PloS One 14, 4 (2019), e0215434.","journal-title":"PloS One"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2631518"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64367-0_15"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359100"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.2307\/143141"},{"issue":"1","key":"e_1_3_1_42_2","first-page":"77","article-title":"Hot routes: Developing a new technique for the spatial analysis of crime","volume":"1","author":"Tompson Lisa","year":"2009","unstructured":"Lisa Tompson, Henry Partridge, and Naomi Shepherd. 2009. Hot routes: Developing a new technique for the spatial analysis of crime. Crime Mapping: A Journal of Research and Practice 1, 1 (2009), 77\u201396.","journal-title":"Crime Mapping: A Journal of Research and Practice"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.3390\/ijgi8050218"},{"issue":"2","key":"e_1_3_1_44_2","first-page":"1","article-title":"Statistically-robust clustering techniques for mapping spatial hotspots: A survey","volume":"55","author":"Xie Yiqun","year":"2022","unstructured":"Yiqun Xie, Shashi Shekhar, and Yan Li. 2022. Statistically-robust clustering techniques for mapping spatial hotspots: A survey. ACM Computing Surveys (CSUR) 55, 2 (2022), 1\u201338.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3354189"},{"issue":"2","key":"e_1_3_1_46_2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10940-016-9292-y","article-title":"Shooting on the street: Measuring the spatial influence of physical features on gun violence in a bounded street network","volume":"33","author":"Xu Jie","year":"2017","unstructured":"Jie Xu and Elizabeth Griffiths. 2017. Shooting on the street: Measuring the spatial influence of physical features on gun violence in a bounded street network. Journal of Quantitative Criminology 33, 2 (2017), 237\u2013253.","journal-title":"Journal of Quantitative Criminology"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2997014"},{"issue":"2","key":"e_1_3_1_48_2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.jtrangeo.2003.10.006","article-title":"Comparison of planar and network K-functions in traffic accident analysis","volume":"12","author":"Yamada Ikuho","year":"2004","unstructured":"Ikuho Yamada and Jean-Claude Thill. 2004. Comparison of planar and network K-functions in traffic accident analysis. Journal of Transport Geography 12, 2 (2004), 149\u2013158.","journal-title":"Journal of Transport Geography"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.2007.00704.x"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589132.3625599"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007619"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3766549","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T12:25:08Z","timestamp":1777119908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3766549"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,25]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3766549"],"URL":"https:\/\/doi.org\/10.1145\/3766549","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,25]]},"assertion":[{"value":"2024-11-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}