More Web Proxy on the site http://driver.im/

poster

SMP: scalable max-P regionalization

Authors:

Hussah Alrashid,

Amr MagdyAuthors Info & Claims

SIGSPATIAL '22: Proceedings of the 30th International Conference on Advances in Geographic Information Systems

Article No.: 75, Pages 1 - 4

https://doi.org/10.1145/3557915.3561011

Published: 22 November 2022 Publication History

Abstract

MP-regions is an NP-hard problem that groups spatial areas to produce a maximum number of regions by enforcing a user-defined constraint at the regional level. Existing approximate algorithms for MP-regions do not scale for large datasets due to their high computational cost. This paper introduces SMP; a scalable technique to support MP-regions on large datasets. SMP works on two stages. The first stage finds an initial solution through randomized search, and the second stage improves this solution through efficient heuristic search. SMP optimizes the region building efficiency and quality by tuning the randomized area selection to trade-off runtime with region homogeneity. The experimental evaluation shows the superiority of our technique to support an order of magnitude larger datasets efficiently compared to the state-of-the-art techniques while producing high-quality solutions.

References

[1]

Daniel Arribas-Bel and Charles R Schmidt. 2013. Self-Organizing Maps and the US Urban Spatial Structure. EPB 40 (2013), 362--371.

[2]

Subhodip Biswas, Fanglan Chen, Zhiqian Chen, Andreea Sistrunk, Nathan Self, Chang-Tien Lu, and Naren Ramakrishnan. 2019. REGAL: A Regionalization Framework for School Boundaries. In SIGSPATIAL. 544--547.

Digital Library

[3]

U.S. Census Bureau. 2019. TIGER/Line Shapefile, 2016, Series Information for the Current Census Tract State-based Shapefile. https://catalog.data.gov/dataset/tiger-line-shapefile-2016-series-information-for-the-current-census-tract-state-based-shapefile.

[4]

U.S. Census Bureau. 2021. About the American Community Survey. https://www.census.gov/programs-surveys/acs/about.html.

[5]

U.S. Census Bureau. 2021. ACS Data Stories-Stats in Action! https://www.census.gov/programs-surveys/acs/about/acs-data-stories.html.

[6]

David Combe, Christine Largeron, Elöd Egyed-Zsigmond, and Mathias Géry. 2012. Combining Relations and Text in Scientific Network Clustering. In ASONAM. 1248--1253.

[7]

Juan C Duque, Luc Anselin, and Sergio J Rey. 2012. The Max-P-Regions Problem. JRS 52 (2012), 397--419.

[8]

Juan C Duque, Richard L Church, and Richard S Middleton. 2011. The P-Regions Problem. Geographical Analysis 43 (2011), 104--126.

[9]

Juan C Duque, Jorge E Patino, Luis A Ruiz, and Josep E Pardo-Pascual. 2015. Measuring Intra-urban Poverty Using Land Cover and Texture Metrics Derived from Remote Sensing Data. LUP 135 (2015), 11--21.

[10]

Juan Carlos Duque, Raúl Ramos, and Jordi Suriñach. 2007. Supervised Regionalization Methods: A Survey. IRSR 30 (2007), 195--220.

[11]

David C Folch and Seth E Spielman. 2014. Identifying Regions Based On Flexible User-defined Constraints. IJGIS 28 (2014), 164--184.

Digital Library

[12]

Fred Glover. 1989. Tabu Search---Part I. ORSA 1 (1989), 190--206.

[13]

Diansheng Guo. 2008. Regionalization with Dynamically Constrained Agglomerative Clustering and Partitioning (REDCAP). IJGIS 22 (2008), 801--823.

Digital Library

[14]

Hyun Kim, Yongwan Chun, and Kamyoung Kim. 2015. Delimitation of Functional Regions Using a P-Regions Problem Approach. IRSR 38 (2015), 235--263.

[15]

Kamyoung Kim, Yongwan Chun, and Hyun Kim. 2017. p-Functional Clusters Location Problem for Detecting Spatial Clusters with Covering Approach. Geographical Analysis 49 (2017), 101--121.

[16]

Jason Laura, Wenwen Li, Sergio J Rey, and Luc Anselin. 2015. Parallelization of a Regionalization Heuristic in Distributed Computing Platforms-a Case Study of Parallel-P-Compact-Regions Problem. IJGIS 29 (2015), 536--555.

Digital Library

[17]

