1、大數據計算理論基礎大數據計算理論基礎 Computing Theory Foundations of Big Data2014年5月陳國良，陸克中，毛睿深圳大學計算機與軟件學院2摘要摘要：大數據是當前IT信息技術研究和應用的熱點。但是，目前的研究多集中于系統和應用層面，理論基礎方面的探討相對較少。本文從計算機科學講起，以計算復雜性理論為基礎，著重研究大數據的計算復雜性（Computational Complexity）和大數據本身的復雜性（Data Complexity）：前者包括大數據統一化抽象表示；大數據劃分技術；大數據NC類計算理論；大數據計算模式等。后者包括大數據復雜性表示；大數據復雜

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

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

4、的歷史演變計算機科學的形式化研究起源于數學的基礎研究：Cantor的集合論集合論與Russell悖論：數學家們在集合論中發現了邏輯矛盾Let R = x | x x then RR R RHilbert綱領：即在通用的形式邏輯系統形式邏輯系統中可以機械地判定任何給定命題的真偽（完備性），證明每一形式系統的相容性，從而導出全部數學的相容性。Gdel提出了形式系統的不完備性不完備性，它不能窮舉全部數學命題，任何足夠強的相容形式系統中均存在著該系統中所不能判定真偽不能判定真偽的命題。Hilbert綱領的失敗啟發人們不要花費大量精力去證明那些不能判定的問題，而應集中精力研究“可計算求解性可計算求解性”

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

6、輸入，能夠在有限步內給出結果，則稱此問題是可計算的。所謂機械機械的過程，系指在描述計算的某種設備上，實施該計算過程，而給出計算結果。可計算性特征可計算性特征：確定性確定性：對相同的初始輸入產生相同的輸出。有限性有限性：在有限設備上能在有限時間內求解。構造性構造性：每一計算過程的執行都是“機械的”或“構造性的”。數學描述性數學描述性：計算的過程可以用嚴格的數學進行描述。停機問題停機問題：對于任意的圖靈機和輸入，是否存在一個算法，用于判定圖靈機在接收初始輸入后可到達停機狀態。若能找到此算法，停機問題可解，否則不可解。計算復雜性計算復雜性：用數學方法研究各類問題計算的復雜性質。也可理解為利用計算機求

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

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

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

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

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

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

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

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

15、riety距離抽象成統一的距離函數，此即下述的度量空間表示。4、度量空間：大數據統一化抽象表示14 4、度量空間：大數據統一化抽象表示15supinf,y Yx Xd x y,maxsupinf,supinf,Hy Yx Xx Xy YdX Yd x yd x ysupinf,x Xy Yd x y 度量空間度量空間拓撲與拓撲空間拓撲與拓撲空間：如果非空集合X的子集族，它滿足以下條件：和X在中；的任意子族之元素的“并”（）在中；的任意子族之元素的“交”（）在中。則稱為X上的一個拓撲拓撲（Topology），偶對（X, ）稱為X上的一個拓撲空間拓撲空間（Topology Space）。度量與度量

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

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

