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

作者2022年1月