陳國(guó)良-哈工程-大數(shù)據(jù)計(jì)算理論基礎(chǔ)-精簡(jiǎn)版[2014-10]

1、大數(shù)據(jù)計(jì)算理論基礎(chǔ)大數(shù)據(jù)計(jì)算理論基礎(chǔ) Computing Theory Foundations of Big Data2014年10月陳國(guó)良，毛睿，陸克中深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院Version 1: 06/2014Version 1: 06/2014.Version 4: 10/2014Version 4: 10/20142摘要摘要：大數(shù)據(jù)是當(dāng)前IT信息技術(shù)研究和應(yīng)用的熱點(diǎn)。但是，目前的研究多集中于系統(tǒng)和應(yīng)用層面，理論基礎(chǔ)方面的探討相對(duì)較少。本文以計(jì)算復(fù)雜性理論為基礎(chǔ)，著重研究大數(shù)據(jù)的可計(jì)算性及其可計(jì)算原理：主要包括大數(shù)據(jù)的可解與不可解問(wèn)題；大數(shù)據(jù)統(tǒng)一化抽象表示；大數(shù)據(jù)劃分技術(shù)；大數(shù)據(jù)NC類(lèi)計(jì)

2、算理論；大數(shù)據(jù)計(jì)算模式等。最后，根據(jù)大數(shù)據(jù)的4V特性，提出大數(shù)據(jù)處理應(yīng)對(duì)策略和變革思維方法研究大數(shù)據(jù)。3目 錄1.計(jì)算理論與計(jì)算復(fù)雜性(1) 可計(jì)算性與計(jì)算復(fù)雜性(2) 計(jì)算復(fù)雜類(lèi)(3) 復(fù)雜類(lèi)關(guān)系2.大數(shù)據(jù)可計(jì)算性(1) 可（能）解與不可（用）解(2) 大數(shù)據(jù)可（能）解與不可（用）解問(wèn)題3.大數(shù)據(jù)可計(jì)算原理(1) 大數(shù)據(jù)統(tǒng)一化抽象表示：度量空間(2) 大數(shù)據(jù)的劃分(3) 大數(shù)據(jù)NC-類(lèi)計(jì)算(4) 大數(shù)據(jù)計(jì)算模式4.結(jié)論(1) 大數(shù)據(jù)處理應(yīng)對(duì)策略(2) 變革思維研究大數(shù)據(jù)1、計(jì)算理論與計(jì)算復(fù)雜性(1) 可計(jì)算性與計(jì)算復(fù)雜性可計(jì)算性與計(jì)算復(fù)雜性可計(jì)算性可計(jì)算性：對(duì)于一個(gè)問(wèn)題，如果存在一個(gè)機(jī)械機(jī)械

3、過(guò)程，對(duì)給定的輸入，能夠在有限步內(nèi)給出結(jié)果，則稱此問(wèn)題是可計(jì)算的。所謂機(jī)械機(jī)械的過(guò)程，系指在描述計(jì)算的某種設(shè)備上（例如圖靈機(jī)上），實(shí)施該計(jì)算過(guò)程，而給出計(jì)算結(jié)果。計(jì)算復(fù)雜性計(jì)算復(fù)雜性：用數(shù)學(xué)方法研究各類(lèi)問(wèn)題計(jì)算的復(fù)雜性質(zhì)。也可理解為利用計(jì)算機(jī)求解問(wèn)題的難易程度。通常用時(shí)空復(fù)雜性度量。圖靈計(jì)算模型圖靈計(jì)算模型：圖靈機(jī)就是對(duì)一條兩端可無(wú)限延長(zhǎng)的紙帶上的0和1執(zhí)行讀寫(xiě)操作，一步一步地改變紙帶上的0或1值，經(jīng)過(guò)有限步驟最終得到一個(gè)滿足預(yù)先要求的符號(hào)串變換。圖靈可計(jì)算性圖靈可計(jì)算性：圖靈的研究成果認(rèn)為“可計(jì)算性 圖靈可計(jì)算性”，即任何在圖靈機(jī)上可求解的問(wèn)題都是可計(jì)算的！41、計(jì)算理論與計(jì)算復(fù)雜性(2)計(jì)

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

