{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:16:56Z","timestamp":1761401816938,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2016,8,10]],"date-time":"2016-08-10T00:00:00Z","timestamp":1470787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Spatial data processing often requires massive datasets, and the task\/data scheduling efficiency of these applications has an impact on the overall processing performance. Among the existing scheduling strategies, hypergraph-based algorithms capture the data sharing pattern in a global way and significantly reduce total communication volume. Due to heterogeneous processing platforms, however, single hypergraph partitioning for later scheduling may be not optimal. Moreover, these scheduling algorithms neglect the overlap between task execution and data transfer that could further decrease execution time. In order to address these problems, an extended hypergraph-based task-scheduling algorithm, named Hypergraph+, is proposed for massive spatial data processing. Hypergraph+ improves upon current hypergraph scheduling algorithms in two ways: (1) It takes platform heterogeneity into consideration offering a metric function to evaluate the partitioning quality in order to derive the best task\/file schedule; and (2) It can maximize the overlap between communication and computation. The GridSim toolkit was used to evaluate Hypergraph+ in an IDW spatial interpolation application on heterogeneous master-slave platforms. Experiments illustrate that the proposed Hypergraph+ algorithm achieves on average a 43% smaller makespan than the original hypergraph scheduling algorithm but still preserves high scheduling efficiency.<\/jats:p>","DOI":"10.3390\/ijgi5080141","type":"journal-article","created":{"date-parts":[[2016,8,10]],"date-time":"2016-08-10T10:14:10Z","timestamp":1470824050000},"page":"141","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Hypergraph+: An Improved Hypergraph-Based Task-Scheduling Algorithm for Massive Spatial Data Processing on Master-Slave Platforms"],"prefix":"10.3390","volume":"5","author":[{"given":"Bo","family":"Cheng","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, China"},{"name":"Collaborative Innovation Center of Geospatial Technology, 129 Luoyu Road, Wuhan 430079, China"}]},{"given":"Xuefeng","family":"Guan","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, China"},{"name":"Collaborative Innovation Center of Geospatial Technology, 129 Luoyu Road, Wuhan 430079, China"}]},{"given":"Huayi","family":"Wu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, China"},{"name":"Collaborative Innovation Center of Geospatial Technology, 129 Luoyu Road, Wuhan 430079, China"}]},{"given":"Rui","family":"Li","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129 Luoyu Road, Wuhan 430079, China"},{"name":"Collaborative Innovation Center of Geospatial Technology, 129 Luoyu Road, Wuhan 430079, China"}]}],"member":"1968","published-online":{"date-parts":[[2016,8,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Liu, Y., Chen, B., Yu, H., Zhao, Y., Huang, Z., and Fang, Y. (2011, January 24\u201326). Applying GPU and POSIX thread technologies in massive remote sensing image data processing. Proceedings of the 19th International Conference on Geoinformatics 2011, Shanghai, China.","DOI":"10.1109\/GeoInformatics.2011.5980671"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Song, W., Yue, S., Wang, L., Zhang, W., and Liu, D. (2011, January 7\u20139). Task scheduling of massive spatial data processing across distributed data centers: What\u2019s new?. Proceedings of the 2011 IEEE 17th International Conference on Parallel and Distributed Systems, Tainan, Taiwan.","DOI":"10.1109\/ICPADS.2011.134"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1080\/19475683.2014.938774","article-title":"The challenges of image segmentation in big remotely sensed imagery data","volume":"20","author":"Xing","year":"2014","journal-title":"Ann. GIS"},{"key":"ref_4","first-page":"1175","article-title":"Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing","volume":"14","author":"Buyya","year":"2002","journal-title":"CCPE"},{"key":"ref_5","unstructured":"Maheswaran, M., Ali, S., Siegal, H.J., Hensgen, D., and Freund, R.F. (1999, January 12). Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems. Proceedings of the 8th Heterogeneous Computing Workshop (HCW\u201999), San Juan, Puerto Rico."},{"key":"ref_6","unstructured":"Casanova, H., Legrand, A., Zagorodnov, D., and Berman, F. (2000, January 1). Heuristics for scheduling parameter sweep applications in grid environments. Proceedings of the 9th Heterogeneous Computing Workshop (HCW\u201900), Cancun, Mexico."},{"key":"ref_7","unstructured":"Khanna, G., Vydyanathan, N., Kurc, T., Catalyurek, U., Wyckoff, P., Saltz, J., and Sadayappan, P. (2005, January 9\u201312). A hypergraph partitioning based approach for scheduling of tasks with batch-shared I\/O. Proceedings of the 5th International Symposium on Cluster Computing and the Grid (CCGrid 2005), Cardiff, UK."},{"key":"ref_8","unstructured":"Berge, C. (1973). Graphs and Hypergraphs, North-Holland Publishing Company."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1155\/2000\/19436","article-title":"Multilevel k-way hypergraph partitioning","volume":"11","author":"Karypis","year":"2000","journal-title":"VLSI Des."},{"key":"ref_10","unstructured":"Cataly\u00fcrek, U.V., and Aykanat, C. (2011). Encyclopedia of Parallel Computing 2011, Springer Science & Business Media."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Trifunovic, A., and Knottenbelt, W.J. (2004, January 27\u201329). Parkway 2.0: A parallel multilevel hypergraph partitioning tool. Proceedings of 19th International Symposium on Computer and Information Sciences (ISCIS 2004), Kemer-Antalya, Turkey.","DOI":"10.1007\/978-3-540-30182-0_79"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-9260(95)00008-4","article-title":"Recent directions in netlist partitioning: A survey","volume":"19","author":"Alpert","year":"1995","journal-title":"Integr. VLSI J."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/92.748202","article-title":"Multilevel hypergraph partitioning: Applications in VLSI domain","volume":"7","author":"Karypis","year":"1999","journal-title":"IEEE Trans. Very Large Scale Integr. (VLSI) Syst."},{"key":"ref_14","unstructured":"Mobasher, B., Jain, N., Han, E.H., and Srivastava, J. (1996). Web Mining: Pattern Discovery from World Wide Web Transactions, Department of Computer Science, University of Minnesota. Technical Report TR96-050."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.is.2007.04.001","article-title":"Clustering spatial networks for aggregate query processing: A hypergraph approach","volume":"33","author":"Demir","year":"2008","journal-title":"Inf. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1109\/71.780863","article-title":"Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication","volume":"10","author":"Aykanat","year":"1999","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TPDS.2007.253277","article-title":"Hypergraph-partitioning-based remapping models for image-space-parallel direct volume rendering of unstructured grids","volume":"18","author":"Cambazoglu","year":"2007","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1109\/TPDS.2006.105","article-title":"Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master-slave environments","volume":"17","author":"Kaya","year":"2006","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.ipm.2015.08.003","article-title":"Argumentation semantics and graph properties","volume":"52","author":"Doumbouya","year":"2016","journal-title":"Inf. Process. Manag."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.irbm.2014.04.001","article-title":"Conceptual graph operations for formal visual reasoning in the medical domain","volume":"35","author":"Foguem","year":"2014","journal-title":"IRBM"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1016\/j.aei.2012.06.006","article-title":"Knowledge-based support in Non-Destructive Testing for health monitoring of aircraft structures","volume":"26","year":"2012","journal-title":"Adv. Eng. Inf."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/j.future.2008.09.006","article-title":"A new paradigm: Data-aware scheduling in grid computing","volume":"25","author":"Kosar","year":"2009","journal-title":"Futur. Gener. Comput. Syst."},{"key":"ref_23","first-page":"459","article-title":"A survey on data-centric and data-aware techniques for large scale infrastructures","volume":"10","author":"Carretero","year":"2016","journal-title":"World Acad. Sci. Eng. Technol. Int. J. Comput. Electr. Auto. Cont. Inf. Eng."},{"key":"ref_24","unstructured":"Mohamed, H.H., and Epema, D.H. (2004, January 20\u201323). An evaluation of the close-to-files processor and data co-allocation policy in multiclusters. Proceedings of the IEEE International Conference on Cluster Computing 2004, Los Alamitos, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.jpdc.2016.04.008","article-title":"Data-aware task scheduling for all-to-all comparison problems in heterogeneous distributed systems","volume":"93","author":"Zhang","year":"2016","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Szmajduch, M., and Ko\u0142odziej, J. (2015, January 26\u201329). Data-aware scheduling in massive heterogeneous systems. Proceedings of the 29th European Conference on Modeling and Simulation ECMS 2015, Varna, Bulgaria.","DOI":"10.7148\/2015-0601"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1016\/j.jpdc.2011.01.002","article-title":"Scalability limits of Bag-of-Tasks applications running on hierarchical platforms","volume":"71","author":"Senger","year":"2011","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_28","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_29","unstructured":"Muthuvelu, N., Liu, J., Soe, N.L., Venugopal, S., Sulistio, A., and Buyya, R. (February, January 30). A dynamic job grouping-based scheduling for deploying applications with fine-grained tasks on global grids. Proceedings of the 3rd Australasian workshop on Grid computing and e-Research (AusGrid 2005), Newcastle, Australia."},{"key":"ref_30","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_31","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/j.jpdc.2007.11.002","article-title":"Parallel multilevel algorithms for hypergraph partitioning","volume":"68","author":"Knottenbelt","year":"2008","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/8\/141\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:28:06Z","timestamp":1760210886000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/8\/141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,10]]},"references-count":31,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2016,8]]}},"alternative-id":["ijgi5080141"],"URL":"https:\/\/doi.org\/10.3390\/ijgi5080141","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2016,8,10]]}}}