信息技術(shù)的快速發(fā)展引發(fā)了數(shù)據(jù)規(guī)模的爆炸式增長，大數(shù)據(jù)已經(jīng)幾乎無處不在，引起了國內(nèi)外學(xué)術(shù)界、工業(yè)界和政府部門的高度重視，被認(rèn)為是一種新的非物質(zhì)生產(chǎn)要素，蘊(yùn)含著重大價值，并將導(dǎo)致科學(xué)研究的深刻變革，對國家的經(jīng)濟(jì)發(fā)展、社會發(fā)展、社會安全穩(wěn)定、科學(xué)進(jìn)展具有戰(zhàn)略性、全局性和長遠(yuǎn)性的意義。
大數(shù)據(jù)的重大價值需要通過求解各種各樣的以大數(shù)據(jù)為輸入的計算問題（以下簡稱大數(shù)據(jù)計算問題）來發(fā)掘利用。大數(shù)據(jù)計算問題的求解算法（以下簡稱大數(shù)據(jù)算法或大數(shù)據(jù)計算方法）的設(shè)計與分析是大數(shù)據(jù)價值發(fā)掘利用的關(guān)鍵。正如算法是計算機(jī)科學(xué)技術(shù)的核心一樣，大數(shù)據(jù)算法是大數(shù)據(jù)科學(xué)技術(shù)的核心，也是大數(shù)據(jù)的實(shí)際應(yīng)用的重要基礎(chǔ)。
雖然算法已經(jīng)具有悠久的研究歷史，研究成果層出不窮，促進(jìn)了計算機(jī)的普遍應(yīng)用，但是，由于目前計算資源的受限性和大數(shù)據(jù)的巨大規(guī)模，大數(shù)據(jù)問題的求解十分困難，多項(xiàng)式時間已經(jīng)不再是大數(shù)據(jù)計算問題易解性的標(biāo)準(zhǔn)，多項(xiàng)式時間算法也不再是大數(shù)據(jù)計算問題的有效求解算法。傳統(tǒng)計算復(fù)雜性理論和多項(xiàng)式時間算法面臨著大數(shù)據(jù)計算問題的嚴(yán)峻挑戰(zhàn)。大數(shù)據(jù)算法已經(jīng)成為大數(shù)據(jù)應(yīng)用的瓶頸。因此，大數(shù)據(jù)算法的設(shè)計與分析已經(jīng)成為計算機(jī)科學(xué)技術(shù)的重要研究領(lǐng)域，吸引了大量的科技工作者。
從20世紀(jì)80年代開始，越來越多的計算機(jī)科技工作者開始從事大數(shù)據(jù)算法設(shè)計與分析的研究工作，也有一些計算機(jī)科學(xué)工作者開始從事大數(shù)據(jù)計算的復(fù)雜性理論研究。最近幾年，隨著大數(shù)據(jù)的迅速增長和大數(shù)據(jù)應(yīng)用的風(fēng)起云涌，人們對大數(shù)據(jù)算法設(shè)計與分析的研究興趣有增無減，大有方興未艾之勢。目前，人們在大數(shù)據(jù)算法設(shè)計與分析方面已經(jīng)取得了很多研究成果，為大數(shù)據(jù)應(yīng)用奠定了初步基礎(chǔ)，促進(jìn)了大數(shù)據(jù)應(yīng)用的進(jìn)展。
遺憾的是，系統(tǒng)介紹大數(shù)據(jù)算法設(shè)計與分析的理論與技術(shù)的學(xué)術(shù)著作目前在國內(nèi)外還很少見。為了滿足國內(nèi)外大數(shù)據(jù)計算理論研究者、大數(shù)據(jù)管理系統(tǒng)研制者、大數(shù)據(jù)應(yīng)用系統(tǒng)開發(fā)者的需要，我撰寫了這本書，試圖為從事大數(shù)據(jù)研究與開發(fā)的科技工作者提供盡量系統(tǒng)全面的大數(shù)據(jù)算法設(shè)計與分析的知識，希望能夠?yàn)榇髷?shù)據(jù)的基礎(chǔ)研究、系統(tǒng)研制和應(yīng)用開發(fā)盡綿薄之力。
在多年大數(shù)據(jù)算法研究過程中，我對大數(shù)據(jù)計算方法進(jìn)行了長期探索，提出和驗(yàn)證了一些適用于大數(shù)據(jù)問題求解的計算方法，如亞線性時間計算方法、基于抽樣的計算方法、基于壓縮的計算方法、增量式計算方法、分布式并行計算方法等。本書以這些方法為主線，分為7章，系統(tǒng)地介紹5種主要大數(shù)據(jù)計算方法，包括大數(shù)據(jù)的亞線性時間計算方法、大數(shù)據(jù)的抽樣計算方法、大數(shù)據(jù)的壓縮計算方法、大數(shù)據(jù)的增量式計算方法和大數(shù)據(jù)的分布式并行計算方法。本書的結(jié)構(gòu)如圖1所示。第1章揭示了本書的撰寫動機(jī)。第2章討論大數(shù)據(jù)計算復(fù)雜性的幾個基本理論問題和大數(shù)據(jù)計算問題的分類，為后面5章奠定理論基礎(chǔ)。第3章描述了大數(shù)據(jù)計算的核心方法，與后面4章緊密相關(guān)。第4章、第5章、第6章和第7章則相互獨(dú)立，介紹了其他4種重要的大數(shù)據(jù)計算方法。
圖1本書的結(jié)構(gòu)
下面簡要地介紹各章的基本內(nèi)容。
〖1〗〖1〗第1章討論大數(shù)據(jù)、大數(shù)據(jù)算法和大數(shù)據(jù)計算的基本概念，介紹大數(shù)據(jù)計算面臨的挑戰(zhàn)和研究問題，綜述大數(shù)據(jù)計算復(fù)雜性理論和高效算法兩方面的研究進(jìn)展，探討大數(shù)據(jù)計算復(fù)雜性理論和高效大數(shù)據(jù)算法的研究問題。
第2章以隨機(jī)存取圖靈機(jī)(RATM)為大數(shù)據(jù)計算模型，介紹大數(shù)據(jù)計算復(fù)雜性的幾個基本理論問題，包括RATM的定義和性能分析、基于RATM的大數(shù)據(jù)計算的易解性標(biāo)準(zhǔn)、基于RATM的大數(shù)據(jù)計算問題分類（如單純易解類問題、偽易解類問題、可近似易解類問題等）以及類之間的關(guān)系、歸約和大數(shù)據(jù)計算問題的完全性。第2章是其他各章的理論基礎(chǔ)。
第3章介紹大數(shù)據(jù)的亞線性時間計算方法。這一章首先以兩個單純易解性大數(shù)據(jù)計算問題為例，討論單純易解性大數(shù)據(jù)計算問題的亞線性時間求解算法的設(shè)計與分析的原理和方法；然后以兩個偽易解性大數(shù)據(jù)計算問題為例，討論通過多項(xiàng)式時間預(yù)處理，實(shí)現(xiàn)偽易解性大數(shù)據(jù)計算問題的亞線性時間求解算法的設(shè)計與分析的原理和方法；最后以3個難解性大數(shù)據(jù)問題為例，討論非易解性大數(shù)據(jù)計算問題的亞線性時間近似算法的設(shè)計與分析的原理和方法。
第4章介紹大數(shù)據(jù)的基于隨機(jī)抽樣的近似計算方法，包括(ε,)�步�似計算方法。這一章首先介紹抽樣計算方法的基本思想和需要解決的關(guān)鍵問題；然后以多個不同的難解性大數(shù)據(jù)計算問題為例，討論基于隨機(jī)抽樣的高效大數(shù)據(jù)算法的設(shè)計與分析的主要方法和基本原理。
第5章介紹大數(shù)據(jù)的壓縮計算方法。這一章介紹的大數(shù)據(jù)計算方法是精確計算方法。這一章首先介紹壓縮計算方法的基本思想、適用范圍、需要解決的問題；然后介紹支持壓縮計算的數(shù)據(jù)壓縮方法；最后以不同的大數(shù)據(jù)計算問題為例，介紹基于壓縮計算方法的大數(shù)據(jù)算法的設(shè)計與分析的主要方法和基本原理。
第6章介紹大數(shù)據(jù)的增量式計算方法。這一章首先介紹大數(shù)據(jù)增量式計算方法的基本概念和思想；然后以不同的大數(shù)據(jù)計算問題為例，介紹基于增量式計算方法的大數(shù)據(jù)算法的設(shè)計與分析的主要方法和基本原理，包括增量式流數(shù)據(jù)查詢與挖掘算法。
第7章討論如何在計算機(jī)機(jī)群或云計算環(huán)境下設(shè)計與分析求解大數(shù)據(jù)計算問題的分布式并行計算方法。這一章首先介紹并行計算系統(tǒng)和并行算法設(shè)計與分析的基本概念；然后介紹有效支持大數(shù)據(jù)分布式并行計算的大數(shù)據(jù)的分布式存儲方法；最后以集合代數(shù)操作和關(guān)系代數(shù)操作為例，介紹求解大數(shù)據(jù)計算問題的分布式并行算法的設(shè)計與分析的主要方法和基本原理，特別是充分利用大數(shù)據(jù)分布式存儲方法特點(diǎn)的分布式并行大數(shù)據(jù)算法的設(shè)計與分析的主要方法和基本原理。
本書不僅凝結(jié)著作者的心血，也凝結(jié)著所有對本書撰寫給予鼓勵、支持、關(guān)心和幫助的同志們的心血。
在本書問世之際，我特別感謝已經(jīng)畢業(yè)并留在我身邊工作的博士高宏教授、王宏志教授、鄒兆年教授、程思瑤教授、張巖副教授、石勝飛副教授、張煒副教授、駱吉洲副教授、劉顯敏副教授、韓希先副教授、苗東菁副教授、張開旗講師，也特別感謝剛剛畢業(yè)和在讀博士研究生石拓、朱同鑫、馬恒釗、高翔宇、肖星星、李逸飛、巢澤敏、高天鵬、呂伯涵、韓帥、張楚涵等同學(xué)。這些已經(jīng)畢業(yè)和在讀的同學(xué)從20世紀(jì)90年代末開始陸續(xù)加入我的團(tuán)隊(duì)，每個人都陪伴我開展大數(shù)據(jù)科學(xué)技術(shù)研究至少5年，本書的主要內(nèi)容都來自我們共同發(fā)表的學(xué)術(shù)論文，凝結(jié)著他們的心血。在本書的撰寫過程中，很多同學(xué)也從多方面給予了我大力的支持和幫助。
我由衷地感謝國家自然科學(xué)基金委員會和國家科技部的支持。我的研究工作多次得到國家自然科學(xué)基金重點(diǎn)項(xiàng)目和面上項(xiàng)目的資助，也多次得到國家科技部863計劃項(xiàng)目和973計劃項(xiàng)目的資助，特別是本書得到了國家自然科學(xué)基金重點(diǎn)項(xiàng)目大數(shù)據(jù)分析的計算理論與高效算法（項(xiàng)目批準(zhǔn)號: 61832003）和重大項(xiàng)目基于超算的大數(shù)據(jù)分析處理基礎(chǔ)算法與編程支撐環(huán)境（項(xiàng)目批準(zhǔn)號: U1811461）的直接資助。
我真誠地感謝我的妻子石敏教授。沒有她的鼓勵、支持、耐心和長期操勞，本書是難以完成的。我也要感謝我的女婿蔡志鵬教授和女兒李英姝教授的鼓勵和鞭策，他們的鞭策對本書的盡快完成起到了重要作用。
由于作者水平有限，書中難免存在錯誤和不當(dāng)之處，懇切希望同行和廣大讀者批評指正。

作者2022年1月