大數(shù)據(jù)計(jì)算理論基礎(chǔ)201405陳國(guó)良

大數(shù)據(jù)計(jì)算理論基礎(chǔ)

ComputingTheory

FoundationsofBigData2014年5月陳國(guó)良，陸克中，毛睿深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院2摘要：

大數(shù)據(jù)是當(dāng)前IT信息技術(shù)研究和應(yīng)用的熱點(diǎn)。但是，目前的研究多集中于系統(tǒng)和應(yīng)用層面，理論基礎(chǔ)方面的探討相對(duì)較少。本文從計(jì)算機(jī)科學(xué)講起，以計(jì)算復(fù)雜性理論為基礎(chǔ)，著重研究大數(shù)據(jù)的計(jì)算復(fù)雜性（ComputationalComplexity）和大數(shù)據(jù)本身的復(fù)雜性（DataComplexity）：前者包括大數(shù)據(jù)統(tǒng)一化抽象表示；大數(shù)據(jù)劃分技術(shù)；大數(shù)據(jù)NC類(lèi)計(jì)算理論；大數(shù)據(jù)計(jì)算模式等。后者包括大數(shù)據(jù)復(fù)雜性表示；大數(shù)據(jù)復(fù)雜性度量；大數(shù)據(jù)復(fù)雜性模型等。最后，根據(jù)大數(shù)據(jù)的4V特性，提出大數(shù)據(jù)處理應(yīng)對(duì)策略和變革思維方法研究大數(shù)據(jù)。3目錄計(jì)算機(jī)科學(xué)與計(jì)算問(wèn)題分類(lèi)計(jì)算機(jī)科學(xué)的經(jīng)典定義計(jì)算機(jī)科學(xué)定義的數(shù)學(xué)解釋計(jì)算機(jī)科學(xué)的歷史演變計(jì)算問(wèn)題分類(lèi)計(jì)算理論可計(jì)算性與計(jì)算復(fù)雜性圖靈計(jì)算模型串行復(fù)雜計(jì)算類(lèi)：P，NP，NPC，NPH并行復(fù)雜計(jì)算類(lèi)：NC，PC歸約大數(shù)據(jù)可計(jì)算性可(能)解與不可(用)解問(wèn)題大數(shù)據(jù)可(能)解與不可(用)解問(wèn)題數(shù)據(jù)庫(kù)查詢類(lèi)的可(能)解與不可(用)解問(wèn)題度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路距離和度量的概念數(shù)據(jù)的度量空間表示度量空間舉例支撐點(diǎn)空間：度量空間的坐標(biāo)化度量空間的坐標(biāo)化支撐點(diǎn)空間的定義舉例完全支撐點(diǎn)空間數(shù)據(jù)的劃分技術(shù)超平面劃分有利點(diǎn)劃分包絡(luò)球劃分大數(shù)據(jù)NC計(jì)算理論NCi類(lèi)的電路定義NCi類(lèi)的層次大數(shù)據(jù)NC-類(lèi)計(jì)算大數(shù)據(jù)計(jì)算模式基于MR的流計(jì)算流計(jì)算實(shí)例研究：Storm流計(jì)算增量計(jì)算大數(shù)據(jù)的復(fù)雜性大數(shù)據(jù)復(fù)雜性表示大數(shù)據(jù)復(fù)雜性度量大計(jì)算復(fù)雜性模型結(jié)論大數(shù)據(jù)處理應(yīng)對(duì)策略變革思維研究大數(shù)據(jù)1、計(jì)算機(jī)科學(xué)與計(jì)算問(wèn)題分類(lèi)

