{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:57:50Z","timestamp":1765357070709},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:p>\n            This paper introduces a generalized spatial regionalization problem, namely, PRUC (\n            <jats:italic>P<\/jats:italic>\n            -Regions with User-defined Constraint) that partitions spatial areas into homogeneous regions. PRUC accounts for user-defined constraints imposed over aggregate region properties. We show that PRUC is an NP-Hard problem. To solve PRUC, we introduce GSLO (Global Search with Local Optimization), a parallel stochastic regionalization algorithm. GSLO is composed of two phases: (1)\n            <jats:italic>Global Search<\/jats:italic>\n            that initially partitions areas into regions that satisfy a user-defined constraint, and (2)\n            <jats:italic>Local Optimization<\/jats:italic>\n            that further improves the quality of the partitioning with respect to intra-region similarity. We conduct an extensive experimental study using real datasets to evaluate the performance of GSLO. Experimental results show that GSLO is up to 100\u00d7 faster than the state-of-the-art algorithms. GSLO provides partitioning that is up to 6\u00d7 better with respect to intra-region similarity. Furthermore, GSLO is able to handle 4\u00d7 larger datasets than the state-of-the-art algorithms.\n          <\/jats:p>","DOI":"10.14778\/3494124.3494133","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:31:46Z","timestamp":1644021106000},"page":"491-503","source":"Crossref","is-referenced-by-count":6,"title":["PRUC"],"prefix":"10.14778","volume":"15","author":[{"given":"Yongyi","family":"Liu","sequence":"first","affiliation":[{"name":"University of California"}]},{"given":"Ahmed R.","family":"Mahmood","sequence":"additional","affiliation":[{"name":"Purdue University"}]},{"given":"Amr","family":"Magdy","sequence":"additional","affiliation":[{"name":"University of California"}]},{"given":"Sergio","family":"Rey","sequence":"additional","affiliation":[{"name":"University of California"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03647-7_15"},{"key":"e_1_2_1_2_1","volume-title":"Stanford","author":"Arthur D.","year":"2006","unstructured":"D. Arthur and S. Vassilvitskii . k-means++: The Advantages of Careful Seeding. Technical report , Stanford , 2006 . D. Arthur and S. Vassilvitskii. k-means++: The Advantages of Careful Seeding. Technical report, Stanford, 2006."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810600665111"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3281548.3281554"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2021.1905819"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397536.3422198"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/14649350307977"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397536.3422265"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359377"},{"key":"e_1_2_1_10_1","volume-title":"Series Information for the Current Census Tract State-based Shapefile","author":"U. C. Bureau","year":"2021","unstructured":"U. C. Bureau . TIGER\/ Line Shapefile , 2016 , Series Information for the Current Census Tract State-based Shapefile , 2021 . https:\/\/catalog.data.gov\/dataset\/tiger-line-shapefile-2016-series-information-for-the-current-census-tract-state-based-shapefile. U. C. Bureau. TIGER\/Line Shapefile, 2016, Series Information for the Current Census Tract State-based Shapefile, 2021. https:\/\/catalog.data.gov\/dataset\/tiger-line-shapefile-2016-series-information-for-the-current-census-tract-state-based-shapefile."},{"key":"e_1_2_1_11_1","volume-title":"A Regionalization Method Based on a Cluster Probability Model. Water Resources Research, 47(11)","author":"Cowpertwait P. S.","year":"2011","unstructured":"P. S. Cowpertwait . A Regionalization Method Based on a Cluster Probability Model. Water Resources Research, 47(11) , 2011 . P. S. Cowpertwait. A Regionalization Method Based on a Cluster Probability Model. Water Resources Research, 47(11), 2011."},{"issue":"53","key":"e_1_2_1_12_1","first-page":"157","article-title":"User's Manual for CPLEX","volume":"46","author":"Cplex I.I.","year":"2009","unstructured":"I.I. Cplex . V12. 1 : User's Manual for CPLEX . International Business Machines Corporation , 46 ( 53 ): 157 , 2009 . I.I. Cplex. V12. 1: User's Manual for CPLEX. International Business Machines Corporation, 46(53):157, 2009.","journal-title":"International Business Machines Corporation"},{"key":"e_1_2_1_13_1","volume-title":"A Spatial Clustering Perspective on Autocorrelation and Regionalization. Environmental and ecological statistics, 15(4):385--401","author":"Csillag F.","year":"2008","unstructured":"F. Csillag , S. Kabos , and T. K. Remmel . A Spatial Clustering Perspective on Autocorrelation and Regionalization. Environmental and ecological statistics, 15(4):385--401 , 2008 . F. Csillag, S. Kabos, and T. K. Remmel. A Spatial Clustering Perspective on Autocorrelation and Regionalization. Environmental and ecological statistics, 15(4):385--401, 2008."},{"issue":"3","key":"e_1_2_1_14_1","first-page":"397","article-title":"The Max-P-Regions Problem. Journal of Regional Science","volume":"52","author":"Duque J. C.","year":"2012","unstructured":"J. C. Duque , L. Anselin , and S. J. Rey . The Max-P-Regions Problem. Journal of Regional Science , JRS , 52 ( 3 ): 397 -- 419 , 2012 . J. C. Duque, L. Anselin, and S. J. Rey. The Max-P-Regions Problem. Journal of Regional Science, JRS, 52(3):397--419, 2012.","journal-title":"JRS"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.2010.00810.x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1177\/0160017607301605"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/gean.12132"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-0462(80)90015-0"},{"key":"e_1_2_1_19_1","volume-title":"Income and Diversity Shapefile","year":"2021","unstructured":"2000 Health , Income and Diversity Shapefile , 2021 . https:\/\/geodacenter.github.io. 2000 Health, Income and Diversity Shapefile, 2021. https:\/\/geodacenter.github.io."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-5915.1977.tb01074.x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810701674970"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00890505"},{"key":"e_1_2_1_23_1","first-page":"1113","article-title":"A Hybrid Heuristic Algorithm for School District Division. The International Archives of Photogrammetry","volume":"42","author":"He X.","year":"2020","unstructured":"X. He and B. Wei . A Hybrid Heuristic Algorithm for School District Division. The International Archives of Photogrammetry , Remote Sensing and Spatial Information Sciences , 42 : 1113 -- 1120 , 2020 . X. He and B. Wei. A Hybrid Heuristic Algorithm for School District Division. The International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 42:1113--1120, 2020.","journal-title":"Remote Sensing and Spatial Information Sciences"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.12927\/hcpap..16836"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/42779"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"issue":"3","key":"e_1_2_1_27_1","first-page":"235","article-title":"Delimitation of Functional Regions Using a p-Regions Problem Approach. International Regional Science Review","volume":"38","author":"Kim H.","year":"2015","unstructured":"H. Kim , Y. Chun , and K. Kim . Delimitation of Functional Regions Using a p-Regions Problem Approach. International Regional Science Review , IRSR , 38 ( 3 ): 235 -- 263 , 2015 . H. Kim, Y. Chun, and K. Kim. Delimitation of Functional Regions Using a p-Regions Problem Approach. International Regional Science Review, IRSR, 38(3):235--263, 2015.","journal-title":"IRSR"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/gean.12109"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59511-5_16"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2891307.2891311"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.1969.tb00615.x"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2014.987287"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2013.10.002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/gean.12038"},{"key":"e_1_2_1_36_1","first-page":"1","volume-title":"International Encyclopedia of Geography:People, the Earth, Environment and Technology: People, the Earth, Environment and Technology","author":"Ligmann-Zielinska A.","year":"2016","unstructured":"A. Ligmann-Zielinska . Spatial Optimization . International Encyclopedia of Geography:People, the Earth, Environment and Technology: People, the Earth, Environment and Technology , pages 1 -- 6 , 2016 . A. Ligmann-Zielinska. Spatial Optimization. International Encyclopedia of Geography:People, the Earth, Environment and Technology: People, the Earth, Environment and Technology, pages 1--6, 2016."},{"key":"e_1_2_1_37_1","first-page":"281","volume-title":"Proceedings of the fifth Berkeley symposium on mathematical statistics and probability","volume":"1","author":"J. MacQueen","year":"1967","unstructured":"J. MacQueen et al. Some Methods for Classification and Analysis of Multivariate Observations . In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability , volume 1 , pages 281 -- 297 , 1967 . J. MacQueen et al. Some Methods for Classification and Analysis of Multivariate Observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281--297, 1967."},{"key":"e_1_2_1_38_1","volume-title":"Survey of Multi-objective Optimization Methods for Engineering. Structural and multidisciplinary optimization, 26(6):369--395","author":"Marler R. T.","year":"2004","unstructured":"R. T. Marler and J. S. Arora . Survey of Multi-objective Optimization Methods for Engineering. Structural and multidisciplinary optimization, 26(6):369--395 , 2004 . R. T. Marler and J. S. Arora. Survey of Multi-objective Optimization Methods for Engineering. Structural and multidisciplinary optimization, 26(6):369--395, 2004."},{"key":"e_1_2_1_39_1","first-page":"31","volume-title":"Regk-means: A Clustering Algorithm Using Spatial Contiguity Constraints For Regionalization Problems. In Brazilian Conference on Intelligent Systems (BRACIS)","author":"Miranda L.","year":"2017","unstructured":"L. Miranda , J. Viterbo Filho , and F. C. Bernardini . Regk-means: A Clustering Algorithm Using Spatial Contiguity Constraints For Regionalization Problems. In Brazilian Conference on Intelligent Systems (BRACIS) , pages 31 -- 36 , 2017 . L. Miranda, J. Viterbo Filho, and F. C. Bernardini. Regk-means: A Clustering Algorithm Using Spatial Contiguity Constraints For Regionalization Problems. In Brazilian Conference on Intelligent Systems (BRACIS), pages 31--36, 2017."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/136588100424954"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2938197.2938206"},{"key":"e_1_2_1_42_1","first-page":"459","volume-title":"Partitioning and Spatial Modelling. Transactions of the Institute of British Geographers","author":"Openshaw S.","year":"1977","unstructured":"S. Openshaw . A Geographical Solution to Scale and Aggregation Problems in Region-Building , Partitioning and Spatial Modelling. Transactions of the Institute of British Geographers , pages 459 -- 472 , 1977 . S. Openshaw. A Geographical Solution to Scale and Aggregation Problems in Region-Building, Partitioning and Spatial Modelling. Transactions of the Institute of British Geographers, pages 459--472, 1977."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROPEC48299.2019.9057044"},{"key":"e_1_2_1_44_1","first-page":"31","article-title":"Regionalization of Urbanization and Spatial Development","volume":"4","author":"Rahman M. M.","year":"2004","unstructured":"M. M. Rahman . Regionalization of Urbanization and Spatial Development : Planning Regions in Bangladesh. The Journal of Geo-Environment , 4 : 31 -- 46 , 2004 . M. M. Rahman. Regionalization of Urbanization and Spatial Development: Planning Regions in Bangladesh. The Journal of Geo-Environment, 4:31--46, 2004.","journal-title":"Planning Regions in Bangladesh. The Journal of Geo-Environment"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2016.1252987"},{"key":"e_1_2_1_47_1","first-page":"517","volume-title":"Proceedings of the 5th International Conference on Frontiers in Intelligent Computing: Theory and Applications","author":"Sheshasaayee A.","year":"2017","unstructured":"A. Sheshasaayee and D. Sridevi . A Combined System for Regionalization in Spatial Data Mining Based on Fuzzy C-Means Algorithm with Gravitational Search Algorithm . In Proceedings of the 5th International Conference on Frontiers in Intelligent Computing: Theory and Applications , pages 517 -- 524 , 2017 . A. Sheshasaayee and D. Sridevi. A Combined System for Regionalization in Spatial Data Mining Based on Fuzzy C-Means Algorithm with Gravitational Search Algorithm. In Proceedings of the 5th International Conference on Frontiers in Intelligent Computing: Theory and Applications, pages 517--524, 2017."},{"key":"e_1_2_1_48_1","volume-title":"Master's thesis","author":"Sindhu V.","year":"2018","unstructured":"V. Sindhu . Exploring Parallel Efficiency and Synergy for Max-P Region Problem Using Python . Master's thesis , Georgia State University , 2018 . V. Sindhu. Exploring Parallel Efficiency and Synergy for Max-P Region Problem Using Python. Master's thesis, Georgia State University, 2018."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/00045608.2012.685044"},{"key":"e_1_2_1_50_1","volume-title":"Courier Corporation","author":"Trudeau R. J.","year":"2013","unstructured":"R. J. Trudeau . Introduction to graph theory . Courier Corporation , 2013 . R. J. Trudeau. Introduction to graph theory. Courier Corporation, 2013."},{"issue":"2","key":"e_1_2_1_51_1","first-page":"222","article-title":"Computer-Based Soil Mapping of Small Areas From Sample Data: Ii. Classification Smoothing. European Journal of Soil Science","volume":"23","author":"Webster R.","year":"1972","unstructured":"R. Webster and P. A. Burrough . Computer-Based Soil Mapping of Small Areas From Sample Data: Ii. Classification Smoothing. European Journal of Soil Science , EJSS , 23 ( 2 ): 222 -- 234 , 1972 . R. Webster and P. A. Burrough. Computer-Based Soil Mapping of Small Areas From Sample Data: Ii. Classification Smoothing. European Journal of Soil Science, EJSS, 23(2):222--234, 1972.","journal-title":"EJSS"},{"key":"e_1_2_1_52_1","first-page":"1","article-title":"A Probabilistic Approach to Address Data Uncertainty","volume":"0","author":"Wei R.","year":"2021","unstructured":"R. Wei , S. Rey , and T. H. Grubesic . A Probabilistic Approach to Address Data Uncertainty in Regionalization. Geographical Analysis , 0 : 1 -- 22 , 2021 . R. Wei, S. Rey, and T. H. Grubesic. A Probabilistic Approach to Address Data Uncertainty in Regionalization. Geographical Analysis, 0:1--22, 2021.","journal-title":"Regionalization. Geographical Analysis"},{"issue":"1","key":"e_1_2_1_53_1","first-page":"135","article-title":"Efficient Regionalization for Spatially Explicit Neighborhood Delineation. International Journal of Geographical Information Science","volume":"35","author":"Wei R.","year":"2021","unstructured":"R. Wei , S. Rey , and E. Knaap . Efficient Regionalization for Spatially Explicit Neighborhood Delineation. International Journal of Geographical Information Science , IJGIS , 35 ( 1 ): 135 -- 151 , 2021 . R. Wei, S. Rey, and E. Knaap. Efficient Regionalization for Spatially Explicit Neighborhood Delineation. International Journal of Geographical Information Science, IJGIS, 35(1):135--151, 2021.","journal-title":"IJGIS"},{"issue":"1","key":"e_1_2_1_54_1","first-page":"1","volume":"11","author":"White D.","year":"1991","unstructured":"D. White , M. Richman , and B. Yarnal . Climate Regionalization and Rotation of Principal Components. International Journal of Climatology , 11 ( 1 ): 1 -- 25 , 1991 . D. White, M. Richman, and B. Yarnal. Climate Regionalization and Rotation of Principal Components. International Journal of Climatology, 11(1):1--25, 1991.","journal-title":"Climate Regionalization and Rotation of Principal Components. International Journal of Climatology"},{"key":"e_1_2_1_55_1","volume-title":"Transferability of Regionalization Methods under Changing Climate. Journal of Hydrology, 568(March 2018):67--81","author":"Yang X.","year":"2019","unstructured":"X. Yang , J. Magnusson , and C.-Y. Xu . Transferability of Regionalization Methods under Changing Climate. Journal of Hydrology, 568(March 2018):67--81 , 2019 . X. Yang, J. Magnusson, and C.-Y. Xu. Transferability of Regionalization Methods under Changing Climate. Journal of Hydrology, 568(March 2018):67--81, 2019."},{"issue":"1","key":"e_1_2_1_56_1","first-page":"1","article-title":"Exploring Regionalization in the Network Urban Space. Journal of Geovisualization and Spatial Analysis","volume":"2","author":"Ye X.","year":"2018","unstructured":"X. Ye , B. She , and S. Benya . Exploring Regionalization in the Network Urban Space. Journal of Geovisualization and Spatial Analysis , JGSA , 2 ( 1 ): 1 -- 11 , 2018 . X. Ye, B. She, and S. Benya. Exploring Regionalization in the Network Urban Space. Journal of Geovisualization and Spatial Analysis, JGSA, 2(1):1--11, 2018.","journal-title":"JGSA"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/645905.672960"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687709"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3494124.3494133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:27:33Z","timestamp":1672226853000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3494124.3494133"}},"subtitle":["P-regions with user-defined constraint"],"short-title":[],"issued":{"date-parts":[[2021,11]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["10.14778\/3494124.3494133"],"URL":"https:\/\/doi.org\/10.14778\/3494124.3494133","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,11]]}}}