Research progress in the complexity theory and algorithms of big-data computation
Yingshu Li, Jianzhong Li · Scientia Sinica Informationis · 2016
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.