基于大数据和云环境的两类关键问题优化建模与优化方法研究

Cloud computing is an effective environment and important research direction for handling big data problems in the future. There will be more and more key big data application problems based on the cloud computing environment with the fast development of internet technology, and it is very necessary and urgent to develop new models and solution algorithms for these key application problems. The resource and task scheduling problems and the domain-specific deep web database sources quick discovery problem are two of the key application problems for the big data problems in the cloud computing environment. For the resource and task scheduling problems in the cloud computing and big data environment, In the existing studies, one of (at most two of) the task completion time, the efficiency, reliability and security of the task execution, the multi-task fairness, the data localization rate, the platform utiliation and reliability, and energy efficiency is (are) taken as the only objective(s) to set up the optimization models and design algorithms. These objectives are not considered and studied as a whole or in the integrated way. We shall consider these objectives in the integrated way, study the universal modeling methodology, and set up widely applicable optimization models and efficient algorithms. For the domain-specific deep web database sources quick discovery problems, the existing studies only considered to maximize coverage rate or harvest rate, and did not consider to minimize the ratio of the total number of the crawler grasped pages over the total number of domain-specific pages (we briefly called crawler load rate), while the later objective conflicts with the other two objectives. We shall consider these objectives in a unified way, and develop the universal optimization models and efficient algorithms which can satisfy the different requirements of the various domain-specific web database sources quick discovery problems.

云计算是处理大数据问题的一个有效环境和未来发展的重要方向。云计算环境下的大数据重要应用问题会随着互联网的快速发展越来越多，急需研究新的建模方法和求解算法。而资源和任务调度问题、特定领域WDB数据源的快速准确发现问题是其中两个关键应用问题。对第一个问题，已有研究主要以任务的完成时间、执行效率、安全性、可靠性、多任务的公平性、数据本地化率、和以平台资源利用率、平台可靠性和能源效用等某个（最多不超过两个）为优化目标设计模型和算法，没有综合考虑这些可能相互矛盾的目标。本项目从总体权衡这些目标，研究统一的建模方法论，建立可满足不同实际需要的新的优化模型及其高效算法。对第二个问题，已有研究只考虑表单覆盖率最大或收获率最大，没有考虑爬过页面总数与特定领域表单页面总数之比（简称爬虫负荷率）最小，而后者与前两者是矛盾的。本项目综合考虑这些目标，建立可满足各目标要求的新的统一优化模型并设计高效的求解算法。

.按计划研究了基于大数据和云环境的两类关键问题优化建模与优化方法，并超额完成了研究计划中的所有任务和所有预期的研究成果。发表SCI论文42篇，其中15篇为中科院一区或二区。主要成果包括：.首先，对大数据和云环境下的资源和任务调度问题，建立了多个单目标全局优化模型、双层优化模型和多目标优化模型，这些模型不仅可解决用户对大数据任务执行的高安全性、高可靠性和高效率等的不同需求，而且可解决云平台对任务执行的约束与限制，更考虑到了云平台自身对系统高利用率、低网络拥塞度和低能耗的需求。同时设计了这些模型的高效求解算法。实验表明，所设计的优化算法能够适应问题的需求，更快地找到问题的最优解或解集。另外，我们突破了传统的单趟任务调度模型，针对具有更高执行效率的多趟任务调度模型及多趟任务调度算法展开了深入研究，将当前已有模型中（N*M+2）维的超大规模优化模型重新建模为只有2维的低维优化模型，此模型是可真正用于云平台上进行大数据任务高效调度的模型。.其次，对大数据和云环境下特定领域深网数据源的发现问题，研究了数据挖掘高覆盖率、高收获率和低爬虫负荷率等目标的影响因素，建立了适应不同需求的多个单目标和多目标优化模型，并设计了模型的高效求解算法。另外，用本体的观点研究了深网数据源接口匹配问题，建立了只利用部分信息的本体元匹配优化模型和高效算法，相较于已有模型和算法，查准率提高了47%，还建立了查全率和查准率均达最优的本体元匹配多目标优化模型。该模型不仅可以用于深网数据源的发现问题，也可用于其他模式匹配问题。.最后，我们研究了云环境下大数据应用问题统一的优化建模方法，以及求解大规模全局优化模型、双层优化模型、多目标优化模型和超多目标优化模型的高效、可广泛使用的优化技术，并将这些理论和技术成功的应用于其他多个大数据应用问题。大量实验验证了我们所提模型的有效性和算法的高效性。