大數(shù)據(jù)計(jì)算理論基礎(chǔ)[2014-05]陳國良

1、大數(shù)據(jù)計(jì)算理論基礎(chǔ)大數(shù)據(jù)計(jì)算理論基礎(chǔ) Computing Theory Foundations of Big Data2014年5月陳國良，陸克中，毛睿深圳大學(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ù)雜性（Computational Complexity）和大數(shù)據(jù)本身的復(fù)雜性（Data Complexity）：前者包括大數(shù)據(jù)統(tǒng)一化抽象表示；大數(shù)據(jù)劃分技術(shù)；大數(shù)據(jù)NC類計(jì)算理論；大數(shù)據(jù)計(jì)算模式等。后者包括大數(shù)據(jù)復(fù)雜性表示；大數(shù)據(jù)復(fù)雜

2、性度量；大數(shù)據(jù)復(fù)雜性模型等。最后，根據(jù)大數(shù)據(jù)的4V特性，提出大數(shù)據(jù)處理應(yīng)對(duì)策略和變革思維方法研究大數(shù)據(jù)。3目 錄1.計(jì)算機(jī)科學(xué)與計(jì)算問題分類1.計(jì)算機(jī)科學(xué)的經(jīng)典定義2.計(jì)算機(jī)科學(xué)定義的數(shù)學(xué)解釋3.計(jì)算機(jī)科學(xué)的歷史演變4.計(jì)算問題分類2.計(jì)算理論1.可計(jì)算性與計(jì)算復(fù)雜性2.圖靈計(jì)算模型3.串行復(fù)雜計(jì)算類：P，NP，NPC，NPH4.并行復(fù)雜計(jì)算類：NC，PC5.歸約3.大數(shù)據(jù)可計(jì)算性1.可(能)解與不可(用)解問題2.大數(shù)據(jù)可(能)解與不可(用)解問題3.數(shù)據(jù)庫查詢類的可(能)解與不可(用)解問題4.度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示1.大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路2.距離和度量的概念3.數(shù)據(jù)的度

3、量空間表示4.度量空間舉例5.支撐點(diǎn)空間：度量空間的坐標(biāo)化1.度量空間的坐標(biāo)化2.支撐點(diǎn)空間的定義3.舉例4.完全支撐點(diǎn)空間6.數(shù)據(jù)的劃分技術(shù)1.超平面劃分2.有利點(diǎn)劃分3.包絡(luò)球劃分7.大數(shù)據(jù)NC計(jì)算理論1.NCi類的電路定義2.NCi類的層次3.大數(shù)據(jù)NC-類計(jì)算8.大數(shù)據(jù)計(jì)算模式(1) 基于MR的流計(jì)算(2) 流計(jì)算(3) 實(shí)例研究：Storm流計(jì)算(4) 增量計(jì)算9.大數(shù)據(jù)的復(fù)雜性1.大數(shù)據(jù)復(fù)雜性表示2.大數(shù)據(jù)復(fù)雜性度量3.大計(jì)算復(fù)雜性模型10. 結(jié)論1.大數(shù)據(jù)處理應(yīng)對(duì)策略2.變革思維研究大數(shù)據(jù)1、計(jì)算機(jī)科學(xué)與計(jì)算問題分類 41、計(jì)算機(jī)科學(xué)與計(jì)算問題分類 計(jì)算機(jī)科學(xué)的歷史演變計(jì)算機(jī)科學(xué)

4、的歷史演變計(jì)算機(jī)科學(xué)的形式化研究起源于數(shù)學(xué)的基礎(chǔ)研究：Cantor的集合論集合論與Russell悖論：數(shù)學(xué)家們在集合論中發(fā)現(xiàn)了邏輯矛盾Let R = x | x x then RR R RHilbert綱領(lǐng)：即在通用的形式邏輯系統(tǒng)形式邏輯系統(tǒng)中可以機(jī)械地判定任何給定命題的真?zhèn)危ㄍ陚湫裕?，證明每一形式系統(tǒng)的相容性，從而導(dǎo)出全部數(shù)學(xué)的相容性。Gdel提出了形式系統(tǒng)的不完備性不完備性，它不能窮舉全部數(shù)學(xué)命題，任何足夠強(qiáng)的相容形式系統(tǒng)中均存在著該系統(tǒng)中所不能判定真?zhèn)尾荒芘卸ㄕ鎮(zhèn)蔚拿}。Hilbert綱領(lǐng)的失敗啟發(fā)人們不要花費(fèi)大量精力去證明那些不能判定的問題，而應(yīng)集中精力研究“可計(jì)算求解性可計(jì)算求解性”