Wenwen Li, Richard L Church, and Michael F Goodchild. 2014. An Extendable Heuristic Framework to Solve the P-Compact-Regions Problem for Urban Economic Modeling. CEUS 43 (2014), 1--13.

[18]

Wenwen Li, Richard L Church, and Michael F Goodchild. 2014. The p-Compact-Regions Problem. Geographical Analysis 46 (2014), 250--273.

[19]

Yongyi Liu, Ahmed R. Mahmood, Amr Magdy, and Sergio Rey. 2022. PRUC: P-Regions with User-Defined Constraint. In VLDB. 491--503.

[20]

Maurizio Maravalle and Bruno Simeone. 1995. A Spanning Tree Heuristic for Regional Clustering. CSTM 24 (1995), 625--639.

[21]

Stan Openshaw. 1977. Optimal Zoning Systems for Spatial Interaction Models. EPA 9 (1977), 169--184.

[22]

Jorge E Patino, Juan C Duque, Josep E Pardo-Pascual, and Luis A Ruiz. 2014. Using Remote Sensing to Assess the Relationship Between Crime and the Urban Layout. Applied Geography 55 (2014), 48--60.

[23]

Ate Poorthuis. 2018. How to Draw a Neighborhood? The Potential of Big Data, Regionalization, and Community Detection for Understanding the Heterogeneous Nature of Urban Neighborhoods. Geographical Analysis 50, 2 (2018), 182--203.

[24]

Tarjan R. 1971. Depth-first Search and Linear Graph Algorithms. SICOM 1 (1971), 114--121.

[25]

Sergio J Rey, Luc Anselin, David C Folch, Daniel Arribas-Bel, Myrna L Sastré Gutiérrez, and Lindsey Interlante. 2011. Measuring Spatial Dynamics in Metropolitan Areas. EDQ 25 (2011), 54--64.

[26]

Sergio J Rey and Myrna L Sastré-Gutiérrez. 2010. Interregional Inequality Dynamics in Mexico. SEA 5 (2010), 277--298.

[27]

Bing She, Juan C Duque, and Xinyue Ye. 2017. The Network-Max-P-Regions Model. IJGIS 31 (2017), 962--981.

Digital Library

[28]

V. Sindhu. 2018. Exploring Parallel Efficiency and Synergy for Max-P Region Problem Using Python. Master's thesis. Georgia State University.

[29]

Seth E Spielman and David C Folch. 2015. Reducing Uncertainty in the American Community Survey through Data-driven Regionalization. PloS ONE 10 (2015), e0115626.

[30]

Ran Wei, Sergio Rey, and Elijah Knaap. 2020. Efficient Regionalization for Spatially Explicit Neighborhood Delineation. IJGIS 35 (2020), 1--17.

[31]

Xinyue Ye, Bing She, and Samuel Benya. 2018. Exploring Regionalization in the Network Urban Space. JGSA 2 (2018), 4.

[32]

Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph Clustering Based on Structural/Attribute Similarities. VLDB 2 (2009), 718--729.

Digital Library

Cited By

Liu YMagdy A(2024)Towards Scalable and Expressive Spatial Grouping QueriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3695757(709-710)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3695757
Kang YLiu YAlrashid HBilgi APurohit SMahmood ARey SMagdy A(2024)Pyneapple-R: Scalable and Expressive Spatial Regionalization2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00437(5497-5500)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00437

Index Terms

SMP: scalable max-P regionalization
1. Information systems
  1. Information systems applications
    1. Spatial-temporal systems
      1. Geographic information systems

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 science

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '22: Proceedings of the 30th International Conference on Advances in Geographic Information Systems

November 2022

806 pages

ISBN:9781450395298

DOI:10.1145/3557915

General Chairs:
Matthias Renz
Kiel University, Germany
,
Mohamed Sarwat
Wherobots Inc. / Arizona State University

Copyright © 2022 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 November 2022

Check for updates

Author Tags

Qualifiers

Poster

Conference

SIGSPATIAL '22

Sponsor:

SIGSPATIAL

SIGSPATIAL '22: The 30th International Conference on Advances in Geographic Information Systems

November 1 - 4, 2022

Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
74
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu YMagdy A(2024)Towards Scalable and Expressive Spatial Grouping QueriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3695757(709-710)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3695757
Kang YLiu YAlrashid HBilgi APurohit SMahmood ARey SMagdy A(2024)Pyneapple-R: Scalable and Expressive Spatial Regionalization2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00437(5497-5500)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00437

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents