大数据计算的复杂性理论与算法研究进展

Research progress in the complexity theory and algorithms of big-data computation

最近几年,大数据研究风起云涌,取得了很多研究成果.尽管如此,大数据基础理论研究结果远未满足实际需要,大量的关键问题尚未解决,完整的基础理论尚待建立.本文旨在探索大数据的基础理论研究问题,综述大数据计算的复杂性理论和算法的研究进展.首先,给出大数据计算的严格定义.其次,讨论大数据计算的6个挑战和10个科学技术问题.然后,综述大数据计算的复杂性理论和算法设计的研究进展.最后,分析评述大数据计算的复杂性理论和算法设计的研究结果,并给出未来研究方向的思考.

With the explosive growth of available data in recent years, big-data research has attracted much attention from both academic and industrial researchers, and many significant advances have been achieved.Nevertheless, the fundamental research results are far from the actual needs, a number of key issues remain unresolved, a complete theory of big-data computation needs to be established, and considerable work remains to be accomplished. This paper focuses on the theoretical aspects of big-data research, especially the research progress of the complexity theory and algorithms of big-data computation. First, big-data computation is formally defined. Then, six challenges and ten research issues of big data are discussed. Next, the results of a survey on the research progress of complexity theory and algorithms of big-data computation are given. Finally, comments on the fundamental research results and the future theoretical research issues of big data are presented and discussed.