{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:28:57Z","timestamp":1760243337081,"version":"build-2065373602"},"reference-count":78,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2014,10,22]],"date-time":"2014-10-22T00:00:00Z","timestamp":1413936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Remote Sensing"],"abstract":"<jats:p>In computer science, dependence analysis determines whether or not it is safe to parallelize statements in programs. In dealing with the data-intensive and computationally intensive spatial operations in processing massive volumes of geometric features, this dependence can be well utilized for exploiting the parallelism. In this paper, we propose a graph-based divide and conquer method for parallelizing spatial operations (GDCMPSO) on vector data. It can represent spatial data dependences in spatial operations through representing the vector features as graph vertices, and their computational dependences as graph edges. By this way, spatial operations can be parallelized in three steps: partitioning the graph into graph components with inter-component edges firstly, simultaneously processing multiple subtasks indicated by the graph components secondly and finally handling remainder tasks denoted by the inter-component edges. To demonstrate how it works, buffer operation and intersection operation under this paradigm are conducted.  In a 12-core environment, the two spatial operations both gain obvious performance improvements, and the speedups are more than eight. The testing results suggest that GDCMPSO contributes to a method for parallelizing spatial operations and can greatly improve the computing efficiency on multi-core architectures.<\/jats:p>","DOI":"10.3390\/rs61010107","type":"journal-article","created":{"date-parts":[[2014,10,22]],"date-time":"2014-10-22T11:01:56Z","timestamp":1413975716000},"page":"10107-10130","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Graph-Based Divide and Conquer Method for Parallelizing Spatial Operations on Vector Data"],"prefix":"10.3390","volume":"6","author":[{"given":"Xiaochen","family":"Kang","sequence":"first","affiliation":[{"name":"Institute of Photogrammetry and Remote Sensing, Chinese Academy of Surveying and Mapping, NO. 28 Lianhuachi West Road, Beijing 100830, China"},{"name":"School of Resource and Environmental Sciences, Wuhan University, NO. 129 Luoyu Road,  Wuhan 430079, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiangguo","family":"Lin","sequence":"additional","affiliation":[{"name":"Institute of Photogrammetry and Remote Sensing, Chinese Academy of Surveying and Mapping, NO. 28 Lianhuachi West Road, Beijing 100830, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,10,22]]},"reference":[{"key":"ref_1","unstructured":"ESRI (Environmental Systems Research Institute, Inc.) Spatial Operation Functions for St_Geometry. Available online: http:\/\/resources.arcgis.com\/en\/help\/main\/10.1\/index.html#\/\/006z00000020000000."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1080\/136588199241012","article-title":"Progress in computational methods for representing geographical concepts","volume":"13","author":"Egenhofer","year":"1999","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1080\/10835547.1998.12091930","article-title":"Gis research infrastructure for spatial analysis of real estate markets","volume":"9","author":"Anselin","year":"1998","journal-title":"J. House Res"},{"key":"ref_4","unstructured":"Opengis\u00ae Implementation Standard for Geographic Information\u2014Simple Feature Access Part 2: Sql Option, 2010. Available online: http:\/\/portal.opengeospatial.org\/files\/?artifact_id=25354."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2037","DOI":"10.1016\/j.wasman.2010.05.024","article-title":"Combining AHP with GIS for landfill site selection: A case study in the Lake Beysehir catchment area (Konya, Turkey)","volume":"30","author":"Sener","year":"2010","journal-title":"Waste Manag"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1080\/13658816.2010.501334","article-title":"A modified grouping genetic algorithm to select ambulance site locations","volume":"25","author":"Comber","year":"2011","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1080\/02693799308901939","article-title":"A GIS method for riparian water quality buffer generation","volume":"7","author":"Xiang","year":"1993","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1080\/13658810412331317742","article-title":"Typhoon insurance pricing with spatial decision support tools","volume":"19","author":"Li","year":"2005","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1080\/13658816.2011.572075","article-title":"A novel web-based system for tropical cyclone analysis and prediction","volume":"26","author":"Leung","year":"2012","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_10","unstructured":"Gui, D., Lin, Z., Zhang, C., and Liu, F. (September, January 25). On the national geographical condition monitoring several strategic issues. Melbourne, VIC, Australia."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Zhang, J., Li, W., and Zhai, L. (2013). Understanding geographical conditions monitoring: A perspective from China. Int. J. Digit. Earth.","DOI":"10.1080\/17538947.2013.846418"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Shekhar, S., Gunturi, V., Evans, M.R., and Yang, K. (2012, January 20). Spatial big-data challenges intersecting mobility and cloud computing. New York, NY, USA.","DOI":"10.1145\/2258056.2258058"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1080\/02693799108927841","article-title":"Point-set topological spatial relations","volume":"5","author":"Egenhofer","year":"1991","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_14","unstructured":"Palacio, M.P., Sol, D., and Gonz\u00e1lez, J. (2003, January 8\u201312). Graph-based knowledge representation for GIS data. Tlaxcala, Mexico."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/j.isprsjprs.2014.01.007","article-title":"A graph edit dictionary for correcting errors in roof topology graphs reconstructed from point clouds","volume":"93","author":"Xiong","year":"2014","journal-title":"ISPRS J. Photogramm. Remote Sens"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Tobler, W.R. (1970). A computer movie simulating urban growth in the Detroit Region. Econ. Geogr, 234\u2013240.","DOI":"10.2307\/143141"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Fischer, M.M., and Nijkamp, P. (2014). Handbook of Regional Science, Springer.","DOI":"10.1007\/978-3-642-23430-9"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"7212","DOI":"10.3390\/rs6087212","article-title":"Streaming progressive tin densification filter for airborne lidar point clouds using multi-core architectures","volume":"6","author":"Kang","year":"2014","journal-title":"Remote Sens"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Lenoski, D.E., and Weber, W.-D. (1995). Scalable Shared-Memory Multiprocessing, Morgan Kaufmann Publishers.","DOI":"10.1016\/B978-1-55860-315-8.50010-5"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1276","DOI":"10.1016\/j.cageo.2009.12.008","article-title":"Leveraging the power of multi-core platforms for large-scale geospatial data processing: Exemplified by generating dem from massive lidar point clouds","volume":"36","author":"Guan","year":"2010","journal-title":"Comput. Geosci"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/99.660313","article-title":"OpenMP: An industry standard API for shared-memory programming","volume":"5","author":"Dagum","year":"1998","journal-title":"IEEE. Comput. Sci. Eng"},{"key":"ref_22","unstructured":"Reinders, J. (2007). Intel Threading Building Blocks: Outfitting C++ for Multi-Core Processor Parallelism, O\u2019Reilly Media, Inc."},{"key":"ref_23","first-page":"267","article-title":"Applying geocomputation to the analysis of spatial distributions","volume":"1","author":"Openshaw","year":"1999","journal-title":"Geogr. Inf. Syst"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1016\/j.parco.2003.03.001","article-title":"Geocomputation\u2019s future at the extremes: High performance computing and nanoclients","volume":"29","author":"Clarke","year":"2003","journal-title":"Parallel Comput"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Abrahart, R.J., and See, L.M. (2014). Geocomputation, Taylor & Francis.","DOI":"10.1201\/b17091"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1016\/S0098-3004(97)00058-7","article-title":"Massively parallel strategies for local spatial interpolation","volume":"23","author":"Armstrong","year":"1997","journal-title":"Comput. Geosci"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1080\/00045601003791243","article-title":"A cybergis framework for the synthesis of cyberinfrastructure, GIS, and spatial analysis","volume":"100","author":"Wang","year":"2010","journal-title":"Ann. Assoc. Am. Geogr"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/j.cageo.2010.05.024","article-title":"Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS","volume":"37","author":"Huang","year":"2011","journal-title":"Comput. Geosci"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0098-3004(94)90001-9","article-title":"Parallel processing of spatial statistics","volume":"20","author":"Armstrong","year":"1994","journal-title":"Comput. Geosci"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1080\/13658810801918509","article-title":"A theoretical approach to the use of cyberinfrastructure in geographical analysis","volume":"23","author":"Wang","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1707","DOI":"10.1080\/13658816.2011.645477","article-title":"Developing a parallel computational implementation of amoeba","volume":"26","author":"Widener","year":"2012","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/j.cageo.2006.09.008","article-title":"Implementation of a parallel high-performance visualization technique in GRASS GIS","volume":"33","author":"Sorokine","year":"2007","journal-title":"Comput. Geosci"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1080\/13658816.2012.692372","article-title":"A parallel computing approach to viewshed analysis of large terrain data using graphics processing units","volume":"27","author":"Zhao","year":"2013","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1080\/13658816.2012.677538","article-title":"Simultaneous computation of total viewshed on large high resolution grids","volume":"27","author":"Tabik","year":"2013","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1080\/13658816.2012.741240","article-title":"Parallel agent-based simulation of individual-level spatial interactions within a multicore computing environment","volume":"27","author":"Gong","year":"2013","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1016\/S0378-4371(01)00141-8","article-title":"Simulation of pedestrian dynamics using a two-dimensional cellular automaton","volume":"295","author":"Burstedde","year":"2001","journal-title":"Phys. A"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Kang, X. (2014). Graph-based synchronous collaborative mapping. Geocarto Int.","DOI":"10.1080\/10106049.2014.883437"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1080\/13658810902754977","article-title":"Teragrid GIScience gateway: Bridging cyberinfrastructure and GIScience","volume":"23","author":"Wang","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/S0198-9715(00)00011-9","article-title":"Towards a framework for high-performance geocomputation: Handling vector-topology within a distributed service environment","volume":"24","author":"Dowers","year":"2000","journal-title":"Comput. Environ. Urban. Syst"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1080\/13658810902733682","article-title":"Introduction to distributed geographic information processing research","volume":"23","author":"Yang","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1080\/13658810802698571","article-title":"Developing a grid-enabled spatial web portal for Internet GIServices and geospatial cyberinfrastructure","volume":"23","author":"Zhang","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1016\/j.compenvurbsys.2010.04.001","article-title":"Geospatial cyberinfrastructure: Past, present and future","volume":"34","author":"Yang","year":"2010","journal-title":"Comput. Environ. Urban. Syst"},{"key":"ref_43","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_44","doi-asserted-by":"crossref","unstructured":"Qin, C.-Z., Zhan, L.-J., Zhu, A.-X., and Zhou, C.-H. (2014). A strategy for raster-based geocomputation under different parallel computing platforms. Int. J. Geogr. Inf. Sci, 1\u201318.","DOI":"10.1080\/13658816.2014.911300"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"SIAM J. Sci. Comput"},{"key":"ref_46","unstructured":"Hennessy, J.L., and Patterson, D.A. (2011). Computer Architecture: A Quantitative Approach, Morgan Kaufmann. [5th ed.]."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Bernstein, A.J. (1966). Analysis of programs for parallel processing. IEEE Trans. Comput, 757\u2013763.","DOI":"10.1109\/PGEC.1966.264565"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Kuck, D.J., Kuhn, R.H., Padua, D.A., Leasure, B., and Wolfe, M. (1981, January 26\u201328). Dependence graphs and compiler optimizations. Williamsburg, VA, USA.","DOI":"10.1145\/567532.567555"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Maydan, D.E., Hennessy, J.L., and Lam, M.S. (1991). Efficient and Exact Data Dependence Analysis, ACM SIGPLAN Notices.","DOI":"10.1145\/113445.113447"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/71.80122","article-title":"An efficient data dependence analysis for parallelizing compilers","volume":"1","author":"Li","year":"1990","journal-title":"IEEE Trans. Parallel Distrib. Syst"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/BFb0038668","article-title":"Data flow and dependence analysis for instruction level parallelism","volume":"589","author":"Rau","year":"1992","journal-title":"Languages and Compilers for Parallel Computing"},{"key":"ref_52","unstructured":"Rundberg, P., and Stenstr\u00f6m, P. (2002). An all-software thread-level data dependence speculation system for multiprocessors. J. Instruction-Level Parallelism, 3."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/2.546611","article-title":"Shared memory consistency models: A tutorial","volume":"29","author":"Adve","year":"1996","journal-title":"Computer"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1109\/TC.1979.1675439","article-title":"How to make a multiprocessor computer that correctly executes multiprocess programs","volume":"100","author":"Lamport","year":"1979","journal-title":"IEEE Trans. Comput"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Haining, R.P. (2003). Spatial Data Analysis: Theory and Practice, Cambridge University Press.","DOI":"10.1017\/CBO9780511754944"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.compenvurbsys.2012.10.003","article-title":"The 2012 free and open source GIS software map\u2014A guide to facilitate research, development, and adoption","volume":"39","author":"Steiniger","year":"2013","journal-title":"Comput. Environ. Urban. Syst"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Appl. Math"},{"key":"ref_58","unstructured":"Deconinck, S. (2008). The Algorithm Design Manual, Springer-Verlag. [2nd ed]."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","article-title":"Balanced graph partitioning","volume":"39","author":"Andreev","year":"2006","journal-title":"Theor. Comput. Syst"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1016\/S0167-8191(00)00048-X","article-title":"Graph partitioning models for parallel computing","volume":"26","author":"Hendrickson","year":"2000","journal-title":"Parallel Comput"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/0916028","article-title":"An improved spectral graph partitioning algorithm for mapping parallel computations","volume":"16","author":"Hendrickson","year":"1995","journal-title":"SIAM J Sci Comput"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-1-4613-8369-7_3","article-title":"Automatic Mesh Partitioning","volume":"56","author":"George","year":"1993","journal-title":"Graphs theory and Sparse Matrix Computation"},{"key":"ref_63","unstructured":"Nour-Omid, B., Raefsky, A., and Lyzenga, G. (1986, January 13\u201318). Solving finite element equations on concurrent computers. Boston, MA, USA."},{"key":"ref_64","unstructured":"Miller, G.L., Teng, S.-H., and Vavasis, S.A. (1991, January 1\u20134). A unified geometric approach to graph separators. San Juan, Philippines."},{"key":"ref_65","unstructured":"Garbers, J., Promel, H.J., and Steger, A. (1990, January 11\u201315). Finding clusters in VLSI circuits. Santa Clara, CA, USA."},{"key":"ref_66","unstructured":"Bui, T.N., and Jones, C. (1993). A Heuristic for Reducing Fill-in in Sparse Matrix Factorization, Parallel Processing for Scientific Computing."},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"1502","DOI":"10.1109\/43.103500","article-title":"An improved two-way partitioning algorithm with stable performance [VLSI]","volume":"10","author":"Cheng","year":"1991","journal-title":"IEEE Trans. Comput. Aided Design Integr. Circuits Syst"},{"key":"ref_68","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., and Leland, R.W. (1995, January 4\u20138). A multi-level algorithm for partitioning graphs. New York, NY, USA.","DOI":"10.1145\/224170.224228"},{"key":"ref_69","unstructured":"Metis-Serial Graph Partitioning and Fill-Reducing Matrix Ordering. Available online: http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/metis\/overview."},{"key":"ref_70","unstructured":"Karypis, G., and Kumar, V. (2013). A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, University of Minnesota Department of Computer Science and Engineering, Army HPC Research Center."},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/j.envsoft.2011.11.014","article-title":"GRASS GIS: A multi-purpose open source GIS","volume":"31","author":"Neteler","year":"2012","journal-title":"Environ. Modell. Softw"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"1345","DOI":"10.1080\/13658810802634956","article-title":"An overview on current free and open source desktop GIS developments","volume":"23","author":"Steiniger","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci"},{"key":"ref_73","unstructured":"GDAL-Geospatial Data Abstraction Library. Available online: http:\/\/www.gdal.org\/."},{"key":"ref_74","unstructured":"GEOS-Geometry Engine, Open Source. Available online: http:\/\/trac.osgeo.org\/geos\/."},{"key":"ref_75","unstructured":"Libspatialindex. Available online: http:\/\/libspatialindex.github.iso."},{"key":"ref_76","unstructured":"Download Openstreetmap Data for This Region: California. Available online: http:\/\/download.geofabrik.de\/north-america\/us\/california.html."},{"key":"ref_77","unstructured":"Openstreetmap Data. Available online: http:\/\/data.openstreetmapdata.com\/land-polygons-split-4326.zip."},{"key":"ref_78","unstructured":"Geodata. Available online: http:\/\/www.subject.ch\/geo\/subject\/data\/layers\/world\/freegis_worlddata-0.2\/geodata\/."}],"container-title":["Remote Sensing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2072-4292\/6\/10\/10107\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:17:15Z","timestamp":1760217435000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2072-4292\/6\/10\/10107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,22]]},"references-count":78,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2014,10]]}},"alternative-id":["rs61010107"],"URL":"https:\/\/doi.org\/10.3390\/rs61010107","relation":{},"ISSN":["2072-4292"],"issn-type":[{"type":"electronic","value":"2072-4292"}],"subject":[],"published":{"date-parts":[[2014,10,22]]}}}