前言

信息技术的快速发展引发了数据规模的爆炸式增长，大数据已经几乎无处不在，引起了国内外学术界、工业界和政府部门的高度重视，被认为是一种新的非物质生产要素，蕴含着重大价值，并将导致科学研究的深刻变革，对国家的经济发展、社会发展、社会安全稳定、科学进展具有战略性、全局性和长远性的意义。

大数据的重大价值需要通过求解各种各样的以大数据为输入的计算问题（以下简称大数据计算问题）来发掘利用。大数据计算问题的求解算法（以下简称大数据算法或大数据计算方法）的设计与分析是大数据价值发掘利用的关键。正如算法是计算机科学技术的核心一样，大数据算法是大数据科学技术的核心，也是大数据的实际应用的重要基础。

虽然算法已经具有悠久的研究历史，研究成果层出不穷，促进了计算机的普遍应用，但是，由于目前计算资源的受限性和大数据的巨大规模，大数据问题的求解十分困难，多项式时间已经不再是大数据计算问题易解性的标准，多项式时间算法也不再是大数据计算问题的有效求解算法。传统计算复杂性理论和多项式时间算法面临着大数据计算问题的严峻挑战。大数据算法已经成为大数据应用的瓶颈。因此，大数据算法的设计与分析已经成为计算机科学技术的重要研究领域，吸引了大量的科技工作者。

从20世纪80年代开始，越来越多的计算机科技工作者开始从事大数据算法设计与分析的研究工作，也有一些计算机科学工作者开始从事大数据计算的复杂性理论研究。最近几年，随着大数据的迅速增长和大数据应用的风起云涌，人们对大数据算法设计与分析的研究兴趣有增无减，大有方兴未艾之势。目前，人们在大数据算法设计与分析方面已经取得了很多研究成果，为大数据应用奠定了初步基础，促进了大数据应用的进展。

遗憾的是，系统介绍大数据算法设计与分析的理论与技术的学术著作目前在国内外还很少见。为了满足国内外大数据计算理论研究者、大数据管理系统研制者、大数据应用系统开发者的需要，我撰写了这本书，试图为从事大数据研究与开发的科技工作者提供尽量系统全面的大数据算法设计与分析的知识，希望能够为大数据的基础研究、系统研制和应用开发尽绵薄之力。

在多年大数据算法研究过程中，我对大数据计算方法进行了长期探索，提出和验证了一些适用于大数据问题求解的计算方法，如亚线性时间计算方法、基于抽样的计算方法、基于压缩的计算方法、增量式计算方法、分布式并行计算方法等。本书以这些方法为主线，分为7章，系统地介绍5种主要大数据计算方法，包括大数据的亚线性时间计算方法、大数据的抽样计算方法、大数据的压缩计算方法、大数据的增量式计算方法和大数据的分布式并行计算方法。本书的结构如图1所示。第1章揭示了本书的撰写动机。第2章讨论大数据计算复杂性的几个基本理论问题和大数据计算问题的分类，为后面5章奠定理论基础。第3章描述了大数据计算的核心方法，与后面4章紧密相关。第4章、第5章、第6章和第7章则相互独立，介绍了其他4种重要的大数据计算方法。

图1本书的结构

下面简要地介绍各章的基本内容。

〖1〗〖1〗第1章讨论大数据、大数据算法和大数据计算的基本概念，介绍大数据计算面临的挑战和研究问题，综述大数据计算复杂性理论和高效算法两方面的研究进展，探讨大数据计算复杂性理论和高效大数据算法的研究问题。

第2章以随机存取图灵机(RATM)为大数据计算模型，介绍大数据计算复杂性的几个基本理论问题，包括RATM的定义和性能分析、基于RATM的大数据计算的易解性标准、基于RATM的大数据计算问题分类（如单纯易解类问题、伪易解类问题、可近似易解类问题等）以及类之间的关系、归约和大数据计算问题的完全性。第2章是其他各章的理论基础。