5、問題。在此思想指引下，A. M. Turing從計(jì)算一個(gè)數(shù)的一般過程入手，將可計(jì)算性概念與機(jī)械程序的執(zhí)行過程統(tǒng)一起來，此即有名的圖靈計(jì)算模型圖靈計(jì)算模型。51、計(jì)算機(jī)科學(xué)與計(jì)算問題分類 計(jì)算問題分類計(jì)算問題分類6計(jì)算問題不可判定問題可判定問題難解(不可能)解問題易解(可解，多項(xiàng)式時(shí)間)問題不可近似問題可近似問題大數(shù)據(jù)可解(BD-Tractable)問題大數(shù)據(jù)不可解(BD-Intractable)問題大數(shù)據(jù)不可近似問題大數(shù)據(jù)可近似問題2、計(jì)算理論（Theory of computation）可計(jì)算性與計(jì)算復(fù)雜性可計(jì)算性與計(jì)算復(fù)雜性可計(jì)算性可計(jì)算性：對(duì)于一個(gè)問題，如果存在一個(gè)機(jī)械機(jī)械過程，對(duì)給定的

6、輸入，能夠在有限步內(nèi)給出結(jié)果，則稱此問題是可計(jì)算的。所謂機(jī)械機(jī)械的過程，系指在描述計(jì)算的某種設(shè)備上，實(shí)施該計(jì)算過程，而給出計(jì)算結(jié)果?？捎?jì)算性特征可計(jì)算性特征：確定性確定性：對(duì)相同的初始輸入產(chǎn)生相同的輸出。有限性有限性：在有限設(shè)備上能在有限時(shí)間內(nèi)求解。構(gòu)造性構(gòu)造性：每一計(jì)算過程的執(zhí)行都是“機(jī)械的”或“構(gòu)造性的”。數(shù)學(xué)描述性數(shù)學(xué)描述性：計(jì)算的過程可以用嚴(yán)格的數(shù)學(xué)進(jìn)行描述。停機(jī)問題停機(jī)問題：對(duì)于任意的圖靈機(jī)和輸入，是否存在一個(gè)算法，用于判定圖靈機(jī)在接收初始輸入后可到達(dá)停機(jī)狀態(tài)。若能找到此算法，停機(jī)問題可解，否則不可解。計(jì)算復(fù)雜性計(jì)算復(fù)雜性：用數(shù)學(xué)方法研究各類問題計(jì)算的復(fù)雜性質(zhì)。也可理解為利用計(jì)算機(jī)求

7、解問題的難易程度。算法復(fù)雜性算法復(fù)雜性：算法復(fù)雜性是對(duì)算法效率的度量，系指運(yùn)行算法所耗費(fèi)的時(shí)間和空間（存儲(chǔ)量）。72、計(jì)算理論（Theory of computation） 圖靈計(jì)算模型圖靈計(jì)算模型將可計(jì)算性概念與機(jī)械程序的執(zhí)行過程統(tǒng)一起來，確認(rèn)任一機(jī)械執(zhí)行過程均可在一臺(tái)機(jī)器（即圖靈機(jī)）上實(shí)現(xiàn)。圖靈機(jī)：圖靈機(jī)就是對(duì)一條兩端可無限延長的紙帶上的0和1執(zhí)行操作，一步一步地改變紙帶上的0或1值，經(jīng)此有限步驟最終得到一個(gè)滿足預(yù)先要求的符號(hào)串變換。圖靈機(jī)的作用：圖靈的研究成果認(rèn)為“可計(jì)算性 圖靈可計(jì)算性”，即任何在圖靈機(jī)上可求解的問題都是可計(jì)算的！82、計(jì)算理論（Theory of computatio

