{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:03Z","timestamp":1750309443004,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T00:00:00Z","timestamp":1744329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["2126449"],"award-info":[{"award-number":["2126449"]}]},{"name":"National Institute Of Environmental Health Sciences of the National Institutes of Health","award":["R21ES031226"],"award-info":[{"award-number":["R21ES031226"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Application domains such as environmental health science, climate science, and geosciences\u2014where the relationship between humans and the environment is studied\u2014are constantly evolving and require innovative approaches in geospatial data analysis. Recent technological advancements have led to the proliferation of high-granularity geospatial data, enabling such domains but posing major challenges in managing vast datasets that have high spatiotemporal similarities. We introduce the Hierarchical Grid Partitioning (HierGP) framework to address this issue. Unlike conventional discrete global grid systems, HierGP dynamically adapts to the data\u2019s inherent characteristics. At the core of our framework is the Map Point Reduction algorithm, designed to aggregate and then collapse data points based on user-defined similarity criteria. This effectively reduces data volume while preserving essential information. The reduction process is particularly effective in handling environmental data from extensive geographical regions. We structure the data into a multilevel hierarchy from which a reduced representative dataset can be extracted. We compare the performance of HierGP against several state-of-the-art geospatial indexing algorithms and demonstrate that HierGP outperforms the existing approaches in terms of runtime, memory footprint, and scalability. We illustrate the benefits of the HierGP approach using two representative applications: analysis of over 289 million location samples from a registry of participants and efficient extraction of environmental data from large polygons. While the application demonstration in this work has focused on environmental health, the methodology of the HierGP framework can be extended to explore diverse geospatial analytics domains.<\/jats:p>","DOI":"10.1145\/3699511","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T15:38:50Z","timestamp":1728401930000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["HierGP: Hierarchical Grid Partitioning for Scalable Geospatial Data Analytics"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1017-5338","authenticated-orcid":false,"given":"Olufunso","family":"Oje","sequence":"first","affiliation":[{"name":"Washington State University, Pullman, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5293-6090","authenticated-orcid":false,"given":"Tashi","family":"Stirewalt","sequence":"additional","affiliation":[{"name":"Washington State University, Pullman, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8835-3104","authenticated-orcid":false,"given":"Ofer","family":"Amram","sequence":"additional","affiliation":[{"name":"Washington State University, Pullman, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9454-4986","authenticated-orcid":false,"given":"Perry","family":"Hystad","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1427-5756","authenticated-orcid":false,"given":"Solmaz","family":"Amiri","sequence":"additional","affiliation":[{"name":"Washington State University, Pullman, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5383-8032","authenticated-orcid":false,"given":"Assefaw","family":"Gebremedhin","sequence":"additional","affiliation":[{"name":"Washington State University, Pullman, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,11]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Mark Altaweel. 2024. H3: Open Source Geospatial Indexing System. Retrieved January 24 2024 from https:\/\/www.geographyrealm.com\/h3-open-source-geospatial-indexing-system\/"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_4"},{"issue":"2","key":"e_1_3_1_4_2","first-page":"183","article-title":"An axis-shifted grid-clustering algorithm","volume":"12","author":"Chang Chung-I.","year":"2009","unstructured":"Chung-I. Chang, Nancy P. Lin, Nien-Yi Jan et\u00a0al. 2009. An axis-shifted grid-clustering algorithm. J. Appl. Sci. Eng. 12, 2 (2009), 183\u2013192.","journal-title":"J. Appl. Sci. Eng."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.worlddev.2021.105745"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1080\/01430750.2022.2037460"},{"key":"e_1_3_1_7_2","unstructured":"GISGeography. 2024. What is NDVI (Normalized Difference Vegetation Index)? Retrieved April 20 2024 from https:\/\/gisgeography.com\/ndvi-normalized-difference-vegetation-index\/"},{"key":"e_1_3_1_8_2","unstructured":"Google. 2023. ERA5-Land Hourly\u2014ECMWF Climate Reanalysis bookmark. Retrieved January 20 2023 from https:\/\/developers.google.com\/earth-engine\/datasets\/catalog\/ECMWF_ERA5_LAND_HOURLY"},{"key":"e_1_3_1_9_2","unstructured":"Google. 2023. MOD13Q1.061 Terra Vegetation Indices 16-Day Global 250m. Retrieved January 20 2023 from https:\/\/developers.google.com\/earth-engine\/datasets\/catalog\/MODIS_061_MOD13Q1"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276312"},{"issue":"11","key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"117005","DOI":"10.1289\/EHP10829","article-title":"Bring your own location data: Use of Google smartphone location history data for environmental health research","volume":"130","author":"Hystad Perry","year":"2022","unstructured":"Perry Hystad, Ofer Amram, Funso Oje, Andrew Larkin, Kwadwo Boakye, Ally Avery, Assefaw Gebremedhin, and Glen Duncan. 2022. Bring your own location data: Use of Google smartphone location history data for environmental health research. Environ. Health Perspect. 130, 11 (2022), 117005.","journal-title":"Environ. Health Perspect."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/2.781637"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/9780470316801.ch2","article-title":"Partitioning around medoids (program PAM)","volume":"344","author":"Kaufman Leonard","year":"1990","unstructured":"Leonard Kaufman and Peter J. Rousseeuw. 1990. Partitioning around medoids (program PAM). Finding Groups Data: Intro. Cluster Anal. 344 (1990), 68\u2013125.","journal-title":"Finding Groups Data: Intro. Cluster Anal."},{"key":"e_1_3_1_14_2","volume-title":"Finding Groups in Data: An Introduction to Cluster Analysis","author":"Kaufman Leonard","year":"2009","unstructured":"Leonard Kaufman and Peter J. Rousseeuw. 2009. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons, New York, NY."},{"key":"e_1_3_1_15_2","first-page":"41","article-title":"Applied open-source discrete global grid systems","volume":"3","author":"Kmoch Alexander","year":"2022","unstructured":"Alexander Kmoch, Oleksandr Matsibora, Ivan Vasilyev, and Evelyn Uuemaa. 2022. Applied open-source discrete global grid systems. AGILE: GISci. Series 3 (2022), 41.","journal-title":"AGILE: GISci. Series"},{"issue":"3","key":"e_1_3_1_16_2","first-page":"343","article-title":"Lightweight indexing and querying services for big spatial data","volume":"12","author":"Lee Kisung","year":"2016","unstructured":"Kisung Lee, Ling Liu, Raghu K. Ganti, Mudhakar Srivatsa, Qi Zhang, Yang Zhou, and Qingyang Wang. 2016. Lightweight indexing and querying services for big spatial data. IEEE Trans. Serv. Comput. 12, 3 (2016), 343\u2013355.","journal-title":"IEEE Trans. Serv. Comput."},{"issue":"13","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"7566","DOI":"10.3390\/su14137566","article-title":"Application of clustering algorithms in the location of electric taxi charging stations","volume":"14","author":"Li Qing","year":"2022","unstructured":"Qing Li, Xue Li, Zuyu Liu, and Yaping Qi. 2022. Application of clustering algorithms in the location of electric taxi charging stations. Sustainability 14, 13 (2022), 7566.","journal-title":"Sustainability"},{"issue":"4","key":"e_1_3_1_18_2","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1080\/13658816.2017.1391389","article-title":"A discrete global grid system for earth system modeling","volume":"32","author":"Lin Bingxian","year":"2018","unstructured":"Bingxian Lin, Liangchen Zhou, Depeng Xu, A.-Xing Zhu, and Guonian Lu. 2018. A discrete global grid system for earth system modeling. Int. J. Geogr. Info. Sci. 32, 4 (2018), 711\u2013737.","journal-title":"Int. J. Geogr. Info. Sci."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2003.08.014"},{"key":"e_1_3_1_20_2","first-page":"281","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability","author":"MacQueen J.","year":"1967","unstructured":"J. MacQueen. 1967. Classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281\u2013297."},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"T. Soni Madhulatha. 2012. An overview on clustering methods. Retrieved from https:\/\/arXiv:1205.1117","DOI":"10.9790\/3021-0204719725"},{"key":"e_1_3_1_22_2","first-page":"1","article-title":"Approximation algorithms for multilevel graph partitioning","volume":"10","author":"Monien Burkhard","year":"2007","unstructured":"Burkhard Monien, Robert Preis, and Stefan Schamberger. 2007. Approximation algorithms for multilevel graph partitioning. Handbook Approx. Algor. Metaheur. 10 (2007), 1\u201360.","journal-title":"Handbook Approx. Algor. Metaheur."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033770"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2008.01.039"},{"key":"e_1_3_1_25_2","first-page":"3610","volume-title":"Proceedings of the IEEE International Geoscience and Remote Sensing Symposium (IGARSS\u201916)","author":"Purss Matthew B. J.","year":"2016","unstructured":"Matthew B. J. Purss, Robert Gibb, Faramarz Samavati, Perry Peterson, and Jin Ben. 2016. The OGC discrete global grid system core standard: A framework for rapid geospatial integration. In Proceedings of the IEEE International Geoscience and Remote Sensing Symposium (IGARSS\u201916). IEEE, 3610\u20133613."},{"key":"e_1_3_1_26_2","first-page":"469","volume-title":"Proceedings of the19th Annual European Symposium on Algorithms (ESA\u201911)","author":"Sanders Peter","year":"2011","unstructured":"Peter Sanders and Christian Schulz. 2011. Engineering multilevel graph partitioning algorithms. In Proceedings of the19th Annual European Symposium on Algorithms (ESA\u201911). Springer, 469\u2013480."},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1109\/ICPR.1996.546732","volume-title":"Proceedings of the 13th International Conference on Pattern Recognition","volume":"2","author":"Schikuta Erich","year":"1996","unstructured":"Erich Schikuta. 1996. Grid-clustering: An efficient hierarchical clustering method for very large data sets. In Proceedings of the 13th International Conference on Pattern Recognition, Vol. 2. IEEE, 101\u2013105."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0956-0521(91)90014-V"},{"key":"e_1_3_1_29_2","first-page":"308","volume-title":"Proceedings of the International Workshop on Education Technology and Training and the International Workshop on Geoscience and Remote Sensing","volume":"2","author":"Sun WenBin","year":"2008","unstructured":"WenBin Sun, MaJun Cui, XueSheng Zhao, and YanLi Gao. 2008. A global discrete grid modeling method based on the spherical degenerate quadtree. In Proceedings of the International Workshop on Education Technology and Training and the International Workshop on Geoscience and Remote Sensing, Vol. 2. IEEE, 308\u2013311."},{"key":"e_1_3_1_30_2","first-page":"478","volume-title":"Proceedings of the International Conference on Electrical Engineering and Informatics (ICEEI\u201915)","author":"Suwardi Iping Supriana","year":"2015","unstructured":"Iping Supriana Suwardi, Dody Dharma, Dicky Prima Satya, and Dessi Puji Lestari. 2015. Geohash index based spatial data model for corporate. In Proceedings of the International Conference on Electrical Engineering and Informatics (ICEEI\u201915). IEEE, 478\u2013483."},{"issue":"6","key":"e_1_3_1_31_2","first-page":"1943","article-title":"An overview of partitioning algorithms in clustering techniques","volume":"5","author":"Saket J. Swarndeep","year":"2016","unstructured":"J. Swarndeep Saket and Sharnil Pandya. 2016. An overview of partitioning algorithms in clustering techniques. Int. J. Adv. Res. Comput. Eng. Technol. 5, 6 (2016), 1943\u20131946.","journal-title":"Int. J. Adv. Res. Comput. Eng. Technol."},{"key":"e_1_3_1_32_2","unstructured":"Uber. 2024. H3\u2014Uber\u2019s Hexagonal Hierarchical Spatial Index\u2014Uber Blog. Retrieved January 24 2024 from https:\/\/www.uber.com\/blog\/h3\/"},{"key":"e_1_3_1_33_2","unstructured":"Uber. 2024. Overview of the H3 Geospatial Indexing System. Retrieved January 24 2024 from https:\/\/h3geo.org\/docs\/core-library\/overview\/"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:ANOR.0000039525.80601.15"},{"key":"e_1_3_1_35_2","first-page":"1974","volume-title":"Proceedings of the IEEE 10th Joint International Information Technology and Artificial Intelligence Conference (ITAIC\u201922)","volume":"10","author":"Wu Yitian","year":"2022","unstructured":"Yitian Wu, Gang Wan, Lei Liu, Yao Mu, Zhanji Wei, and Shuai Wang. 2022. A review of the research on discrete global grid systems in digital earth. In Proceedings of the IEEE 10th Joint International Information Technology and Artificial Intelligence Conference (ITAIC\u201922), Vol. 10. IEEE, 1974\u20131978."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s40745-015-0040-1"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233324"},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","first-page":"131","DOI":"10.5194\/isprs-annals-IV-4-W2-131-2017","article-title":"A novel approach of indexing and retrieving spatial polygons for efficient spatial region queries","volume":"4","author":"Zhao J. H.","year":"2017","unstructured":"J. H. Zhao, X. Z. Wang, F. Y. Wang, Z. H. Shen, Y. C. Zhou, and Y. L. Wang. 2017. A novel approach of indexing and retrieving spatial polygons for efficient spatial region queries. ISPRS Ann. Photogram. Remote Sens. Spatial Info. Sci. 4 (2017), 131\u2013138.","journal-title":"ISPRS Ann. Photogram. Remote Sens. Spatial Info. Sci."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3699511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:51Z","timestamp":1750295391000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,11]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3699511"],"URL":"https:\/\/doi.org\/10.1145\/3699511","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2025,4,11]]},"assertion":[{"value":"2024-01-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}