5、ion）到H。簡(jiǎn)記之為：L(NPC) T H(NPH)。5NPHNPCNPP當(dāng)PNP時(shí)，NPH問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)求解。NPPNPC當(dāng)PNP時(shí)，NPC問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)求解。1、計(jì)算理論與計(jì)算復(fù)雜性NC-類(lèi)問(wèn)題類(lèi)問(wèn)題：在PRAM模型上，使用多項(xiàng)式數(shù)目（Polynomial size）的處理器，運(yùn)行在對(duì)數(shù)多項(xiàng)式時(shí)間（Polylog time）內(nèi)的一類(lèi)問(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-歸約到

6、L2，簡(jiǎn)記為L(zhǎng)1 NC L2。P完全（完全（PC）問(wèn)題）問(wèn)題：對(duì)于LP，且P中的任意L均可NC-歸約到L，則稱L是P完全的。6PNCPC當(dāng)PNC時(shí)，PC問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)求解。1、計(jì)算理論與計(jì)算復(fù)雜性(3)復(fù)雜類(lèi)關(guān)系復(fù)雜類(lèi)關(guān)系串行空間與并行時(shí)間關(guān)系Sequential-PSPACE = Parallel-PTIME復(fù)雜類(lèi)包含關(guān)系NC P NP PSPACE EXPTIME EXPSPACE7NCNCP PNPNPPSPACEPSPACEEXPSPACEEXPSPACEEXPTIMEEXPTIME2、大數(shù)據(jù)可計(jì)算性(1)可（能）解（可（能）解（Tractable）與不可（用）解（）與不可（用

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

8、用）解問(wèn)題在大數(shù)據(jù)時(shí)有些問(wèn)題是可（能）解的，例如布爾選擇查詢；但很多問(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)題了。大數(shù)據(jù)查詢類(lèi)可（能）解問(wèn)題（大數(shù)據(jù)查詢類(lèi)可（能）解問(wèn)題（Wenfei Fan）對(duì)于數(shù)據(jù)庫(kù)D中的查詢Q，如果存在著一個(gè)多項(xiàng)式時(shí)間PTIME的預(yù)處理函數(shù)，使得D= (D)，即將D分解成多項(xiàng)式數(shù)目個(gè)D，在對(duì)數(shù)多項(xiàng)式時(shí)間（Polylogarit

9、hmic Time）內(nèi)可完成對(duì)D的并行查詢，這就是所謂的大數(shù)據(jù)查詢類(lèi)的可（能）解問(wèn)題。在大數(shù)據(jù)時(shí)，串行多項(xiàng)式時(shí)間的算法所需的時(shí)間太長(zhǎng)而不實(shí)用，變成不可解的了；但在并行NC類(lèi)計(jì)算時(shí)，因計(jì)算時(shí)間是對(duì)數(shù)多項(xiàng)式的，所以在大數(shù)據(jù)時(shí)，NC類(lèi)計(jì)算仍是可解的。8(1) 大數(shù)據(jù)統(tǒng)一化抽象表示：度量空間大數(shù)據(jù)統(tǒng)一化抽象表示：度量空間距離和度量距離和度量：在數(shù)學(xué)上，度量空間是一個(gè)集合，集合中的元素之間的距離距離（Distance）叫做度量度量（Metric）。度量與度量空間度量與度量空間：設(shè)X為非空集合，d: X X R，(x, y) d(x, y)為映射，如果x,y,zX滿足： d(x, y) = d(y, x)