8、n）串行計(jì)算類：串行計(jì)算類：P，NP，NPC，NPHP類問題類問題：在確定圖靈機(jī)上多項(xiàng)式（Polynomial）時(shí)間內(nèi)可求解的一類問題。NP類問題類問題：在非確定圖靈機(jī)上多項(xiàng)式時(shí)間內(nèi)可求解的一類問題（所有NP問題均必須在有限步內(nèi)是可判定的）。NPC問題問題：對(duì)于LNP的問題，且NP類中的每一個(gè)L均可在多項(xiàng)式時(shí)間內(nèi)歸約（轉(zhuǎn)換）到L，LP L，則稱L為NPC（NP完全）的（第一個(gè)被證明是NPC問題的是布爾滿足性問題：Boolean Satisfiability Problem，SAT）。NPH（難）問題（難）問題：一個(gè)問題H稱為NP難的，當(dāng)且僅當(dāng)存在著一個(gè)NPC問題L，L可在多項(xiàng)式時(shí)間內(nèi)圖靈歸約圖

9、靈歸約（Turing-Reduction）到H。簡記之為：L(NPC) T H(NPH)（例如判定停機(jī)問題是NPH問題）。9NPHNPCNPPNPPNPC當(dāng)PNP時(shí)，NPH問題不能在多項(xiàng)式時(shí)間內(nèi)求解。當(dāng)PNP時(shí)，NPC問題不能在多項(xiàng)式時(shí)間內(nèi)求解。注：注：所有NPC問題均能在多項(xiàng)式時(shí)間內(nèi)歸約到NPH而求解之。 NPC中的每個(gè)元素均必須是NP中的元素。 NPH問題中不一定必須是NP中的元素。2、計(jì)算理論（Theory of computation）并行計(jì)算類：并行計(jì)算類：NC，PCNC-類問題類問題：在PRAM模型上，使用多項(xiàng)式數(shù)目（Polynomial size）的處理器，運(yùn)行在對(duì)數(shù)多項(xiàng)式時(shí)間（

10、Polylog time）內(nèi)的一類問題。（此類問題包括整數(shù)加法、乘法、除法，矩陣乘，行列式，找最大匹配（RNC問題）等）。NC-算法算法：在PRAM模型上，一個(gè)求解問題的算法使用了多項(xiàng)式數(shù)目的處理器，花費(fèi)了對(duì)數(shù)多項(xiàng)式時(shí)間，則稱此算法為NC-算法。NC-歸約形式定義歸約形式定義：對(duì)于問題L1和L2，如果存在一個(gè)NC-算法，可將L1的求解轉(zhuǎn)換成L2的求解，則稱L1可NC-歸約到L2，簡記為L1 NC L2。P完全（完全（PC）問題）問題：對(duì)于LP，且P中的任意L均可NC-歸約到L，則稱L是P完全的。10PNCPC當(dāng)PNC時(shí)，PC問題不能在多項(xiàng)式時(shí)間內(nèi)求解。2、計(jì)算理論（Theory of comp

11、utation） 113、大數(shù)據(jù)可計(jì)算性可（能）解（可（能）解（Tractable）與不可（用）解（）與不可（用）解（Intractable）可（能）解可（能）解（Tractable: meaning “easily managed” ）問題問題：經(jīng)典定義是在多項(xiàng)式時(shí)多項(xiàng)式時(shí)間間內(nèi)可以解決的問題。不可（用）解不可（用）解（Intractable）問題問題：系指理論上能夠解（在無限長時(shí)間內(nèi)），但實(shí)際上求解時(shí)間太長而無法用的問題。因此缺乏多項(xiàng)式時(shí)間缺乏多項(xiàng)式時(shí)間解的問題被視為不可（用）解的問題。完全問題不可解性：完全問題不可解性：在PNP時(shí)，NPC問題是不可（用）解的問題；在PNC時(shí)，PC問題是不