41、計(jì)算機(jī)科學(xué)與計(jì)算問(wèn)題分類(lèi)計(jì)算機(jī)科學(xué)的歷史演變計(jì)算機(jī)科學(xué)的形式化研究起源于數(shù)學(xué)的基礎(chǔ)研究：Cantor的集合論與Russell悖論：數(shù)學(xué)家們?cè)诩险撝邪l(fā)現(xiàn)了邏輯矛盾LetR={x|x?x}thenR∈R?R?RHilbert綱領(lǐng)：即在通用的形式邏輯系統(tǒng)中可以機(jī)械地判定任何給定命題的真?zhèn)危ㄍ陚湫裕?，證明每一形式系統(tǒng)的相容性，從而導(dǎo)出全部數(shù)學(xué)的相容性。G?del提出了形式系統(tǒng)的不完備性，它不能窮舉全部數(shù)學(xué)命題，任何足夠強(qiáng)的相容形式系統(tǒng)中均存在著該系統(tǒng)中所不能判定真?zhèn)蔚拿}。Hilbert綱領(lǐng)的失敗啟發(fā)人們不要花費(fèi)大量精力去證明那些不能判定的問(wèn)題，而應(yīng)集中精力研究“可計(jì)算求解性”問(wèn)題。在此思想指引下，A.M.Turing從計(jì)算一個(gè)數(shù)的一般過(guò)程入手，將可計(jì)算性概念與機(jī)械程序的執(zhí)行過(guò)程統(tǒng)一起來(lái)，此即有名的圖靈計(jì)算模型。51、計(jì)算機(jī)科學(xué)與計(jì)算問(wèn)題分類(lèi)計(jì)算問(wèn)題分類(lèi)6計(jì)算問(wèn)題不可判定問(wèn)題可判定問(wèn)題難解(不可能)解問(wèn)題易解(可解，多項(xiàng)式時(shí)間)問(wèn)題不可近似問(wèn)題可近似問(wèn)題大數(shù)據(jù)可解(BD-Tractable)問(wèn)題大數(shù)據(jù)不可解(BD-Intractable)問(wèn)題大數(shù)據(jù)不可近似問(wèn)題大數(shù)據(jù)可近似問(wèn)題2、計(jì)算理論（Theoryofcomputation）可計(jì)算性與計(jì)算復(fù)雜性可計(jì)算性：對(duì)于一個(gè)問(wèn)題，如果存在一個(gè)機(jī)械過(guò)程，對(duì)給定的輸入，能夠在有限步內(nèi)給出結(jié)果，則稱此問(wèn)題是可計(jì)算的。所謂機(jī)械的過(guò)程，系指在描述計(jì)算的某種設(shè)備上，實(shí)施該計(jì)算過(guò)程，而給出計(jì)算結(jié)果?？捎?jì)算性特征：確定性：對(duì)相同的初始輸入產(chǎn)生相同的輸出。有限性：在有限設(shè)備上能在有限時(shí)間內(nèi)求解。構(gòu)造性：每一計(jì)算過(guò)程的執(zhí)行都是“機(jī)械的”或“構(gòu)造性的”。數(shù)學(xué)描述性：計(jì)算的過(guò)程可以用嚴(yán)格的數(shù)學(xué)進(jìn)行描述。停機(jī)問(wèn)題：對(duì)于任意的圖靈機(jī)和輸入，是否存在一個(gè)算法，用于判定圖靈機(jī)在接收初始輸入后可到達(dá)停機(jī)狀態(tài)。若能找到此算法，停機(jī)問(wèn)題可解，否則不可解。計(jì)算復(fù)雜性：用數(shù)學(xué)方法研究各類(lèi)問(wèn)題計(jì)算的復(fù)雜性質(zhì)。也可理解為利用計(jì)算機(jī)求解問(wèn)題的難易程度。算法復(fù)雜性：算法復(fù)雜性是對(duì)算法效率的度量，系指運(yùn)行算法所耗費(fèi)的時(shí)間和空間（存儲(chǔ)量）。72、計(jì)算理論（Theoryofcomputation）圖靈計(jì)算模型將可計(jì)算性概念與機(jī)械程序的執(zhí)行過(guò)程統(tǒng)一起來(lái)，確認(rèn)任一機(jī)械執(zhí)行過(guò)程均可在一臺(tái)機(jī)器（即圖靈機(jī)）上實(shí)現(xiàn)。圖靈機(jī)：圖靈機(jī)就是對(duì)一條兩端可無(wú)限延長(zhǎng)的紙帶上的0和1執(zhí)行操作，一步一步地改變紙帶上的0或1值，經(jīng)此有限步驟最終得到一個(gè)滿足預(yù)先要求的符號(hào)串變換。圖靈機(jī)的作用：圖靈的研究成果認(rèn)為“可計(jì)算性＝圖靈可計(jì)算性”，即任何在圖靈機(jī)上可求解的問(wèn)題都是可計(jì)算的！82、計(jì)算理論（Theoryofcomputation）串行計(jì)算類(lèi)：P，NP，NPC，NPHP類(lèi)問(wèn)題：在確定圖靈機(jī)上多項(xiàng)式（Polynomial）時(shí)間內(nèi)可求解的一類(lèi)問(wèn)題。NP類(lèi)問(wèn)題：在非確定圖靈機(jī)上多項(xiàng)式時(shí)間內(nèi)可求解的一類(lèi)問(wèn)題（所有NP問(wèn)題均必須在有限步內(nèi)是可判定的）。NPC問(wèn)題：對(duì)于L∈NP的問(wèn)題，且NP類(lèi)中的每一個(gè)L’均可在多項(xiàng)式時(shí)間內(nèi)歸約（轉(zhuǎn)換）到L，L’≤PL，則稱L為NPC（NP完全）的（第一個(gè)被證明是NPC問(wèn)題的是布爾滿足性問(wèn)題：BooleanSatisfiabilityProblem，SAT）。NPH（難）問(wèn)題：一個(gè)問(wèn)題H稱為NP難的，當(dāng)且僅當(dāng)存在著一個(gè)NPC問(wèn)題L，L可在多項(xiàng)式時(shí)間內(nèi)圖靈歸約（Turing-Reduction）到H。簡(jiǎn)記之為：L(NPC)

