{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T00:48:14Z","timestamp":1788828494792,"version":"build-2803163510"},"reference-count":25,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,3,23]],"date-time":"2017-03-23T00:00:00Z","timestamp":1490227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41301411"],"award-info":[{"award-number":["41301411"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003819","name":"Natural Science Foundation of Hubei Province","doi-asserted-by":"publisher","award":["2015CFB399"],"award-info":[{"award-number":["2015CFB399"]}],"id":[{"id":"10.13039\/501100003819","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grand Special of High resolution On Earth Observation: Application demonstration system of high resolution remote sensing and transportation","award":["07-Y30B10-9001-14\/16"],"award-info":[{"award-number":["07-Y30B10-9001-14\/16"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>More and more vector-based cellular automata (VCA) models have been built to leverage parallel computing to model rapidly changing cities and urban regions. During parallel simulation, common task decomposition methods based on space partitioning, e.g. grid partitioning (GRID) and recursive binary space partitioning (BSP), do not work well given the heterogeneity of VCA parcel tasks. In this paper, to solve this problem, we propose a novel task decomposition method for distributed VCA models based on k-means clustering, named KCP. Firstly, the polygon dataset is converted into points based on centroids, which combines the size of two parcels and the outer distance. A low-cost recursive quad-partition is then applied to decide the initial cluster centers based on parcel density. Finally, neighbor parcels can be allocated into the same subdivision through k-means clustering. As a result, the proposed KCP method takes both the number of tasks and computing complexity into consideration to achieve a well-balanced local workload. A typical urban VCA growth model was designed to evaluate the proposed KCP method with traditional spatial partitioning methods, i.e. GRID and BSP. KCP had the shortest total simulation time when compared with GRID and BSP. During experimental urban growth simulations, the time spent on a single iteration was reduced by 15% with the BSP and by 25% with the GRID method. The total simulation time with a 120 m neighborhood buffer size was reduced by more than one hour to around three minutes with 32 cores.<\/jats:p>","DOI":"10.3390\/ijgi6040093","type":"journal-article","created":{"date-parts":[[2017,3,23]],"date-time":"2017-03-23T11:47:59Z","timestamp":1490269679000},"page":"93","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Novel k-Means Clustering Based Task Decomposition Method for Distributed Vector-Based CA Models"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3771-3210","authenticated-orcid":false,"given":"Zhenqiang","family":"Li","sequence":"first","affiliation":[{"name":"The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing,Wuhan University, 129 Luoyu Road, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuefeng","family":"Guan","sequence":"additional","affiliation":[{"name":"The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing,Wuhan University, 129 Luoyu Road, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huayi","family":"Wu","sequence":"additional","affiliation":[{"name":"The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing,Wuhan University, 129 Luoyu Road, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianya","family":"Gong","sequence":"additional","affiliation":[{"name":"The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing,Wuhan University, 129 Luoyu Road, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2017,3,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1068\/b33093","article-title":"Vecgca: A vector-based geographic cellular automata model allowing geometric transformations of objects","volume":"35","author":"Menard","year":"2008","journal-title":"Environ. Plan. B Plan. Des."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.compenvurbsys.2008.09.008","article-title":"Implementation of a dynamic neighborhood in a land-use vector-based cellular automata model","volume":"33","author":"Moreno","year":"2009","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/PL00011463","article-title":"Resel filtering to aid visualisation within an exploratory data analysis system","volume":"2","author":"Moore","year":"2000","journal-title":"J. Geogr. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1080\/13658810050057597","article-title":"Development of voronoi-based cellular automata-an integrated dynamic model for geographical information systems","volume":"14","author":"Shi","year":"2000","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_5","unstructured":"Shiyuan, H., and Deren, L. (2004, January 7\u20139). Vector Cellular Automata Based Geographical Entity. Proceedings of the 12th International Conference on Geoinformatics, G\u00e4vle, Sweden."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Allen, J., and Lu, K. (2003). Modeling and prediction of future urban growth in the Charleston region of South Carolina: A GIS-based integrated approach. Conserv. Ecol.","DOI":"10.5751\/ES-00595-080202"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/13658816.2016.1184271","article-title":"Simulating urban growth under planning policies through parcel-based cellular automata (parca) model","volume":"30","author":"Abolhasani","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_8","unstructured":"Gonz\u00e1lez, P.B., G\u00f3mez-Delgado, M., and Benavente, F.-A. (2015, January 7\u201310). Vector-Based Cellular Automata: Exploring New Methods of Urban Growth Simulation with Cadastral Parcels and Graph Theory. Proceedings of the CUPUM 2015, Cambridge, MA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1080\/13658816.2014.987779","article-title":"Characterization of neighborhood sensitivity of an irregular cellular automata model of urban growth","volume":"29","author":"Dahal","year":"2015","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/S0198-9715(00)00012-0","article-title":"High-resolution integrated modelling of the spatial dynamics of urban and regional systems","volume":"24","author":"White","year":"2000","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.compenvurbsys.2015.07.004","article-title":"From raster to vector cellular automata models: A new approach to simulate urban growth with the help of graph theory","volume":"54","year":"2015","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1177\/0037549706068826","article-title":"A parallel fish landscape model for ecosystem modeling","volume":"82","author":"Wang","year":"2006","journal-title":"Simulation"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1080\/13658810903107464","article-title":"Parallel cellular automata for large-scale urban simulation using load-balancing techniques","volume":"24","author":"Li","year":"2010","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.compenvurbsys.2014.09.004","article-title":"Design and implementation strategy of a parallel agent-based schelling model","volume":"49","author":"Kim","year":"2015","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1080\/13658810902984228","article-title":"A general-purpose parallel raster processing programming library test application using a geographic cellular automata model","volume":"24","author":"Guan","year":"2010","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","article-title":"Data clustering: 50 years beyond k-means","volume":"31","author":"Jain","year":"2010","journal-title":"Pattern Recognit. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1080\/01969727308546046","article-title":"A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters","volume":"3","author":"Dunn","year":"1973","journal-title":"J. Cybern."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/TPAMI.1986.4767778","article-title":"Efficient implementation of the fuzzy c-means clustering algorithms","volume":"8","author":"Cannon","year":"1986","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_19","unstructured":"Steinbach, M., Karypis, G., and Kumar, V. (2000, January 20). A Comparison of Document Clustering Techniques. Proceedings of the KDD Workshop on Text Mining, Boston, MA, USA."},{"key":"ref_20","unstructured":"Pelleg, D., and Moore, A.W. (July, January 29). X-means: Extending K-means with Efficient Estimation of the Number of Clusters. Proceedings of the Seventeenth International Conference on Machine Learning, Stanford, CA, USA."},{"key":"ref_21","unstructured":"Johnston, K.M. (2013). Agent Analyst: Agent-Based Modeling in Arcgis, Esri Press."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","article-title":"A bridging model for parallel computation","volume":"33","author":"Valiant","year":"1990","journal-title":"Commun. ACM"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/j.jpdc.2016.04.004","article-title":"Efficient parallel simulation of spatially-explicit agent-based epidemiological models","volume":"93","author":"Rao","year":"2016","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1177\/0037549712462620","article-title":"Parallel agent-based simulation with repast for high performance computing","volume":"89","author":"Collier","year":"2013","journal-title":"Simulation"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Li, Z., Guan, X., Li, R., and Wu, H. (2016). 4d-sas: A distributed dynamic-data driven simulation and analysis system for massive spatial agent-based modeling. ISPRS Int. J. Geo-Inf.","DOI":"10.3390\/ijgi5040042"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/4\/93\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:31:06Z","timestamp":1760207466000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/4\/93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,23]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,4]]}},"alternative-id":["ijgi6040093"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6040093","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,23]]}}}