12、可（用）解的問題。大數(shù)據(jù)可（能）解與不可（用）解問題大數(shù)據(jù)可（能）解與不可（用）解問題在大數(shù)據(jù)時(shí)有些問題是可（能）解的，例如布爾選擇查詢（在數(shù)據(jù)集D中，是否存在某一列的元組值為指定值，在B+樹1索引上可在O(log(|D|)時(shí)間內(nèi)解決）；但很多問題是不可（能）解的，例如圖的寬度優(yōu)先搜索2 （是P完全的）。在大數(shù)據(jù)時(shí)，傳統(tǒng)的可（能）解問題，可能成為不可（用）解問題：例如采用速度可達(dá)6Gbps的快速硬盤，線性掃描1EB（E=1018字節(jié)）的數(shù)據(jù)，這本是線性復(fù)雜度的可（能）解問題，但實(shí)際需要長達(dá)5.28年時(shí)間，這就變成了不可（用）解問題了。12注1：B+樹樹是B樹的變形，關(guān)鍵字與數(shù)據(jù)值（鍵/值）成對(duì)

13、存儲(chǔ)在樹的同一節(jié)點(diǎn)中，其中所有數(shù)據(jù)值存在樹的葉節(jié)點(diǎn)中，只將關(guān)鍵字與子女節(jié)點(diǎn)的指針存在樹的內(nèi)節(jié)點(diǎn)中。注2：寬度優(yōu)先搜索寬度優(yōu)先搜索（BFS：Breadth-First-Search）從根節(jié)點(diǎn)開始，沿著樹的寬度遍歷其所有子節(jié)點(diǎn)，這些子節(jié)點(diǎn)被加入一個(gè)先進(jìn)先出FIFO的隊(duì)列中。然后從FIFO隊(duì)列中取出先進(jìn)入的子節(jié)點(diǎn)，重復(fù)上述寬度遍歷過程，直到所有節(jié)點(diǎn)均被訪問過。BFS問題是個(gè)P完全問題。 3、大數(shù)據(jù)可計(jì)算性13PTIME(TQ)BD-IntractableBD-Tractable(TQ0)P(TQ)NCPCTQ0 大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路類型和距離函數(shù)類型和距離函數(shù)

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

15、riety距離抽象成統(tǒng)一的距離函數(shù)，此即下述的度量空間表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示14 4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示15supinf,y Yx Xd x y,maxsupinf,supinf,Hy Yx Xx Xy YdX Yd x yd x ysupinf,x Xy Yd x y 度量空間度量空間拓?fù)渑c拓?fù)淇臻g拓?fù)渑c拓?fù)淇臻g：如果非空集合X的子集族，它滿足以下條件：和X在中；的任意子族之元素的“并”（）在中；的任意子族之元素的“交”（）在中。則稱為X上的一個(gè)拓?fù)渫負(fù)洌═opology），偶對(duì)（X, ）稱為X上的一個(gè)拓?fù)淇臻g拓?fù)淇臻g（Topology Space）。度量與度量

16、空間度量與度量空間：設(shè)X為非空集合，d: X X R，(x, y) d(x, y)為映射，如果x,y,zX滿足： d(x, y) = d(y, x)（對(duì)稱性）； d(x, y) 0 和 d(x, y) = 0 iff x = y（半正定性）； d(x, z) d(x, y) + d(y, z)（三角不等式）。則稱d為X上的一個(gè)度量度量（距離），偶對(duì)（X,d）為度量空間度量空間，d(x,y)稱為是x與y間的距離。注注：度量空間是一類特殊的拓?fù)淇臻g；而n維歐氏空間是一類特殊的度量空間。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示16 度量空間舉例度量空間舉例字符串：數(shù)據(jù)類型可用文本類型（如ASCII碼等）數(shù)

17、組表示；其距離函數(shù)可用編輯距離（Edit Distance）表示：即將兩個(gè)字符串相互轉(zhuǎn)換所需的編輯動(dòng)作（插入、刪除、替換等）的總開銷。蛋白質(zhì)序列：數(shù)據(jù)類型可用字節(jié)（蛋白質(zhì)的序列由20種氨基酸表示，每一種氨基酸用一個(gè)字節(jié)表示）數(shù)組表示；其距離函數(shù)可用全局比對(duì)（Global Alignment）表示：即加權(quán)的編輯距離。基因序列：數(shù)據(jù)類型可用字節(jié)（基因序列由4種堿基表示，每一種堿基用一個(gè)字節(jié)表示）數(shù)組表示；其距離函數(shù)可用海明距離（Hamming Distance：對(duì)應(yīng)位不相同的數(shù)目）表示。圖片：數(shù)據(jù)類型可用長度為66的實(shí)數(shù)數(shù)組表示，用以表征圖片的結(jié)構(gòu)、紋理、顏色等特征；其距離函數(shù)可用“結(jié)構(gòu)距離（歐幾

