Statistical Inference for Spatial Regionalization
Article No.: 65, Pages 1 - 12
Abstract
The process of regionalization involves clustering a set of spatial areas into spatially contiguous regions. Given the NP-hard nature of regionalization problems, all existing algorithms yield approximate solutions. To ascertain the quality of these approximations, it is crucial for domain experts to obtain statistically significant evidence on optimizing the objective function, in comparison to a random reference distribution derived from all potential sample solutions. In this paper, we propose a novel spatial regionalization problem, denoted as SISR (Statistical Inference for Spatial Regionalization), which generates random sample solutions with a predetermined region cardinality. The driving motivation behind SISR is to conduct statistical inference on any given regionalization scheme. To address SISR, we present a parallel technique named PRRP (P-Regionalization through Recursive Partitioning). PRRP operates over three phases: the region growing phase constructs initial regions with a predefined cardinality, while the region merging and region splitting phases ensure the spatial contiguity of unassigned areas, allowing for the growth of subsequent regions with predefined cardinalites. An extensive evaluation shows the effectiveness of PRRP using various real datasets.
References
[1]
H. Alrashid, Y. Liu, and A. Magdy. SMP: Scalable Max-P Regionalization. In SIGSPATIAL, pages 1--4, 2022.
[2]
H. Alrashid, Y. Liu, and A. Magdy. PAGE: Parallel Scalable Regionalization Framework. TSAS, pages 1--27, 2023.
[3]
K. Andreev and H. Racke. Balanced Graph Partitioning. Theory of Computing Systems, 39(6):929--939, 2006.
[4]
l. Anselin. GeoDa, 2003. https://geodacenter.github.io/.
[5]
R. Assunção and et. al. Efficient Regionalization Techniques for Socio-economic Geographical Units Using Minimum Spanning Trees. IJGIS, 20:797--811, 2006.
[6]
O. Aydin, M. V. Janikas, R. Assunção, and T.-H. Lee. SKATER-CON: Unsupervised Regionalization via Stochastic Tree Partitioning Within a Consensus Framework Using Random Spanning Trees. In SIGSPATIAL, pages 33--42, 2018.
[7]
R. Benedetti and et. al. The Identification of Spatially Constrained Homogeneous Clusters of Covid-19 Transmission in Italy. RSPP, 12:1169--1187, 2020.
[8]
U. Benlic and J.-K. Hao. An Effective Multilevel Tabu Search Approach for Balanced Graph Partitioning. Operations Research, 38(7):1066--1075, 2011.
[9]
D. Bereznyi, A. Qutbuddin, Y. Her, and K. Yang. Node-attributed spatial graph partitioning. In SIGSPATIAL, pages 58--67, 2020.
[10]
S. Biswas and et. al. REGAL: A Regionalization Framework for School Boundaries. In SIGSPATIAL, pages 544--547, 2019.
[11]
U. C. Bureau. TIGER/Line Shapefile, 2016, Series Information for the Current Census Tract State-based Shapefile, 2019. https://catalog.data.gov/dataset.
[12]
E. Chambers and et. al. Aggregating Community Maps. In SIGSPATIAL, pages 1--12, 2022.
[13]
D. Combe, C. Largeron, E. Egyed-Zsigmond, and M. Géry. Combining Relations and Text in Scientific Network Clustering. In ASONAM, pages 1248--1253, 2012.
[14]
A. Das, S. Ghosh, K. Das, T. Basu, I. Dutta, and M. Das. Living Environment Matters: Unravelling the Spatial Clustering of COVID-19 Hotspots in Kolkata Megacity, India. Sustainable Cities and Society, 65:102577, 2021.
[15]
D. Delling, D. Fleischman, A. V. Goldberg, I. Razenshteyn, and R. F. Werneck. An Exact Combinatorial Algorithm for Minimum Graph Bisection. Mathematical Programming, 153(2):417--458, 2015.
[16]
J. C. Duque, R. L. Church, and R. S. Middleton. The P-Regions Problem. Geographical Analysis, 43:104--126, 2011.
[17]
J. C. Duque and et. al. The Max-P-Regions Problem. JRS, 52:397--419, 2012.
[18]
J. C. Duque, R. Ramos, and J. Suriñach. Supervised Regionalization Methods: A Survey. IRSR, 30:195--220, 2007.
[19]
U. Feige and R. Krauthgamer. A Polylogarithmic Approximation of the Minimum Bisection. SICOM, 31(4):1090--1118, 2002.
[20]
A. Felner. Finding Optimal Solutions to the Graph Partitioning Problem with Heuristic Search. AMAI, 45(3):293--322, 2005.
[21]
D. C. Folch and S. E. Spielman. Identifying Regions Based On Flexible User-defined Constraints. IJGIS, 28:164--184, 2014.
[22]
Gedicke and et. al. Aggregating Land-use Polygons Considering Line Features as Separating Map Elements. CGIS, 48(2):124--139, 2021.
[23]
J.-H. Haunert and A. Wolff. Area Aggregation in Map Generalisation by Mixed-integer Programming. IJGIS, 24(12):1871--1897, 2010.
[24]
J. Hurley. Regionalization and the Allocation of Healthcare Resources to Meet Population Health Needs. Healthcare Papers, 5:34--39, 2004.
[25]
Y. Kang and A. Magdy. EMP: Max-P Regionalization with Enriched Constraints. In ICDE, 2022.
[26]
H. Kim, Y. Chun, and K. Kim. Delimitation of Functional Regions Using a P-Regions Problem Approach. IRSR, 38:235--263, 2015.
[27]
K. Kim and et. al. Spatial Optimization for Regionalization Problems with Spatial Interaction: a Heuristic Approach. IJGIS, 30(3):451--473, 2016.
[28]
K. Kim and et. al. p-Functional Clusters Location Problem for Detecting Spatial Clusters with Covering Approach. Geographical Analysis, 49:101--121, 2017.
[29]
Y. Kong, Y. Zhu, and Y. Wang. A Center-based Modeling Approach to Solve the Districting Problem. IJGIS, 33(2):368--384, 2019.
[30]
J. Laura, W. Li, S. J. Rey, and L. Anselin. Parallelization of a Regionalization Heuristic in Distributed Computing Platforms-a Case Study of Parallel-P-Compact-Regions Problem. IJGIS, 29:536--555, 2015.
[31]
C. Li, Y. Yin, X. Liu, and P. Wu. An Automated Processing Method for Agglomeration Areas. ISPRS, 7(6):204, 2018.
[32]
C. Li, Y. Yin, P. Wu, and W. Wu. An Area Merging Method in Map Generalization Considering Typical Characteristics of Structured Geographic Objects. CGIS, 48(3):210--224, 2021.
[33]
W. Li, R. L. Church, and M. F. Goodchild. The p-Compact-Regions Problem. Geographical Analysis, 46:250--273, 2014.
[34]
Y. Liang and et. al. Region2Vec: Community Detection on Spatial Networks Using Graph Embedding with Node Attributes and Spatial Interactions. In SIGSPATIAL, pages 1--4, 2022.
[35]
Y. Liu, A. R. Mahmood, A. Magdy, and S. Rey. PRUC: P-Regions with User-Defined Constraint. In VLDB, pages 491--503, 2022.
[36]
J. Oehrlein and J.-H. Haunert. A Cutting-Plane Method for Contiguity-Constrained Spatial Aggregation. JOSIS, (15):89--120, 2017.
[37]
T. R. Depth-first Search and Linear Graph Algorithms. SICOM, 1:114--121, 1971.
[38]
S. Rey. Random Regions, 2021. https://github.com/sjsrey/spopt/blob/randomregion/notebooks/randomregion.ipynb.
[39]
K. Schloegel, G. Karypis, and V. Kumar. Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning. In European Conference on Parallel Processing, pages 296--310, 2000.
[40]
B. She, J. C. Duque, and X. Ye. The network-max-p-regions model. IJGIS, 31:962--981, 2017.
[41]
R. Wei, S. Rey, and E. Knaap. Efficient Regionalization for Spatially Explicit Neighborhood Delineation. IJGIS, 35:1--17, 2020.
[42]
J. Yao, X. Zhang, and A. T. Murray. Spatial Optimization for Land-use Allocation: Accounting for Sustainability Concerns. IRSR, 41(6):579--600, 2018.
[43]
X. Ye, B. She, and S. Benya. Exploring Regionalization in the Network Urban Space. JGSA, 2:4, 2018.
[44]
Y. Zhou, H. Cheng, and J. X. Yu. Graph Clustering Based on Structural/Attribute Similarities. PVLDB, 2:718--729, 2009.
Index Terms
- Statistical Inference for Spatial Regionalization
Recommendations
PAGE: Parallel Scalable Regionalization Framework
Regionalization techniques group spatial areas into a set of homogeneous regions to analyze and draw conclusions about spatial phenomena. A recent regionalization problem, called MP-regions, groups spatial areas to produce a maximum number of regions by ...
Spatial clustering and outlier analysis for the regionalization of maize cultivation in China
Regionalization has been the foundation of large-scale plantation and local optimization for crop cultivation. Current regionalization approaches practiced mainly rely on qualitative analysis and heuristic methods, which cannot meet the increasingly ...
Spatial clustering and outlier analysis for the regionalization of maize cultivation in China
ACACOS'10: Proceedings of the 9th WSEAS international conference on Applied computer and applied computational scienceRegionalization has been the foundation of large-scale plantation and local optimization for crop cultivation. Current regionalization approaches practiced mainly rely on qualitative analysis and heuristic methods, which cannot meet the increasingly ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
686 pages
ISBN:9798400701689
DOI:10.1145/3589132
- General Chairs:
- Maria Luisa Damiani,
- Matthias Renz,
- Program Chairs:
- Ahmed Eldawy,
- Peer Kröger,
- Mario A Nascimento
Copyright © 2023 Owner/Author(s).
This work is licensed under a Creative Commons Attribution-NoDerivs International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 December 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation
- Google-CAHSI research grant
- Saudi Arabia Cultural Mission SACM
Conference
SIGSPATIAL '23
Sponsor:
SIGSPATIAL '23: 31st ACM International Conference on Advances in Geographic Information Systems
November 13 - 16, 2023
Hamburg, Germany
Acceptance Rates
Overall Acceptance Rate 257 of 1,238 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 283Total Downloads
- Downloads (Last 12 months)275
- Downloads (Last 6 weeks)18
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in