参数计算理论与技术在大数据环境下的应用

Based on the theory and algorithmic techniques in parameterized computation, the current project proposes a new computation model for bigdata computation. The new model has two relatively independent parameters, representing the input data size and describing the power of the computation resources, respectively, and provides a formal and convenient theoretical model for the study of bigdata computation under limited computation resources. Compared to the known computation models proposed in the literature, the new model fits better for the study of general bigdata computation. The project will be focused on new algorithmic techniques and computational complexity theory for bigdata computation. To meet the demands for bigdata computation in the fast development in national economy, we will study algorithms and computational complexity for a number of important computational problems in bigdata, such as data de-noising, data clustering, data reduction, and bioinformatics problems.

以参数计算理论与算法技术为基础，本项目提出一个新的大数据环境下的计算模型。新计算模型带有两个相对独立的参数分别表示数据量的大小和描述可用的计算资源。基于新的计算模型可以很方便地研究在大数据环境下如何使用有限资源有效地解决大数据中的计算问题。与目前已有的大数据算法计算模型相比较，新的计算模型更适合大数据环境下通用计算问题的研究。本项目将主要研究在这一新的计算模型下解决各类大数据计算问题所需要的新的算法技术以及相应的计算复杂性理论。通过对一系列大数据环境下的重要计算问题（如数据噪音处理问题、数据聚类分析问题、数据缩减问题和生物计算等问题）的研究，发展一套新的大数据环境下的算法技术和计算复杂性理论系统，以满足我国国民经济发展对大数据计算和应用的需求。

在本课题基金的支持下，四年来项目负责人陈建二教授带领其研究团队按照研究计划中的研究内容和技术路线展开了研究，并积极与国内外相关领域学者交流，取得了较好的研究成果。课题组对新提出的大数据计算模型给出了精确定义，并利用新的计算模型对大数据环境下的一些著名的组合优化问题，如带权和不带权的图匹配问题和边支配集的核心化问题，进行深入研究，得到了一系列世界上目前最好的结果，改进了以前这些问题的最好已知结果。课题组同时开辟了与大数据密切相关的核心化问题和基于云计算应用的并行2阶段流水线机器(multiple 2-stage flowshops)调度问题的研究。在2阶段流水线机器调度问题的研究中着重研究如何对带截止期的2阶段工作进行调度以取得最大收益。我们研究了问题的计算难解复杂度，并提出了多个快速近似算法，取得了一系列研究成果。项目组还开展了与本课题相关的网络安全问题和可满足问题(Satisfiability)的精确算法以及其在人工智能领域中的应用的研究，取得了成果。