18、里得）+紋理距離（歐幾里得）+顏色距離（曼哈頓：|xi-yi|）”三種距離的代數(shù)和表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示17 度量空間的坐標(biāo)化度量空間的坐標(biāo)化度量空間的問題度量空間的問題：度量空間是個(gè)數(shù)據(jù)集合，集合中的諸元素沒有坐標(biāo)，這樣就無法對(duì)集合中的諸元素按遠(yuǎn)近施行劃分（Partitioning）操作。約定：令（M, d）是一個(gè)度量空間，S = xi|xiM, 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),

19、, d(x,pk), xS其中d(x,pi)是x到pi的距離。這樣，度量空間M中數(shù)據(jù)集S的元素xi都賦予了坐標(biāo)。支撐點(diǎn)空間的定義支撐點(diǎn)空間的定義支撐點(diǎn)空間定義：IP,d(S) = xP|xP = IP,d(x) = (d(x,p1), d(x,p2), , d(x,pk), xS解釋：支撐點(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

20、)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初始值0 1 21 0 12 1 01 2 3A B Cd(x,A)d(x,B)d(x,C)x 完全支撐點(diǎn)空間完全支撐點(diǎn)空間把所有的點(diǎn)都選為支撐點(diǎn)：P=S，MRnIS,d(S) = xS|xS = IS,d(x) = (d(x,x1), d(x,x2), , d(x,xk), xS5、支撐點(diǎn)空間：度量空間的坐標(biāo)化20 x1x2xnx1d(x1, x1)d(x1, x2)d(x1, xn)x2d(x2, x1)d(x2, x2)d(x2, xn)xnd(xn,

21、x1)d(xn, x2)d(xn, xn)6、數(shù)據(jù)劃分技術(shù)在度量空間中，我們可按數(shù)據(jù)到支撐點(diǎn)的遠(yuǎn)近距離進(jìn)行如下在度量空間中，我們可按數(shù)據(jù)到支撐點(diǎn)的遠(yuǎn)近距離進(jìn)行如下3種劃分種劃分超平面（超平面（Hyper-plane）劃分）劃分選擇中心點(diǎn)C1和C2；劃一超平面L（將C1和C2的連線垂直平分）；(1) 數(shù)據(jù)按距離C1和C2的遠(yuǎn)近劃分之。21C1C2L Left of LRight of LC1,C2 6、數(shù)據(jù)劃分技術(shù) 有利點(diǎn)（有利點(diǎn)（Vantage Point）劃分）劃分選擇有利點(diǎn)VP1，以VP1為圓心、R1為半徑畫圓；數(shù)據(jù)按位于圓內(nèi)、外劃分之；再從圓內(nèi)、外分別選擇有利點(diǎn)VP21、VP22，分別以

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

23、點(diǎn)。23C1C2C3C1,R(C1) C2,R(C2) C3,R(C3) 7、大數(shù)據(jù)NC計(jì)算理論 NCi類（類（Nicks Class）的電路定義：）的電路定義：NCi類均衡電路定義類均衡電路定義：NCi可定義為可計(jì)算的一組函數(shù)，可由一簇均衡電路輸出的一組布爾函數(shù)值表示，其中電路有多項(xiàng)式數(shù)目個(gè)門（至多兩輸入），深度為O(login)，i1。（電路越深，表示電路的級(jí)數(shù)越多）RNC（Randomized NC）類概率電路定義類概率電路定義：它是由一簇概率電路可計(jì)算的一組函數(shù)，此電路中除了通常的門以外，還有一個(gè)具有隨機(jī)概率“正確”與“錯(cuò)誤”的輸出門，電路計(jì)算正確的概率至少是1/2。 NC類的層次類的

24、層次NCi類層次可定義如下類層次可定義如下：NC1 NC2 NCi，NC類一般定義：NC = k1NCk247、大數(shù)據(jù)NC計(jì)算理論 大數(shù)據(jù)大數(shù)據(jù)NC-類計(jì)算類計(jì)算NC類與類與PRAM模型關(guān)系模型關(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ì)算的一類函數(shù)，它們之間關(guān)系如下：NCk EREWk CREWk CRCWk NCk+1大數(shù)據(jù)大數(shù)據(jù)NC-類計(jì)算類計(jì)算：采用上述方法，首先將大數(shù)據(jù)集D劃分成多項(xiàng)式數(shù)目個(gè)子集Di(i=1,2,Polynomial Size)

25、；然后對(duì)Di在對(duì)數(shù)多項(xiàng)式時(shí)間（Polytime）內(nèi)施行并行處理。如果上述步驟證明是可行的，則稱此類數(shù)據(jù)計(jì)算為NC-類計(jì)算。注注1：NC類在不同的并行計(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ì)算的流計(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-Batch MR

26、：首先把流式數(shù)據(jù)按到達(dá)時(shí)間的先后形成一些小的靜態(tài)數(shù)據(jù)；然后定期啟動(dòng)MR施行微批處理計(jì)算。流水流水MR：通過作業(yè)內(nèi)或作業(yè)間數(shù)據(jù)傳輸?shù)牧魉€，實(shí)現(xiàn)Online Hadoop，即實(shí)現(xiàn)了Map到Reduce之間數(shù)據(jù)的Pipeline，使得Map產(chǎn)生部分?jǐn)?shù)據(jù)后就可送到Reduce端，以便Reduce可提前或定期計(jì)算。動(dòng)態(tài)加入輸入動(dòng)態(tài)加入輸入：數(shù)據(jù)未完全到位時(shí)，提前向運(yùn)行中的作業(yè)加入新的輸入數(shù)據(jù)，這樣將數(shù)據(jù)流切成較小的data segment，可大大減少處理大作業(yè)的等待時(shí)間。268、大數(shù)據(jù)計(jì)算模式 流計(jì)算（流計(jì)算（Stream Computing）定義定義：流處理是一種易于開發(fā)并行性的計(jì)算機(jī)編程范例，勿需