≤T

H(NPH)

（例如判定停機(jī)問(wèn)題是NPH問(wèn)題）。9NPHNPCNPP

NPPNPC當(dāng)P≠NP時(shí)，NPH問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)求解。當(dāng)P≠NP時(shí)，NPC問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)求解。注：①所有NPC問(wèn)題均能在多項(xiàng)式時(shí)間內(nèi)歸約到NPH而求解之。

②NPC中的每個(gè)元素均必須是NP中的元素。

③NPH問(wèn)題中不一定必須是NP中的元素。2、計(jì)算理論（Theoryofcomputation）并行計(jì)算類(lèi)：NC，PCNC-類(lèi)問(wèn)題：在PRAM模型上，使用多項(xiàng)式數(shù)目（Polynomialsize）的處理器，運(yùn)行在對(duì)數(shù)多項(xiàng)式時(shí)間（Polylogtime）內(nèi)的一類(lèi)問(wèn)題。（此類(lèi)問(wèn)題包括整數(shù)加法、乘法、除法，矩陣乘，行列式，找最大匹配（RNC問(wèn)題）等）。NC-算法：在PRAM模型上，一個(gè)求解問(wèn)題的算法使用了多項(xiàng)式數(shù)目的處理器，花費(fèi)了對(duì)數(shù)多項(xiàng)式時(shí)間，則稱此算法為NC-算法。NC-歸約形式定義：對(duì)于問(wèn)題L1和L2，如果存在一個(gè)NC-算法，可將L1的求解轉(zhuǎn)換成L2的求解，則稱L1可NC-歸約到L2，簡(jiǎn)記為L(zhǎng)1

≤NCL2。P完全（PC）問(wèn)題：對(duì)于L∈P，且P中的任意L’均可NC-歸約到L，則稱L是P完全的。10PNCPC

當(dāng)P≠NC時(shí)，PC問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)求解。2、計(jì)算理論（Theoryofcomputation）