第3章介绍大数据的亚线性时间计算方法。这一章首先以两个单纯易解性大数据计算问题为例，讨论单纯易解性大数据计算问题的亚线性时间求解算法的设计与分析的原理和方法；然后以两个伪易解性大数据计算问题为例，讨论通过多项式时间预处理，实现伪易解性大数据计算问题的亚线性时间求解算法的设计与分析的原理和方法；最后以3个难解性大数据问题为例，讨论非易解性大数据计算问题的亚线性时间近似算法的设计与分析的原理和方法。

第4章介绍大数据的基于随机抽样的近似计算方法，包括(ε,δ)近似计算方法。这一章首先介绍抽样计算方法的基本思想和需要解决的关键问题；然后以多个不同的难解性大数据计算问题为例，讨论基于随机抽样的高效大数据算法的设计与分析的主要方法和基本原理。

第5章介绍大数据的压缩计算方法。这一章介绍的大数据计算方法是精确计算方法。这一章首先介绍压缩计算方法的基本思想、适用范围、需要解决的问题；然后介绍支持压缩计算的数据压缩方法；最后以不同的大数据计算问题为例，介绍基于压缩计算方法的大数据算法的设计与分析的主要方法和基本原理。

第6章介绍大数据的增量式计算方法。这一章首先介绍大数据增量式计算方法的基本概念和思想；然后以不同的大数据计算问题为例，介绍基于增量式计算方法的大数据算法的设计与分析的主要方法和基本原理，包括增量式流数据查询与挖掘算法。

第7章讨论如何在计算机机群或云计算环境下设计与分析求解大数据计算问题的分布式并行计算方法。这一章首先介绍并行计算系统和并行算法设计与分析的基本概念；然后介绍有效支持大数据分布式并行计算的大数据的分布式存储方法；最后以集合代数操作和关系代数操作为例，介绍求解大数据计算问题的分布式并行算法的设计与分析的主要方法和基本原理，特别是充分利用大数据分布式存储方法特点的分布式并行大数据算法的设计与分析的主要方法和基本原理。

本书不仅凝结着作者的心血，也凝结着所有对本书撰写给予鼓励、支持、关心和帮助的同志们的心血。

在本书问世之际，我特别感谢已经毕业并留在我身边工作的博士高宏教授、王宏志教授、邹兆年教授、程思瑶教授、张岩副教授、石胜飞副教授、张炜副教授、骆吉洲副教授、刘显敏副教授、韩希先副教授、苗东菁副教授、张开旗讲师，也特别感谢刚刚毕业和在读博士研究生石拓、朱同鑫、马恒钊、高翔宇、肖星星、李逸飞、巢泽敏、高天鹏、吕伯涵、韩帅、张楚涵等同学。这些已经毕业和在读的同学从20世纪90年代末开始陆续加入我的团队，每个人都陪伴我开展大数据科学技术研究至少5年，本书的主要内容都来自我们共同发表的学术论文，凝结着他们的心血。在本书的撰写过程中，很多同学也从多方面给予了我大力的支持和帮助。

我由衷地感谢国家自然科学基金委员会和国家科技部的支持。我的研究工作多次得到国家自然科学基金重点项目和面上项目的资助，也多次得到国家科技部863计划项目和973计划项目的资助，特别是本书得到了国家自然科学基金重点项目“大数据分析的计算理论与高效算法（项目批准号: 61832003）”和重大项目“基于超算的大数据分析处理基础算法与编程支撑环境（项目批准号: U1811461）”的直接资助。

我真诚地感谢我的妻子石敏教授。没有她的鼓励、支持、耐心和长期操劳，本书是难以完成的。我也要感谢我的女婿蔡志鹏教授和女儿李英姝教授的鼓励和鞭策，他们的鞭策对本书的尽快完成起到了重要作用。

由于作者水平有限，书中难免存在错误和不当之处，恳切希望同行和广大读者批评指正。

作者2022年1月