27、顯式管理計(jì)算的任務(wù)調(diào)度、同步和通信等。組成組成：流處理系由一組流式的數(shù)據(jù)和在流數(shù)據(jù)單元上的一系列操作（稱之為Kernel Function）所組成。其中Kernel Function通常是流水線式的。優(yōu)點(diǎn)優(yōu)點(diǎn)：因?yàn)镵ernel和Stream抽象揭示了數(shù)據(jù)的相關(guān)性和使用數(shù)據(jù)的局部性，所以編譯工具很容易自動(dòng)優(yōu)化。流處理在傳統(tǒng)的DSP或GPU中廣泛應(yīng)用。注釋注釋：早在上世紀(jì)80年代開發(fā)的數(shù)據(jù)流語言SISAL(Stream and Interaction in Single Assignment Language)就是一種流處理語言。278、大數(shù)據(jù)計(jì)算模式 實(shí)例研究：實(shí)例研究：Storm流計(jì)算流計(jì)算S

28、torm系由函數(shù)式程序設(shè)計(jì)語言開發(fā)的。Storm系統(tǒng)架構(gòu)系統(tǒng)架構(gòu)：系統(tǒng)采用主-從結(jié)構(gòu)，由三種節(jié)點(diǎn)組成：主節(jié)點(diǎn)（類似Hadoop的Job tracker）統(tǒng)管全局，負(fù)責(zé)接收作業(yè)，分配任務(wù)；監(jiān)控節(jié)點(diǎn)（類似Hadoop的Task tracker）負(fù)責(zé)接收任務(wù)，起/停工作進(jìn)程；工作節(jié)點(diǎn)執(zhí)行進(jìn)程，負(fù)責(zé)處理數(shù)據(jù)。Storm計(jì)算模型計(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)主要優(yōu)點(diǎn)：Storm具有Scale-out能力，計(jì)算所需的各種狀態(tài)均是自滿足的，可以簡單地加入