113、大數(shù)據(jù)可計(jì)算性可（能）解（Tractable）與不可（用）解（Intractable）可（能）解（Tractable:meaning“easilymanaged”）問(wèn)題：經(jīng)典定義是在多項(xiàng)式時(shí)間內(nèi)可以解決的問(wèn)題。不可（用）解（Intractable）問(wèn)題：系指理論上能夠解（在無(wú)限長(zhǎng)時(shí)間內(nèi)），但實(shí)際上求解時(shí)間太長(zhǎng)而無(wú)法用的問(wèn)題。因此缺乏多項(xiàng)式時(shí)間解的問(wèn)題被視為不可（用）解的問(wèn)題。完全問(wèn)題不可解性：在P≠NP時(shí)，NPC問(wèn)題是不可（用）解的問(wèn)題；在P≠NC時(shí)，PC問(wèn)題是不可（用）解的問(wèn)題。大數(shù)據(jù)可（能）解與不可（用）解問(wèn)題在大數(shù)據(jù)時(shí)有些問(wèn)題是可（能）解的，例如布爾選擇查詢（在數(shù)據(jù)集D中，是否存在某一列的元組值為指定值，在B+樹(shù)[1]索引上可在O(log(|D|))時(shí)間內(nèi)解決）；但很多問(wèn)題是不可（能）解的，例如圖的寬度優(yōu)先搜索[2]（是P完全的）。在大數(shù)據(jù)時(shí)，傳統(tǒng)的可（能）解問(wèn)題，可能成為不可（用）解問(wèn)題：例如采用速度可達(dá)6Gbps的快速硬盤(pán)，線性掃描1EB（E=1018字節(jié)）的數(shù)據(jù)，這本是線性復(fù)雜度的可（能）解問(wèn)題，但實(shí)際需要長(zhǎng)達(dá)5.28年時(shí)間，這就變成了不可（用）解問(wèn)題了。12注1：B+樹(shù)是B樹(shù)的變形，關(guān)鍵字與數(shù)據(jù)值（鍵/值）成對(duì)存儲(chǔ)在樹(shù)的同一節(jié)點(diǎn)中，其中所有數(shù)據(jù)值存在樹(shù)的葉節(jié)點(diǎn)中，只將關(guān)鍵字與子女節(jié)點(diǎn)的指針存在樹(shù)的內(nèi)節(jié)點(diǎn)中。注2：寬度優(yōu)先搜索（BFS：Breadth-First-Search）從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷其所有子節(jié)點(diǎn)，這些子節(jié)點(diǎn)被加入一個(gè)先進(jìn)先出FIFO的隊(duì)列中。然后從FIFO隊(duì)列中取出先進(jìn)入的子節(jié)點(diǎn)，重復(fù)上述寬度遍歷過(guò)程，直到所有節(jié)點(diǎn)均被訪問(wèn)過(guò)。BFS問(wèn)題是個(gè)P完全問(wèn)題。

3、大數(shù)據(jù)可計(jì)算性13PTIME(ΠTQ)BD-IntractableBD-Tractable(ΠTQ0)P(ΠTQ)NCPCΠTQ0大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路類(lèi)型和距離函數(shù)：這是數(shù)據(jù)表示的兩個(gè)基本參數(shù)，其中類(lèi)型可以是一維數(shù)據(jù)、多維數(shù)據(jù)、字符串、圖片等；對(duì)于復(fù)雜數(shù)據(jù)，除了精確匹配以外，更多要以距離衡量彼此的相似性。多維數(shù)據(jù)作為統(tǒng)一化抽象表示的局限性：使用多維數(shù)據(jù)作為統(tǒng)一表示時(shí)，數(shù)據(jù)本身必須能表示成特征向量（FeatureVector），且數(shù)據(jù)間的相似性用特征向量的歐式距離等衡量。但對(duì)有些數(shù)據(jù)和應(yīng)用無(wú)法滿足上述條件，例如文本字符串往往使用編輯距離，蛋白質(zhì)序列只能使用比對(duì)（Alignment）距離，圖片等只能使用Hausdorff距離等等。統(tǒng)一化抽象表示：針對(duì)上述情況，可將Variety數(shù)據(jù)抽象成統(tǒng)一的數(shù)據(jù)類(lèi)型，將Variety距離抽象成統(tǒng)一的距離函數(shù)，此即下述的度量空間表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示14

4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示15度量空間拓?fù)渑c拓?fù)淇臻g：如果非空集合X的子集族τ，它滿足以下條件：?和X在τ中；τ的任意子族之元素的“并”（∪）在τ中；τ的任意子族之元素的“交”（∩）在τ中。則稱τ為X上的一個(gè)拓?fù)洌═opology），偶對(duì)（X,τ）稱為X上的一個(gè)拓?fù)淇臻g（TopologySpace）。度量與度量空間：設(shè)X為非空集合，d:X×X