10、（對(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間的距離。度量空間的坐標(biāo)化度量空間的坐標(biāo)化選擇支撐點(diǎn)：令（X, d）是一個(gè)度量空間，S = xi|xiX, i=1,2,n是X中的一個(gè)數(shù)據(jù)集，S X；在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,p

11、k), xS其中d(x,pi)是x到pi的距離。這樣，度量空間M中數(shù)據(jù)集S的元素xi都賦予了坐標(biāo)。 注：支撐點(diǎn)應(yīng)選擇得使支撐點(diǎn)間的距離要足夠遠(yuǎn)，同時(shí)其應(yīng)與其余點(diǎn)的距離亦足夠遠(yuǎn)。3、大數(shù)據(jù)可計(jì)算原理93、大數(shù)據(jù)可計(jì)算原理(2) 大數(shù)據(jù)的劃分大數(shù)據(jù)的劃分在度量空間中，我們可按數(shù)據(jù)到支撐點(diǎn)的遠(yuǎn)近距離進(jìn)行如下在度量空間中，我們可按數(shù)據(jù)到支撐點(diǎn)的遠(yuǎn)近距離進(jìn)行如下3種劃分種劃分1) 超平面（超平面（Hyper-plane）劃分）劃分超平面樹(shù)（超平面樹(shù)（General Hyper-plane Tree，GHT）：超平面劃分的基本形式）：超平面劃分的基本形式 選擇中心點(diǎn)C1和C2； 劃一超平面L（將C1和C2

12、的連線垂直平分）； 數(shù)據(jù)按距離C1和C2的遠(yuǎn)近劃分之。10C1C2L Left of LRight of LC1,C2 0 x=d(C1, xi)y=d(C2, xi)L: y = x 度量空間度量空間 劃分樹(shù)邏輯結(jié)構(gòu)劃分樹(shù)邏輯結(jié)構(gòu) 支撐點(diǎn)空間支撐點(diǎn)空間3、大數(shù)據(jù)可計(jì)算原理SAT(Spatial Approximation Tree) 在GHT的基礎(chǔ)上，使用多個(gè)中心點(diǎn) 以中心點(diǎn)形成的Voronoi 圖進(jìn)行數(shù)據(jù)劃分11C1, C2, , CnCell of C1Cell of C2Cell of CnC1C6C5C4C3C2C7C8 度量空間度量空間 劃分樹(shù)邏輯結(jié)構(gòu)劃分樹(shù)邏輯結(jié)構(gòu) 高維的支撐點(diǎn)空

13、間高維的支撐點(diǎn)空間3、大數(shù)據(jù)可計(jì)算原理完全完全超平面樹(shù)超平面樹(shù)(Complete General Hyper-plane Tree)令d1, d2表示數(shù)據(jù)到C1, C2的距離，GHT的劃分邊界為d1-d2 =0擴(kuò)展GHT，充分利用d1, d2所包含信息：采用多個(gè)不同的截距： d1-d2 =Hi，即雙曲線劃分考慮變量d1+d2： d1+d2 =Ei，即橢圓劃分12C1C2 度量空間度量空間 支撐點(diǎn)空間支撐點(diǎn)空間d1=d(C1, xi)d2=d(C2, xi)3、大數(shù)據(jù)可計(jì)算原理2）有利點(diǎn)（）有利點(diǎn)（Vantage Point）劃分）劃分有利點(diǎn)樹(shù)有利點(diǎn)樹(shù)(Vantange Point Tree,

14、VPT)：有利點(diǎn)劃分的基本形式：有利點(diǎn)劃分的基本形式 選擇有利點(diǎn)VP1，以VP1為圓心、R1為半徑畫(huà)圓； 數(shù)據(jù)按位于圓內(nèi)、外劃分之； 再?gòu)膱A內(nèi)、外分別選擇有利點(diǎn)VP21、VP22，分別以R21和R22為圓心畫(huà)圓。13 d(VP1, x)R1d(VP1, x)R1VP1,R1 d(VP22, x)R22d(VP22, x)R22VP22,R22 VP21,R21 R22 R1 VP1R21VP21VP22qrR1d(VP1, x) 度量空間度量空間 劃分樹(shù)邏輯結(jié)構(gòu)劃分樹(shù)邏輯結(jié)構(gòu) 支撐點(diǎn)空間支撐點(diǎn)空間3、大數(shù)據(jù)可計(jì)算原理多有利點(diǎn)樹(shù)多有利點(diǎn)樹(shù)(Multiple Vantage Point Tree,

15、 MVPT)擴(kuò)充VPT： 采用多個(gè)有利點(diǎn) 每個(gè)有利點(diǎn)定義多個(gè)半徑進(jìn)行數(shù)據(jù)劃分14VP1VP2d(VP1, x)d(VP2, x) 度量空間度量空間 支撐點(diǎn)空間支撐點(diǎn)空間3、大數(shù)據(jù)可計(jì)算原理3) 包絡(luò)球（包絡(luò)球（Bounding Sphere）劃分）劃分 選擇中心點(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)。15C1C2C3C1,R(C1) C2