18、里得）+紋理距離（歐幾里得）+顏色距離（曼哈頓：|xi-yi|）”三種距離的代數和表示。4、度量空間：大數據統一化抽象表示17 度量空間的坐標化度量空間的坐標化度量空間的問題度量空間的問題：度量空間是個數據集合，集合中的諸元素沒有坐標，這樣就無法對集合中的諸元素按遠近施行劃分（Partitioning）操作。約定：令（M, d）是一個度量空間，S = xi|xiM, i=1,2,n是M中的一個數據集，S M；在S中選擇k個支撐點（Pivots），P=pj|j = 1,2,k， P S。度量空間數據集S到k維實數空間的映射：M Rk : IP,d(x) = (d(x,p1), d(x,p2),

19、, d(x,pk), xS其中d(x,pi)是x到pi的距離。這樣，度量空間M中數據集S的元素xi都賦予了坐標。支撐點空間的定義支撐點空間的定義支撐點空間定義：IP,d(S) = xP|xP = IP,d(x) = (d(x,p1), d(x,p2), , d(x,pk), xS解釋：支撐點空間就是度量空間中元素集合S在多維實數空間中的映象，其每個元素的各個坐標是相應的度量空間中數據到各個支撐點的距離。5、支撐點空間：度量空間的坐標化18 5、支撐點空間：度量空間的坐標化19編號原坐標(x,y)映射后坐標(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)支撐點A支撐點B支撐點C初始值0 1 21 0 12 1 01 2 3A B Cd(x,A)d(x,B)d(x,C)x 完全支撐點空間完全支撐點空間把所有的點都選為支撐點：P=S，MRnIS,d(S) = xS|xS = IS,d(x) = (d(x,x1), d(x,x2), , d(x,xk), xS5、支撐點空間：度量空間的坐標化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、數據劃分技術在度量空間中，我們可按數據到支撐點的遠近距離進行如下在度量空間中，我們可按數據到支撐點的遠近距離進行如下3種劃分種劃分超平面（超平面（Hyper-plane）劃分）劃分選擇中心點C1和C2；劃一超平面L（將C1和C2的連線垂直平分）；(1) 數據按距離C1和C2的遠近劃分之。21C1C2L Left of LRight of LC1,C2 6、數據劃分技術 有利點（有利點（Vantage Point）劃分）劃分選擇有利點VP1，以VP1為圓心、R1為半徑畫圓；數據按位于圓內、外劃分之；再從圓內、外分別選擇有利點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、數據劃分技術 包絡球（包絡球（Bounding Sphere）劃分）劃分選擇中心點C1，以其為圓心、R(C1)為半徑畫一圓，包含了所有數據；在上述圓內另選中心點C2、C3，再以其為圓心，以R(C2)和R(C3)為半徑畫圓，將數據劃分成兩部分；此兩圓均在以C1為圓心的圓內，且所有點均在兩圓內；因為以C2、C3為圓心的圓是從以C1為圓心的圓衍生出來的，劃分可能重疊是其明顯缺

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

24、層次NCi類層次可定義如下類層次可定義如下：NC1 NC2 NCi，NC類一般定義：NC = k1NCk247、大數據NC計算理論 大數據大數據NC-類計算類計算NC類與類與PRAM模型關系模型關系：定義EREWk、CREWk和CRCWk分別由使用多項式數目的處理器、運行時間為O(logkn)對數多項式的并行計算模型PRAM-EREW、PRAM-CREW和PRAM-CRCW可計算的一類函數，它們之間關系如下：NCk EREWk CREWk CRCWk NCk+1大數據大數據NC-類計算類計算：采用上述方法，首先將大數據集D劃分成多項式數目個子集Di(i=1,2,Polynomial Size)

25、；然后對Di在對數多項式時間（Polytime）內施行并行處理。如果上述步驟證明是可行的，則稱此類數據計算為NC-類計算。注注1：NC類在不同的并行計算模型上是保持不變的。注注2：變量x的多項式通式為： f(x) = a1x1+ a2x2+ aixi+ anxn 對數logx的多項式通式為： f(x) = a1logx+a2log2x+ailogix+anlognx258、大數據計算模式基于基于MR的流計算的流計算MR是針對靜態批處理計算的，啟動MR時，計算數據均已到位（例如：保存在DFS中的數據）；而流數據是源源不斷流入系統的，顯然傳統的MR不行，改進的方法包括：Micro-Batch MR

26、：首先把流式數據按到達時間的先后形成一些小的靜態數據；然后定期啟動MR施行微批處理計算。流水流水MR：通過作業內或作業間數據傳輸的流水線，實現Online Hadoop，即實現了Map到Reduce之間數據的Pipeline，使得Map產生部分數據后就可送到Reduce端，以便Reduce可提前或定期計算。動態加入輸入動態加入輸入：數據未完全到位時，提前向運行中的作業加入新的輸入數據，這樣將數據流切成較小的data segment，可大大減少處理大作業的等待時間。268、大數據計算模式 流計算（流計算（Stream Computing）定義定義：流處理是一種易于開發并行性的計算機編程范例，勿需

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

28、torm系由函數式程序設計語言開發的。Storm系統架構系統架構：系統采用主-從結構，由三種節點組成：主節點（類似Hadoop的Job tracker）統管全局，負責接收作業，分配任務；監控節點（類似Hadoop的Task tracker）負責接收任務，起/停工作進程；工作節點執行進程，負責處理數據。Storm計算模型計算模型：該模型系由Spout（負責產生事件Event）和Bolt（負責接收并處理事件）組成。事件Event流會在Spout和Bolt之間動態流動，以計算出所需的結果。Storm主要優點主要優點：Storm具有Scale-out能力，計算所需的各種狀態均是自滿足的，可以簡單地加入

29、新的計算節點以滿足系統計算能力的提升；另外，Storm可以維持分布式計算涉及到的多進程間通信、同步和正確性依賴關系，確保信息會被完整處理。288、大數據計算模式 增量計算（增量計算（Incremental Computing）定義定義：增量計算系指僅對變化的輸入數據施行重新計算，以節省全部數據計算時間。增量計算前提增量計算前提：增量計算需要預先定義好能被單獨處理的最小變化單元最小變化單元（Smallest Unit of Change）。如果一個變化在定義好的最小變化單元區間（Scope）內，則可施行增量計算。增量計算的實現增量計算的實現：構造所有需要再計算的數據元素的相關圖（Dependen

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

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

32、大數據復雜性模型（大數據復雜性模型（Benjamin W. Wah）基于結構的概率圖模型基于結構的概率圖模型：概率圖模型（Probabilistic Graphical Model）是一類利用圖形模式圖形模式（Graphical Model）表達基于概率相關關系的模型。在此模型中表達變量（數據）之間的關系時，通常使用了貝葉斯網絡（Bayesian Network）和馬爾科夫隨機場（Markov Random Field），其主要區別是貝葉斯網絡采用有向無環圖（Directed Acyclic Graph）來表達因果關系，而馬爾科夫隨機場則采用無向圖（Undirected Graph）來表達變量的相互關系。概率圖模型主要研究其精確推理/近似推理方法和模型的參數及結構學習方法，以及用此模型進行統計決策建模等。II