→R，(x,y)→d(x,y)為映射，如果?x,y,z∈X滿足：

d(x,y)=d(y,x)（對(duì)稱性）；

d(x,y)≥0和d(x,y)=0iffx=y（半正定性）；

d(x,z)≤d(x,y)+d(y,z)（三角不等式）。則稱d為X上的一個(gè)度量（距離），偶對(duì)（X,d）為度量空間，d(x,y)稱為是x與y間的距離。注：度量空間是一類(lèi)特殊的拓?fù)淇臻g；而n維歐氏空間是一類(lèi)特殊的度量空間。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示16度量空間舉例字符串：數(shù)據(jù)類(lèi)型可用文本類(lèi)型（如ASCII碼等）數(shù)組表示；其距離函數(shù)可用編輯距離（EditDistance）表示：即將兩個(gè)字符串相互轉(zhuǎn)換所需的編輯動(dòng)作（插入、刪除、替換等）的總開(kāi)銷(xiāo)。蛋白質(zhì)序列：數(shù)據(jù)類(lèi)型可用字節(jié)（蛋白質(zhì)的序列由20種氨基酸表示，每一種氨基酸用一個(gè)字節(jié)表示）數(shù)組表示；其距離函數(shù)可用全局比對(duì)（GlobalAlignment）表示：即加權(quán)的編輯距離。基因序列：數(shù)據(jù)類(lèi)型可用字節(jié)（基因序列由4種堿基表示，每一種堿基用一個(gè)字節(jié)表示）數(shù)組表示；其距離函數(shù)可用海明距離（HammingDistance：對(duì)應(yīng)位不相同的數(shù)目）表示。圖片：數(shù)據(jù)類(lèi)型可用長(zhǎng)度為66的實(shí)數(shù)數(shù)組表示，用以表征圖片的結(jié)構(gòu)、紋理、顏色等特征；其距離函數(shù)可用“結(jié)構(gòu)距離（歐幾里得）+紋理距離（歐幾里得）+顏色距離（曼哈頓：Σ|xi-yi|）”三種距離的代數(shù)和表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示17度量空間的坐標(biāo)化度量空間的問(wèn)題：度量空間是個(gè)數(shù)據(jù)集合，集合中的諸元素沒(méi)有坐標(biāo)，這樣就無(wú)法對(duì)集合中的諸元素按遠(yuǎn)近施行劃分（Partitioning）操作。約定：令（M,d）是一個(gè)度量空間，S={xi|xi∈M,i=1,2,…,n}是M中的一個(gè)數(shù)據(jù)集，S?M；在S中選擇k個(gè)支撐點(diǎn)（Pivots），P={pj|j

=1,2,…,k}，

P?S。度量空間數(shù)據(jù)集S到k維實(shí)數(shù)空間的映射：

M→

Rk:IP,d(x)=(d(x,p1),d(x,p2),…,d(x,pk)),x∈S

其中d(x,pi)是x到pi的距離。這樣，度量空間M中數(shù)據(jù)集S的元素xi都賦予了坐標(biāo)。支撐點(diǎn)空間的定義支撐點(diǎn)空間定義：IP,d(S)

={xP|xP=IP,d(x)=(d(x,p1),d(x,p2),…,d(x,pk)),x∈S}解釋?zhuān)褐吸c(diǎn)空間就是度量空間中元素集合S在多維實(shí)數(shù)空間中的映象，其每個(gè)元素的各個(gè)坐標(biāo)是相應(yīng)的度量空間中數(shù)據(jù)到各個(gè)支撐點(diǎn)的距離。5、支撐點(diǎn)空間：度量空間的坐標(biāo)化18

5、支撐點(diǎn)空間：度量空間的坐標(biāo)化19編號(hào)原坐標(biāo)(x,y)映射后坐標(biāo)(d(A,p1),d(A,p2))1(0,0)(0,1.414)2(0,1)(1,1)3(1,1)(1.414,0)4(1,0)(1,1)5(0.5,0.5)(0.707,0.707)支撐點(diǎn)A支撐點(diǎn)B支撐點(diǎn)C初始值012101210123ABCd(x,A)d(x,B)d(x,C)x完全支撐點(diǎn)空間把所有的點(diǎn)都選為支撐點(diǎn)：P=S，M→Rn

