{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T21:37:22Z","timestamp":1770413842206,"version":"3.49.0"},"reference-count":32,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2017,9,28]],"date-time":"2017-09-28T00:00:00Z","timestamp":1506556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Science and Technology Project of Qingdao","award":["16-6-2-61-NSH"],"award-info":[{"award-number":["16-6-2-61-NSH"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Airborne Light Detection and Ranging (LiDAR) is widely used in digital elevation model (DEM) generation. However, the very large volume of LiDAR datasets brings a great challenge for the traditional serial algorithm. Using parallel computing to accelerate the efficiency of DEM generation from LiDAR points has been a hot topic in parallel geo-computing. Generally, most of the existing parallel algorithms running on high-performance clusters (HPC) were in process-paralleling mode, with a static scheduling strategy. The static strategy would not respond dynamically according to the computation progress, leading to load unbalancing. Additionally, because each process has independent memory space, the cost of dealing with boundary problems increases obviously with the increase in the number of processes. Actually, these two problems can have a significant influence on the efficiency of DEM generation for larger datasets, especially for those of irregular shapes. Thus, to solve these problems, we combined the advantages of process-paralleling with the advantages of thread-paralleling, forming a new idea: using process-paralleling to achieve a flexible schedule and scalable computation, using thread-paralleling inside the process to reduce boundary problems. Therefore, we proposed a hybrid process\/thread parallel algorithm for generating DEM from LiDAR points. Firstly, at the process level, we designed a parallel method (PPDB) to accelerate the partitioning of LiDAR points. We also proposed a new dynamic scheduling strategy to achieve better load balancing. Secondly, at the thread level, we designed an asynchronous parallel strategy to hide the cost of LiDAR points\u2019 reading. Lastly, we tested our algorithm with three LiDAR datasets. Experiments showed that our parallel algorithm had no influence on the accuracy of the resultant DEM. At the same time, our algorithm reduced the conversion time from 112,486 s to 2342 s when we used the largest dataset (150 GB). The PPDB was parallelizable and the new dynamic scheduling strategy achieved a better load balancing. Furthermore, the asynchronous parallel strategy reduced the impact of LiDAR points reading. When compared with the traditional process-paralleling algorithm, the hybrid process\/thread parallel algorithm improved the conversion efficiency by 30%.<\/jats:p>","DOI":"10.3390\/ijgi6100300","type":"journal-article","created":{"date-parts":[[2017,9,28]],"date-time":"2017-09-28T11:22:44Z","timestamp":1506597764000},"page":"300","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Hybrid Process\/Thread Parallel Algorithm for Generating DEM from LiDAR Points"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7327-7575","authenticated-orcid":false,"given":"Yibin","family":"Ren","sequence":"first","affiliation":[{"name":"Qingdao Collaborative Innovation Center of Marine Science and Technology, College of Information Science and Engineering, Ocean University of China, No. 238, Songling Road, Qingdao 266100, China"},{"name":"Laboratory for Regional Oceanography and Numerical Modeling, Qingdao National Laboratory for Marine Science and Technology, No. 1, Wenhai Road, Qingdao 266237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenjie","family":"Chen","sequence":"additional","affiliation":[{"name":"Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology, Nanjing University, No. 163, Xianlin Avenue, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Chen","sequence":"additional","affiliation":[{"name":"Qingdao Collaborative Innovation Center of Marine Science and Technology, College of Information Science and Engineering, Ocean University of China, No. 238, Songling Road, Qingdao 266100, China"},{"name":"Laboratory for Regional Oceanography and Numerical Modeling, Qingdao National Laboratory for Marine Science and Technology, No. 1, Wenhai Road, Qingdao 266237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Han","sequence":"additional","affiliation":[{"name":"Qingdao Collaborative Innovation Center of Marine Science and Technology, College of Information Science and Engineering, Ocean University of China, No. 238, Songling Road, Qingdao 266100, China"},{"name":"Laboratory for Regional Oceanography and Numerical Modeling, Qingdao National Laboratory for Marine Science and Technology, No. 1, Wenhai Road, Qingdao 266237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanjie","family":"Wang","sequence":"additional","affiliation":[{"name":"Qingdao Collaborative Innovation Center of Marine Science and Technology, College of Information Science and Engineering, Ocean University of China, No. 238, Songling Road, Qingdao 266100, China"},{"name":"Laboratory for Regional Oceanography and Numerical Modeling, Qingdao National Laboratory for Marine Science and Technology, No. 1, Wenhai Road, Qingdao 266237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,9,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0098-3004(98)00032-6","article-title":"A comparison of algorithms used to compute hill slope as a property of the DEM","volume":"24","author":"Jones","year":"1998","journal-title":"Comput. Geosci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Liu, L., and \u00d6ZSU, M.T. (2009). Digital Elevation Models. Encyclopedia of Database Systems, Springer.","DOI":"10.1007\/978-0-387-39940-9"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1080\/13658810600607337","article-title":"Deriving ground surface digital elevation models from LiDAR data with geostatistics","volume":"20","author":"Lloyd","year":"2006","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0034-4257(02)00185-2","article-title":"Utilizing DEMs derived from LIDAR data to analyze morphologic change in the North Carolina coastline","volume":"85","author":"White","year":"2003","journal-title":"Remote Sens. Environ."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"847","DOI":"10.14358\/PERS.71.7.847","article-title":"DEM generation and building detection from Lidar data","volume":"71","author":"Ma","year":"2005","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1109\/LGRS.2012.2205130","article-title":"Fast Filtering of LiDAR Point Cloud in Urban Areas Based on Scan Line Segmentation and GPU Acceleration","volume":"10","author":"Hu","year":"2013","journal-title":"IEEE Geosci. Remote Sens."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.cageo.2010.05.017","article-title":"Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds","volume":"37","author":"Ma","year":"2011","journal-title":"Comput. Geosci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.cageo.2013.05.005","article-title":"Parallel scanline algorithm for rapid rasterization of vector geographic data","volume":"59","author":"Wang","year":"2013","journal-title":"Comput. Geosci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.cageo.2014.08.007","article-title":"Parallel relative radiometric normalisation for remote sensing image mosaics","volume":"73","author":"Chen","year":"2014","journal-title":"Comput. Geosci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1080\/13658816.2011.563744","article-title":"A parallel computing approach to fast geostatistical areal interpolation","volume":"25","author":"Guan","year":"2011","journal-title":"Int. J. Geogr. Inf."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s10586-015-0512-2","article-title":"Geographical information system parallelization for spatial big data processing: A review","volume":"19","author":"Zhao","year":"2016","journal-title":"Clust. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.envsoft.2013.10.005","article-title":"A layered approach to parallel computing for spatially distributed hydrological modeling","volume":"51","author":"Liu","year":"2014","journal-title":"Environ. Modell. Softw."},{"key":"ref_13","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_14","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_15","doi-asserted-by":"crossref","first-page":"2555","DOI":"10.3390\/s90402555","article-title":"Parallel Processing Method for Airborne Laser Scanning Data Using a PC Cluster and a Virtual Grid","volume":"9","author":"Han","year":"2009","journal-title":"Sensors-Basel"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Danner, A., Breslow, A., Baskin, J., and Wilikofsky, D. (2012, January 6\u20139). Hybrid MPI\/GPU interpolation for grid DEM construction. Proceedings of the International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA.","DOI":"10.1145\/2424321.2424360"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Huang, F., Bu, S., Tao, J., and Tan, X. (2016). OpenCL Implementation of a Parallel Universal Kriging Algorithm for Massive Spatial Data Interpolation on Heterogeneous Systems. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5060096"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1016\/S0167-739X(00)00054-6","article-title":"Understanding performance of SMP clusters running MPI programs","volume":"17","author":"Cappello","year":"2001","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.cpc.2010.06.035","article-title":"Hybrid CUDA, OpenMP, and MPI parallel programming on multicore GPU clusters","volume":"182","author":"Yang","year":"2011","journal-title":"Comput. Phys. Commun."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1256","DOI":"10.1016\/j.jcss.2013.02.005","article-title":"Performance modeling of hybrid MPI\/OpenMP scientific applications on large-scale multicore supercomputers","volume":"79","author":"Wu","year":"2013","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2766196.2766200","article-title":"A vision for GPU-accelerated parallel computation on geo-spatial datasets","volume":"6","author":"Prasad","year":"2015","journal-title":"Sigspatial Spec."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1145\/1816038.1816021","article-title":"Debunking the 100X GPU vs. CPU myth:an evaluation of throughput computing on CPU and GPU","volume":"38","author":"Lee","year":"2010","journal-title":"Acm Sigarch Comput. Arch. News"},{"key":"ref_23","first-page":"437","article-title":"Research Progress and Review of High-Performance GIS","volume":"19","author":"Zuo","year":"2017","journal-title":"J. Geo-Inf. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1080\/17538947.2016.1144800","article-title":"PMODTRAN: A parallel implementation based on MODTRAN for massive remote sensing data processing","volume":"9","author":"Huang","year":"2016","journal-title":"Int. J. Digit. Earth"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Chatzimilioudis, G., Costa, C., Zeinalipouryazti, D., Lee, W.C., and Pitoura, E. (,  2016). Distributed in-memory processing of All K Nearest Neighbor queries. Proceedings of the IEEE International Conference on Data Engineering, Helsinki, Finland.","DOI":"10.1109\/ICDE.2016.7498389"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1254","DOI":"10.1016\/j.jpdc.2012.05.006","article-title":"A dynamic and adaptive load balancing strategy for parallel file system with large-scale I\/O servers","volume":"72","author":"Dong","year":"2012","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_27","first-page":"86","article-title":"Data Partition Method for Parallel Interpolation Based on Time Balance","volume":"29","author":"Qian","year":"2013","journal-title":"Geogr. Geo-Inf. Sci."},{"key":"ref_28","first-page":"55","article-title":"Dynamic Strip Partitioning Method Oriented Parallel Computing for Construction of Delaunay Triangulation","volume":"14","author":"Qi","year":"2012","journal-title":"J. Geo-Inf. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"141","DOI":"10.5194\/isprs-archives-XLII-4-W1-141-2016","article-title":"Evaluating Error of LiDar Derived DEM Interpolation for Vegetation Area","volume":"XLII-4\/W1","author":"Ismail","year":"2016","journal-title":"Int. Arch. Photogramm. Remote Sens. S"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1111\/j.1467-9671.2012.01347.x","article-title":"A Parallel Framework for Processing Massive Spatial Data with a Split-and-Merge Paradigm","volume":"16","author":"Guan","year":"2012","journal-title":"Trans. GIS"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.future.2013.12.039","article-title":"A case study of large-scale parallel I\/O analysis and optimization for numerical weather prediction system","volume":"37","author":"Zou","year":"2014","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1044","DOI":"10.1016\/j.cageo.2007.07.010","article-title":"An adaptive inverse-distance weighting spatial interpolation technique","volume":"34","author":"Lu","year":"2008","journal-title":"Comput. Geosci."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/10\/300\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:46:07Z","timestamp":1760208367000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/10\/300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,28]]},"references-count":32,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2017,10]]}},"alternative-id":["ijgi6100300"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6100300","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,28]]}}}