16、,R(C2) C3,R(C3) 3、大數(shù)據(jù)可計(jì)算原理(3) 大數(shù)據(jù)大數(shù)據(jù)NC-類(lèi)計(jì)算類(lèi)計(jì)算1) NC計(jì)算時(shí)空復(fù)雜度計(jì)算時(shí)空復(fù)雜度并行化所瞄準(zhǔn)的問(wèn)題是具有W(n)=多項(xiàng)式求解時(shí)間的P類(lèi)問(wèn)題。并行計(jì)算的目標(biāo)是降低求解問(wèn)題的時(shí)間，針對(duì)P類(lèi)問(wèn)題的并行化，應(yīng)將其求解時(shí)間T(n)減少到低于多項(xiàng)式時(shí)間（例如對(duì)數(shù)多項(xiàng)式時(shí)間）。根據(jù)P(n)T(n)W(n)，當(dāng)W(n)為多項(xiàng)式和T(n)低于多項(xiàng)式時(shí)，P(n)應(yīng)選擇為多項(xiàng)式的。2) NC類(lèi)計(jì)算類(lèi)計(jì)算并非所有P類(lèi)問(wèn)題均可有效地在并行機(jī)上求解，其中NC類(lèi)問(wèn)題（NC P）被認(rèn)為能有效地在并行機(jī)上求解：它使用了P(n)=多項(xiàng)式數(shù)目處理器，T(n)=對(duì)數(shù)多項(xiàng)式求解時(shí)間。常見(jiàn)

17、有NC類(lèi)問(wèn)題包括：整數(shù)、運(yùn)算；矩陣運(yùn)算；前綴計(jì)算；選擇和排序；圖的雙連通、連通片、極大匹配；串匹配；計(jì)算幾何中的一些問(wèn)題等。許多NC類(lèi)問(wèn)題是成本最優(yōu)的，例如并行掃描T(n)=O(logn)，P(n)=n/logn，W(n)=O(n)；有些成本最優(yōu)的NC類(lèi)算法是超快的，例如并行字符串匹配算法T(n)=O(loglogn)，P(n)=n/logn。注：“NC類(lèi)”一詞系由Cook杜撰的，它源于研究均衡電路的Nick Pipenger。163、大數(shù)據(jù)可計(jì)算原理3) P類(lèi)問(wèn)題的并行化類(lèi)問(wèn)題的并行化P中的有些問(wèn)題（例如MC2上前綴計(jì)算）其并行求解時(shí)間是亞線性的（T(n)=O(nx), 0 x1），這類(lèi)能被

18、并行化的P類(lèi)問(wèn)題不在NC類(lèi)中。例如當(dāng)n0.5109時(shí)，n log3n，此類(lèi)亞線性的并行算法可能比NC類(lèi)算法還要快。P中的有些問(wèn)題具有“固有（天然）的串行性”，例如P完全問(wèn)題，它不能通過(guò)并行顯著加速，所以被認(rèn)為是“難并行化的問(wèn)題”。常見(jiàn)的P完全問(wèn)題包括：電路值問(wèn)題；線性不等式問(wèn)題；有序深度優(yōu)先搜索問(wèn)題；最大流問(wèn)題；計(jì)算幾何的凸殼問(wèn)題等。4) 大數(shù)據(jù)大數(shù)據(jù)NC類(lèi)計(jì)算類(lèi)計(jì)算NC類(lèi)與類(lèi)與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ì)算的一類(lèi)函數(shù)