IS,d(S)={xS|xS

=IS,d(x)=(d(x,x1),d(x,x2),…,d(x,xk)),x∈S}5、支撐點(diǎn)空間：度量空間的坐標(biāo)化20x1x2……xnx1d(x1,x1)d(x1,x2)……d(x1,xn)x2d(x2,x1)d(x2,x2)……d(x2,xn)………………………………………………xnd(xn,x1)d(xn,x2)……d(xn,xn)6、數(shù)據(jù)劃分技術(shù)在度量空間中，我們可按數(shù)據(jù)到支撐點(diǎn)的遠(yuǎn)近距離進(jìn)行如下3種劃分超平面（Hyper-plane）劃分選擇中心點(diǎn)C1和C2；劃一超平面L（將C1和C2的連線垂直平分）；數(shù)據(jù)按距離C1和C2的遠(yuǎn)近劃分之。21C1C2LLeftofLRightofLC1,C2

6、數(shù)據(jù)劃分技術(shù)有利點(diǎn)（VantagePoint）劃分選擇有利點(diǎn)VP1，以VP1為圓心、R1為半徑畫(huà)圓；數(shù)據(jù)按位于圓內(nèi)、外劃分之；再?gòu)膱A內(nèi)、外分別選擇有利點(diǎn)VP21、VP22，分別以R21和R22為圓心畫(huà)圓。22d(VP1,x)≤R1d(VP1,x)>R1VP1,R1

d(VP22,x)≤R22d(VP22,x)>R22VP22,R22

……VP21,R21

R22

R1

VP1R21VP21VP22qr6、數(shù)據(jù)劃分技術(shù)包絡(luò)球（BoundingSphere）劃分選擇中心點(diǎn)C1，以其為圓心、R(C1)為半徑畫(huà)一圓，包含了所有數(shù)據(jù)；在上述圓內(nèi)另選中心點(diǎn)C2、C3，再以其為圓心，以R(C2)和R(C3)為半徑畫(huà)圓，將數(shù)據(jù)劃分成兩部分；此兩圓均在以C1為圓心的圓內(nèi)，且所有點(diǎn)均在兩圓內(nèi)；因?yàn)橐訡2、C3為圓心的圓是從以C1為圓心的圓衍生出來(lái)的，劃分可能重疊是其明顯缺點(diǎn)。23C1C2C3C1,R(C1)C2,R(C2)

C3,R(C3)

7、大數(shù)據(jù)NC計(jì)算理論NCi類(lèi)（Nick’sClass）的電路定義：NCi類(lèi)均衡電路定義：NCi可定義為可計(jì)算的一組函數(shù)，可由一簇均衡電路輸出的一組布爾函數(shù)值表示，其中電路有多項(xiàng)式數(shù)目個(gè)門(mén)（至多兩輸入），深度為O(login)，i≥1。（電路越深，表示電路的級(jí)數(shù)越多）RNC（RandomizedNC）類(lèi)概率電路定義：它是由一簇概率電路可計(jì)算的一組函數(shù)，此電路中除了通常的門(mén)以外，還有一個(gè)具有隨機(jī)概率“正確”與“錯(cuò)誤”的輸出門(mén)，電路計(jì)算正確的概率至少是1/2。NC類(lèi)的層次NCi類(lèi)層次可定義如下：NC1

?

NC2

?

…?