29、新的計(jì)算節(jié)點(diǎn)以滿足系統(tǒng)計(jì)算能力的提升；另外，Storm可以維持分布式計(jì)算涉及到的多進(jìn)程間通信、同步和正確性依賴關(guān)系，確保信息會(huì)被完整處理。288、大數(shù)據(jù)計(jì)算模式 增量計(jì)算（增量計(jì)算（Incremental Computing）定義定義：增量計(jì)算系指僅對(duì)變化的輸入數(shù)據(jù)施行重新計(jì)算，以節(jié)省全部數(shù)據(jù)計(jì)算時(shí)間。增量計(jì)算前提增量計(jì)算前提：增量計(jì)算需要預(yù)先定義好能被單獨(dú)處理的最小變化單元最小變化單元（Smallest Unit of Change）。如果一個(gè)變化在定義好的最小變化單元區(qū)間（Scope）內(nèi)，則可施行增量計(jì)算。增量計(jì)算的實(shí)現(xiàn)增量計(jì)算的實(shí)現(xiàn)：構(gòu)造所有需要再計(jì)算的數(shù)據(jù)元素的相關(guān)圖（Dependen

30、cy Graph）；需要修改的數(shù)據(jù)元素可由相關(guān)圖的傳遞閉包（Transitive Closure）給出。也就是說，如果從一變化的元素到另一元素存在著一條路徑，則后者將要被修改。應(yīng)用實(shí)例應(yīng)用實(shí)例：采用增量計(jì)算處理滲流（過濾）器（Percolator: Incremental Processing Using Distributed Transactions），獲得比采用MR方法更好的性能，其延遲時(shí)間改善了好幾個(gè)數(shù)量級(jí)（OSDI, 2010）。299、大數(shù)據(jù)的復(fù)雜性大數(shù)據(jù)復(fù)雜性表示大數(shù)據(jù)復(fù)雜性表示探索大數(shù)據(jù)的本征特征（探索大數(shù)據(jù)的本征特征（Intrinsic Property）：尋找大數(shù)據(jù)間的本征

31、結(jié)構(gòu)（Intrinsic Structure）；研究大數(shù)據(jù)間的跨時(shí)空連接模式（Connection Patterns）。量化大數(shù)據(jù)的特征表示量化大數(shù)據(jù)的特征表示：用抽樣、抽象和特征提取方法量化特征數(shù)據(jù)；將量化的特征數(shù)據(jù)表示成高維稀疏特征矩陣。大數(shù)據(jù)復(fù)雜性度量大數(shù)據(jù)復(fù)雜性度量計(jì)算語義距離計(jì)算語義距離：通過上下文語義分析計(jì)算語義距離；使用測度函數(shù)（如歐式距離等）和基于機(jī)器學(xué)習(xí)模型度量語義距離。復(fù)雜性度量復(fù)雜性度量：選取度量參數(shù)度量參數(shù)，包括數(shù)據(jù)的多維度性（D）、多樣性（S）、不確定性（U）和間斷性（I）等；構(gòu)建復(fù)雜性函數(shù)復(fù)雜性函數(shù)f(D,S,U,I)=aD+bS+cU+dI。309、大數(shù)據(jù)復(fù)雜性

32、大數(shù)據(jù)復(fù)雜性模型（大數(shù)據(jù)復(fù)雜性模型（Benjamin W. Wah）基于結(jié)構(gòu)的概率圖模型基于結(jié)構(gòu)的概率圖模型：概率圖模型（Probabilistic Graphical Model）是一類利用圖形模式圖形模式（Graphical Model）表達(dá)基于概率相關(guān)關(guān)系的模型。在此模型中表達(dá)變量（數(shù)據(jù)）之間的關(guān)系時(shí)，通常使用了貝葉斯網(wǎng)絡(luò)（Bayesian Network）和馬爾科夫隨機(jī)場（Markov Random Field），其主要區(qū)別是貝葉斯網(wǎng)絡(luò)采用有向無環(huán)圖（Directed Acyclic Graph）來表達(dá)因果關(guān)系，而馬爾科夫隨機(jī)場則采用無向圖（Undirected Graph）來表達(dá)變量的相互關(guān)系。概率圖模型主要研究其精確推理/近似推理方法和模型的參數(shù)及結(jié)構(gòu)學(xué)習(xí)方法，以及用此模型進(jìn)行統(tǒng)計(jì)決策建模等。II