19、，它們之間關(guān)系如下：NCk EREWk CREWk CRCWk NCk+1大數(shù)據(jù)大數(shù)據(jù)NC-類(lèi)計(jì)算類(lèi)計(jì)算：在PRAM模型上，首先將大數(shù)據(jù)集D劃分成多項(xiàng)式數(shù)目個(gè)子集Di(i=1,2,Polynomial Size)；然后對(duì)Di在對(duì)數(shù)多項(xiàng)式時(shí)間（Polylogarithmic time）內(nèi)施行并行處理。如果上述步驟證明是可行的，則稱此類(lèi)數(shù)據(jù)計(jì)算為NC-類(lèi)計(jì)算。173、大數(shù)據(jù)可計(jì)算原理在小數(shù)據(jù)時(shí)：在小數(shù)據(jù)時(shí)：NC類(lèi)計(jì)算采用巨量處理器（高階多項(xiàng)式數(shù)目個(gè)），能快速（低階對(duì)數(shù)多項(xiàng)式時(shí)間，數(shù)秒之內(nèi)）求解中等大小規(guī)模的問(wèn)題（幾十萬(wàn)個(gè)輸入）。在大數(shù)據(jù)時(shí)：在大數(shù)據(jù)時(shí)：NC類(lèi)計(jì)算面對(duì)大規(guī)模問(wèn)題（數(shù)百萬(wàn)以上個(gè)輸入）常

20、采用中等大小數(shù)目的處理器（低階多項(xiàng)式，線性或亞線性數(shù)目個(gè)）進(jìn)行很快（高階對(duì)數(shù)多項(xiàng)式時(shí)間）求解。(4)大數(shù)據(jù)計(jì)算模式大數(shù)據(jù)計(jì)算模式基于MR的流計(jì)算：首先把流式數(shù)據(jù)按到達(dá)時(shí)間的先后形成一些小的靜態(tài)數(shù)據(jù)；然后定期啟動(dòng)MR施行微批處理計(jì)算。流計(jì)算：流計(jì)算是一種易于開(kāi)發(fā)并行性的計(jì)算機(jī)編程范例，由一組流式的數(shù)據(jù)和在流數(shù)據(jù)單元上的一系列操作所組成，編譯工具很容易自動(dòng)優(yōu)化,在傳統(tǒng)的DSP或GPU中廣泛應(yīng)用。增量計(jì)算：它僅對(duì)變化的輸入數(shù)據(jù)施行重新計(jì)算，以節(jié)省全部數(shù)據(jù)計(jì)算時(shí)間。增量計(jì)算預(yù)先定義好能被單獨(dú)處理的最小變化單元，當(dāng)輸入數(shù)據(jù)在變化區(qū)間內(nèi)，對(duì)需要再計(jì)算的相關(guān)數(shù)據(jù)元素施行重新計(jì)算，以節(jié)省計(jì)算時(shí)間。18小數(shù)據(jù)小數(shù)據(jù)大數(shù)據(jù)大數(shù)據(jù)處理器數(shù)目高階多項(xiàng)式低階多項(xiàng)式（線性、亞線性）計(jì)算時(shí)間低階對(duì)數(shù)多項(xiàng)式高階對(duì)數(shù)多項(xiàng)式可解性P類(lèi)問(wèn)題會(huì)成為不可解的（PTime）NC類(lèi)問(wèn)題會(huì)是可解的（Logtime）4、結(jié)論(1) 大數(shù)據(jù)處理應(yīng)對(duì)策略大數(shù)據(jù)處理應(yīng)對(duì)策略大容量大容量（Volume）：主要體現(xiàn)數(shù)據(jù)存儲(chǔ)量大和計(jì)算量大。為此，要采用采用并行于分布式處理系統(tǒng)架構(gòu)并行于分布式處理系統(tǒng)架構(gòu)（Parallel & Distributed Processing System Architecture）?？焖俾士焖俾剩╒elocity）：主要指數(shù)據(jù)入/出速度快，更新和增長(zhǎng)速度快，數(shù)據(jù)傳