NCi，NC類(lèi)一般定義：NC=∪k≥1NCk247、大數(shù)據(jù)NC計(jì)算理論大數(shù)據(jù)NC-類(lèi)計(jì)算NC類(lèi)與PRAM模型關(guān)系：定義EREWk、CREWk和CRCWk分別由使用多項(xiàng)式數(shù)目的處理器、運(yùn)行時(shí)間為O(logkn)對(duì)數(shù)多項(xiàng)式的并行計(jì)算模型PRAM-EREW、PRAM-CREW和PRAM-CRCW可計(jì)算的一類(lèi)函數(shù)，它們之間關(guān)系如下：NCk?EREWk?CREWk?CRCWk?NCk+1大數(shù)據(jù)NC-類(lèi)計(jì)算：采用上述方法，首先將大數(shù)據(jù)集D劃分成多項(xiàng)式數(shù)目個(gè)子集Di(i=1,2,···,PolynomialSize)；然后對(duì)Di在對(duì)數(shù)多項(xiàng)式時(shí)間（Polytime）內(nèi)施行并行處理。如果上述步驟證明是可行的，則稱此類(lèi)數(shù)據(jù)計(jì)算為NC-類(lèi)計(jì)算。注1：NC類(lèi)在不同的并行計(jì)算模型上是保持不變的。注2：變量x的多項(xiàng)式通式為：

f(x)=a1x1+a2x2+…+aixi+…+anxn

對(duì)數(shù)logx的多項(xiàng)式通式為：

