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

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

2、性度量；大數(shù)據(jù)復雜性模型等。最后，根據(jù)大數(shù)據(jù)的4V特性，提出大數(shù)據(jù)處理應對策略和變革思維方法研究大數(shù)據(jù)。3目 錄1.計算機科學與計算問題分類1.計算機科學的經典定義2.計算機科學定義的數(shù)學解釋3.計算機科學的歷史演變4.計算問題分類2.計算理論1.可計算性與計算復雜性2.圖靈計算模型3.串行復雜計算類：P，NP，NPC，NPH4.并行復雜計算類：NC，PC5.歸約3.大數(shù)據(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.支撐點空間：度量空間的坐標化1.度量空間的坐標化2.支撐點空間的定義3.舉例4.完全支撐點空間6.數(shù)據(jù)的劃分技術1.超平面劃分2.有利點劃分3.包絡球劃分7.大數(shù)據(jù)NC計算理論1.NCi類的電路定義2.NCi類的層次3.大數(shù)據(jù)NC-類計算8.大數(shù)據(jù)計算模式(1) 基于MR的流計算(2) 流計算(3) 實例研究：Storm流計算(4) 增量計算9.大數(shù)據(jù)的復雜性1.大數(shù)據(jù)復雜性表示2.大數(shù)據(jù)復雜性度量3.大計算復雜性模型10. 結論1.大數(shù)據(jù)處理應對策略2.變革思維研究大數(shù)據(jù)1、計算機科學與計算問題分類 41、計算機科學與計算問題分類 計算機科學的歷史演變計算機科學

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

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

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

7、解問題的難易程度。算法復雜性算法復雜性：算法復雜性是對算法效率的度量，系指運行算法所耗費的時間和空間（存儲量）。72、計算理論（Theory of computation） 圖靈計算模型圖靈計算模型將可計算性概念與機械程序的執(zhí)行過程統(tǒng)一起來，確認任一機械執(zhí)行過程均可在一臺機器（即圖靈機）上實現(xiàn)。圖靈機：圖靈機就是對一條兩端可無限延長的紙帶上的0和1執(zhí)行操作，一步一步地改變紙帶上的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模型上，使用多項式數(shù)目（Polynomial size）的處理器，運行在對數(shù)多項式時間（

10、Polylog time）內的一類問題。（此類問題包括整數(shù)加法、乘法、除法，矩陣乘，行列式，找最大匹配（RNC問題）等）。NC-算法算法：在PRAM模型上，一個求解問題的算法使用了多項式數(shù)目的處理器，花費了對數(shù)多項式時間，則稱此算法為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、大數(shù)據(jù)可計算性可（能）解（可（能）解（Tractable）與不可（用）解（）與不可（用）解（Intractable）可（能）解可（能）解（Tractable: meaning “easily managed” ）問題問題：經典定義是在多項式時多項式時間間內可以解決的問題。不可（用）解不可（用）解（Intractable）問題問題：系指理論上能夠解（在無限長時間內），但實際上求解時間太長而無法用的問題。因此缺乏多項式時間缺乏多項式時間解的問題被視為不可（用）解的問題。完全問題不可解性：完全問題不可解性：在PNP時，NPC問題是不可（用）解的問題；在PNC時，PC問題是不

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

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

14、：這是數(shù)據(jù)表示的兩個基本參數(shù)，其中類型可以是一維數(shù)據(jù)、多維數(shù)據(jù)、字符串、圖片等；對于復雜數(shù)據(jù)，除了精確匹配以外，更多要以距離衡量彼此的相似性。多維數(shù)據(jù)作為統(tǒng)一化抽象表示的局限性多維數(shù)據(jù)作為統(tǒng)一化抽象表示的局限性：使用多維數(shù)據(jù)作為統(tǒng)一表示時，數(shù)據(jù)本身必須能表示成特征向量（Feature Vector），且數(shù)據(jù)間的相似性用特征向量的歐式距離等衡量。但對有些數(shù)據(jù)和應用無法滿足上述條件，例如文本字符串往往使用編輯距離，蛋白質序列只能使用比對（Alignment）距離，圖片等只能使用Hausdorff距離等等。統(tǒng)一化抽象表示統(tǒng)一化抽象表示：針對上述情況，可將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 度量空間度量空間拓撲與拓撲空間拓撲與拓撲空間：如果非空集合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、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示16 度量空間舉例度量空間舉例字符串：數(shù)據(jù)類型可用文本類型（如ASCII碼等）數(shù)

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

18、里得）+紋理距離（歐幾里得）+顏色距離（曼哈頓：|xi-yi|）”三種距離的代數(shù)和表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示17 度量空間的坐標化度量空間的坐標化度量空間的問題度量空間的問題：度量空間是個數(shù)據(jù)集合，集合中的諸元素沒有坐標，這樣就無法對集合中的諸元素按遠近施行劃分（Partitioning）操作。約定：令（M, d）是一個度量空間，S = xi|xiM, i=1,2,n是M中的一個數(shù)據(jù)集，S M；在S中選擇k個支撐點（Pivots），P=pj|j = 1,2,k， P S。度量空間數(shù)據(jù)集S到k維實數(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都賦予了坐標。支撐點空間的定義支撐點空間的定義支撐點空間定義：IP,d(S) = xP|xP = IP,d(x) = (d(x,p1), d(x,p2), , d(x,pk), xS解釋：支撐點空間就是度量空間中元素集合S在多維實數(shù)空間中的映象，其每個元素的各個坐標是相應的度量空間中數(shù)據(jù)到各個支撐點的距離。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、數(shù)據(jù)劃分技術在度量空間中，我們可按數(shù)據(jù)到支撐點的遠近距離進行如下在度量空間中，我們可按數(shù)據(jù)到支撐點的遠近距離進行如下3種劃分種劃分超平面（超平面（Hyper-plane）劃分）劃分選擇中心點C1和C2；劃一超平面L（將C1和C2的連線垂直平分）；(1) 數(shù)據(jù)按距離C1和C2的遠近劃分之。21C1C2L Left of LRight of LC1,C2 6、數(shù)據(jù)劃分技術 有利點（有利點（Vantage Point）劃分）劃分選擇有利點VP1，以VP1為圓心、R1為半徑畫圓；數(shù)據(jù)按位于圓內、外劃分之；再從圓內、外分別選擇有利點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ù)劃分技術 包絡球（包絡球（Bounding Sphere）劃分）劃分選擇中心點C1，以其為圓心、R(C1)為半徑畫一圓，包含了所有數(shù)據(jù)；在上述圓內另選中心點C2、C3，再以其為圓心，以R(C2)和R(C3)為半徑畫圓，將數(shù)據(jù)劃分成兩部分；此兩圓均在以C1為圓心的圓內，且所有點均在兩圓內；因為以C2、C3為圓心的圓是從以C1為圓心的圓衍生出來的，劃分可能重疊是其明顯缺

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

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

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

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

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

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

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

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

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

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