f(x)=a1logx+a2log2x+…+ailogix+…+anlognx258、大數(shù)據(jù)計(jì)算模式基于MR的流計(jì)算MR是針對(duì)靜態(tài)批處理計(jì)算的，啟動(dòng)MR時(shí)，計(jì)算數(shù)據(jù)均已到位（例如：保存在DFS中的數(shù)據(jù)）；而流數(shù)據(jù)是源源不斷流入系統(tǒng)的，顯然傳統(tǒng)的MR不行，改進(jìn)的方法包括：Micro-BatchMR：首先把流式數(shù)據(jù)按到達(dá)時(shí)間的先后形成一些小的靜態(tài)數(shù)據(jù)；然后定期啟動(dòng)MR施行微批處理計(jì)算。流水MR：通過(guò)作業(yè)內(nèi)或作業(yè)間數(shù)據(jù)傳輸?shù)牧魉€，實(shí)現(xiàn)OnlineHadoop，即實(shí)現(xiàn)了Map到Reduce之間數(shù)據(jù)的Pipeline，使得Map產(chǎn)生部分?jǐn)?shù)據(jù)后就可送到Reduce端，以便Reduce可提前或定期計(jì)算。動(dòng)態(tài)加入輸入：數(shù)據(jù)未完全到位時(shí)，提前向運(yùn)行中的作業(yè)加入新的輸入數(shù)據(jù)，這樣將數(shù)據(jù)流切成較小的datasegment，可大大減少處理大作業(yè)的等待時(shí)間。268、大數(shù)據(jù)計(jì)算模式流計(jì)算（StreamComputing）定義：流處理是一種易于開(kāi)發(fā)并行性的計(jì)算機(jī)編程范例，勿需顯式管理計(jì)算的任務(wù)調(diào)度、同步和通信等。組成：流處理系由一組流式的數(shù)據(jù)和在流數(shù)據(jù)單元上的一系列操作（稱之為KernelFunction）所組成。其中KernelFunction通常是流水線式的。優(yōu)點(diǎn)：因?yàn)镵ernel和Stream抽象揭示了數(shù)據(jù)的相關(guān)性和使用數(shù)據(jù)的局部性，所以編譯工具很容易自動(dòng)優(yōu)化。流處理在傳統(tǒng)的DSP或GPU中廣泛應(yīng)用。注釋?zhuān)涸缭谏鲜兰o(jì)80年代開(kāi)發(fā)的數(shù)據(jù)流語(yǔ)言SISAL(StreamandInteractioninSingleAssignmentLanguage)就是一種流處理語(yǔ)言。278、大數(shù)據(jù)計(jì)算模式實(shí)例研究：Storm流計(jì)算Storm系由函數(shù)式程序設(shè)計(jì)語(yǔ)言開(kāi)發(fā)的。Storm系統(tǒng)架構(gòu)：系統(tǒng)采用主-從結(jié)構(gòu)，由三種節(jié)點(diǎn)組成：主節(jié)點(diǎn)（類(lèi)似Hadoop的Jobtracker）統(tǒng)管全局，負(fù)責(zé)接收作業(yè)，分配任務(wù)；監(jiān)控節(jié)點(diǎn)（類(lèi)似Hadoop的Tasktracker）負(fù)責(zé)接收任務(wù)，起/停工作進(jìn)程；工作節(jié)點(diǎn)執(zhí)行進(jìn)程，負(fù)責(zé)處理數(shù)據(jù)。Storm計(jì)算模型：該模型系由Spout（負(fù)責(zé)產(chǎn)生事件Event）和Bolt（負(fù)責(zé)接收并處理事件）組成。事件Event流會(huì)在Spout和Bolt之間動(dòng)態(tài)流動(dòng)，以計(jì)算出所需的結(jié)果。Storm主要優(yōu)點(diǎn)：Storm具有Scale-out能力，計(jì)算所需的各種狀態(tài)均是自滿足的，可以簡(jiǎn)單地加入新的計(jì)算節(jié)點(diǎn)以滿足系統(tǒng)計(jì)算能力的提升；另外，Storm可以維持分布式計(jì)算涉及到的多進(jìn)程間通信、同步和正確性依賴關(guān)系，確保信息會(huì)被完整處理。288、大數(shù)據(jù)計(jì)算模式增量計(jì)算（IncrementalComputing）定義：增量計(jì)算系指僅對(duì)變化的輸入數(shù)據(jù)施行重新計(jì)算，以節(jié)省全部數(shù)據(jù)計(jì)算時(shí)間。增量計(jì)算前提：增量計(jì)算需要預(yù)先定義好能被單獨(dú)處理的最小變化單元（SmallestUnitofChange）。如果一個(gè)變化在定義好的最小變化單元區(qū)間（Scope）內(nèi)，則可施行增量計(jì)算。增量計(jì)算的實(shí)現(xiàn)：構(gòu)造所有需要再計(jì)算的數(shù)據(jù)元素的相關(guān)圖（DependencyGraph）；需要修改的數(shù)據(jù)元素可由相關(guān)圖的傳遞閉包（TransitiveClosure）給出。也就是說(shuō)，如果從一變化的元素到另一元素存在著一條路徑，則后者將要被修改。應(yīng)用實(shí)例：采用增量計(jì)算處理滲流（過(guò)濾）器（Percolator:IncrementalProcessingUsingDistributedTransactions），獲得比采用MR方法更好的性能，其延遲時(shí)間改善了好幾個(gè)數(shù)量級(jí)（OSDI,2010）。299、大數(shù)據(jù)的復(fù)雜性大數(shù)據(jù)復(fù)雜性表示探索大數(shù)據(jù)的本征特征（IntrinsicProperty）：尋找大數(shù)據(jù)間的本征結(jié)構(gòu)（IntrinsicStructure）；研究大數(shù)據(jù)間的跨時(shí)空連接模式（ConnectionPatterns）。量化大數(shù)據(jù)的特征表示：用抽樣、抽象和特征提取方法量化特征數(shù)據(jù)；將量化的特征數(shù)據(jù)表示成高維稀疏特征矩陣。大數(shù)據(jù)復(fù)雜性度量計(jì)算語(yǔ)義距離：通過(guò)上下文語(yǔ)義分析計(jì)算語(yǔ)義距離；使用測(cè)度函數(shù)（如歐式距離等）和基于機(jī)器學(xué)習(xí)模型度量語(yǔ)義距離。復(fù)雜性度量：選取度量參數(shù)，包括數(shù)據(jù)的多維度性（D）、多樣性（S）、不確定性（U）和間斷性（I）等；構(gòu)建復(fù)雜性函數(shù)f(D,S,U,I)=aD+bS+cU+dI。309、大數(shù)據(jù)復(fù)雜性大數(shù)據(jù)復(fù)雜性模型（BenjaminW.Wah）基于結(jié)構(gòu)的概率圖模型：概率圖模型（ProbabilisticGraphicalModel）是一類(lèi)利用圖形模式（GraphicalModel）表達(dá)基于概率相關(guān)關(guān)系的模型。在此模型中表達(dá)變量（數(shù)據(jù)）之間的關(guān)系時(shí)，通常使用了貝葉斯網(wǎng)絡(luò)（BayesianNetwork）和馬爾科夫隨機(jī)場(chǎng)（MarkovRandomField），其主要區(qū)別