陈国良-哈工程-大数据计算理论基础-精简版[2014-10]

1、大数据计算理论基础大数据计算理论基础 Computing Theory Foundations of Big Data2014年10月陈国良，毛睿，陆克中深圳大学计算机与软件学院Version 1: 06/2014Version 1: 06/2014.Version 4: 10/2014Version 4: 10/20142摘要摘要：大数据是当前IT信息技术研究和应用的热点。但是，目前的研究多集中于系统和应用层面，理论基础方面的探讨相对较少。本文以计算复杂性理论为基础，着重研究大数据的可计算性及其可计算原理：主要包括大数据的可解与不可解问题；大数据统一化抽象表示；大数据划分技术；大数据NC类计

2、算理论；大数据计算模式等。最后，根据大数据的4V特性，提出大数据处理应对策略和变革思维方法研究大数据。3目 录1.计算理论与计算复杂性(1) 可计算性与计算复杂性(2) 计算复杂类(3) 复杂类关系2.大数据可计算性(1) 可（能）解与不可（用）解(2) 大数据可（能）解与不可（用）解问题3.大数据可计算原理(1) 大数据统一化抽象表示：度量空间(2) 大数据的划分(3) 大数据NC-类计算(4) 大数据计算模式4.结论(1) 大数据处理应对策略(2) 变革思维研究大数据1、计算理论与计算复杂性(1) 可计算性与计算复杂性可计算性与计算复杂性可计算性可计算性：对于一个问题，如果存在一个机械机械

3、过程，对给定的输入，能够在有限步内给出结果，则称此问题是可计算的。所谓机械机械的过程，系指在描述计算的某种设备上（例如图灵机上），实施该计算过程，而给出计算结果。计算复杂性计算复杂性：用数学方法研究各类问题计算的复杂性质。也可理解为利用计算机求解问题的难易程度。通常用时空复杂性度量。图灵计算模型图灵计算模型：图灵机就是对一条两端可无限延长的纸带上的0和1执行读写操作，一步一步地改变纸带上的0或1值，经过有限步骤最终得到一个满足预先要求的符号串变换。图灵可计算性图灵可计算性：图灵的研究成果认为“可计算性 图灵可计算性”，即任何在图灵机上可求解的问题都是可计算的！41、计算理论与计算复杂性(2)计

4、算复杂类计算复杂类P类问题类问题：在确定图灵机上多项式（Polynomial）时间内可求解的一类问题。NP类问题类问题：在非确定图灵机上多项式时间内可求解的一类问题（所有NP问题均必须在有限步内是可判定的）。NPC问题问题：对于LNP的问题，且NP类中的每一个L均可在多项式时间内归约（转换）到L，LP L，则称L为NPC（NP完全）的（第一个被证明是NPC问题的是布尔满足性问题：Boolean Satisfiability Problem，SAT）。NPH（难）问题（难）问题：一个问题H称为NP难的，当且仅当存在着一个NPC问题L，L可在多项式时间内图灵归约图灵归约（Turing-Reduct

5、ion）到H。简记之为：L(NPC) T H(NPH)。5NPHNPCNPP当PNP时，NPH问题不能在多项式时间内求解。NPPNPC当PNP时，NPC问题不能在多项式时间内求解。1、计算理论与计算复杂性NC-类问题类问题：在PRAM模型上，使用多项式数目（Polynomial size）的处理器，运行在对数多项式时间（Polylog time）内的一类问题。NC-算法算法：在PRAM模型上，一个求解问题的算法使用了多项式数目的处理器，花费了对数多项式时间，则称此算法为NC-算法。NC-归约归约：对于问题L1和L2，如果存在一个NC-算法，可将L1的求解转换成L2的求解，则称L1可NC-归约到

6、L2，简记为L1 NC L2。P完全（完全（PC）问题）问题：对于LP，且P中的任意L均可NC-归约到L，则称L是P完全的。6PNCPC当PNC时，PC问题不能在多项式时间内求解。1、计算理论与计算复杂性(3)复杂类关系复杂类关系串行空间与并行时间关系Sequential-PSPACE = Parallel-PTIME复杂类包含关系NC P NP PSPACE EXPTIME EXPSPACE7NCNCP PNPNPPSPACEPSPACEEXPSPACEEXPSPACEEXPTIMEEXPTIME2、大数据可计算性(1)可（能）解（可（能）解（Tractable）与不可（用）解（）与不可（用

7、）解（Intractable）可（能）解可（能）解（Tractable: meaning “easily managed” ）问题问题：经典定义是在多项式时多项式时间间内可以解决的问题。不可（用）解不可（用）解（Intractable）问题问题：系指理论上能够解（在无限制时间内，have no limits），但实际上求解时间太长而无法用的问题。因此缺乏多项式时间缺乏多项式时间解的问题被视为不可（用）解的问题。完全问题不可解性：完全问题不可解性：在PNP时，NPC问题是不可（用）解的问题；在PNC时，PC问题是不可（用）解的问题。(2)大数据可（能）解与不可（用）解问题大数据可（能）解与不可（

8、用）解问题在大数据时有些问题是可（能）解的，例如布尔选择查询；但很多问题是不可（能）解的，例如图的宽度优先搜索2 （是P完全的）。在大数据时，传统的可（能）解问题，可能成为不可（用）解问题：例如采用速度可达6Gbps的快速硬盘，线性扫描1EB（E=1018字节）的数据，这本是线性复杂度的可（能）解问题，但实际需要长达5.28年时间，这就变成了不可（用）解问题了。大数据查询类可（能）解问题（大数据查询类可（能）解问题（Wenfei Fan）对于数据库D中的查询Q，如果存在着一个多项式时间PTIME的预处理函数，使得D= (D)，即将D分解成多项式数目个D，在对数多项式时间（Polylogarit

9、hmic Time）内可完成对D的并行查询，这就是所谓的大数据查询类的可（能）解问题。在大数据时，串行多项式时间的算法所需的时间太长而不实用，变成不可解的了；但在并行NC类计算时，因计算时间是对数多项式的，所以在大数据时，NC类计算仍是可解的。8(1) 大数据统一化抽象表示：度量空间大数据统一化抽象表示：度量空间距离和度量距离和度量：在数学上，度量空间是一个集合，集合中的元素之间的距离距离（Distance）叫做度量度量（Metric）。度量与度量空间度量与度量空间：设X为非空集合，d: X X R，(x, y) d(x, y)为映射，如果x,y,zX满足： d(x, y) = d(y, x)

10、（对称性）； 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间的距离。度量空间的坐标化度量空间的坐标化选择支撑点：令（X, d）是一个度量空间，S = xi|xiX, i=1,2,n是X中的一个数据集，S X；在S中选择k个支撑点（Pivots），P=pj|j = 1,2,k， P S。将数据集S映射到k维实数空间：M Rk : IP,d(x) = (d(x,p1), d(x,p2), , d(x,p

11、k), xS其中d(x,pi)是x到pi的距离。这样，度量空间M中数据集S的元素xi都赋予了坐标。 注：支撑点应选择得使支撑点间的距离要足够远，同时其应与其余点的距离亦足够远。3、大数据可计算原理93、大数据可计算原理(2) 大数据的划分大数据的划分在度量空间中，我们可按数据到支撑点的远近距离进行如下在度量空间中，我们可按数据到支撑点的远近距离进行如下3种划分种划分1) 超平面（超平面（Hyper-plane）划分）划分超平面树（超平面树（General Hyper-plane Tree，GHT）：超平面划分的基本形式）：超平面划分的基本形式 选择中心点C1和C2； 划一超平面L（将C1和C2

12、的连线垂直平分）； 数据按距离C1和C2的远近划分之。10C1C2L Left of LRight of LC1,C2 0 x=d(C1, xi)y=d(C2, xi)L: y = x 度量空间度量空间 划分树逻辑结构划分树逻辑结构 支撑点空间支撑点空间3、大数据可计算原理SAT(Spatial Approximation Tree) 在GHT的基础上，使用多个中心点 以中心点形成的Voronoi 图进行数据划分11C1, C2, , CnCell of C1Cell of C2Cell of CnC1C6C5C4C3C2C7C8 度量空间度量空间 划分树逻辑结构划分树逻辑结构 高维的支撑点空

13、间高维的支撑点空间3、大数据可计算原理完全完全超平面树超平面树(Complete General Hyper-plane Tree)令d1, d2表示数据到C1, C2的距离，GHT的划分边界为d1-d2 =0扩展GHT，充分利用d1, d2所包含信息：采用多个不同的截距： d1-d2 =Hi，即双曲线划分考虑变量d1+d2： d1+d2 =Ei，即椭圆划分12C1C2 度量空间度量空间 支撑点空间支撑点空间d1=d(C1, xi)d2=d(C2, xi)3、大数据可计算原理2）有利点（）有利点（Vantage Point）划分）划分有利点树有利点树(Vantange Point Tree,

14、VPT)：有利点划分的基本形式：有利点划分的基本形式 选择有利点VP1，以VP1为圆心、R1为半径画圆； 数据按位于圆内、外划分之； 再从圆内、外分别选择有利点VP21、VP22，分别以R21和R22为圆心画圆。13 d(VP1, x)R1d(VP1, x)R1VP1,R1 d(VP22, x)R22d(VP22, x)R22VP22,R22 VP21,R21 R22 R1 VP1R21VP21VP22qrR1d(VP1, x) 度量空间度量空间 划分树逻辑结构划分树逻辑结构 支撑点空间支撑点空间3、大数据可计算原理多有利点树多有利点树(Multiple Vantage Point Tree,

15、 MVPT)扩充VPT： 采用多个有利点 每个有利点定义多个半径进行数据划分14VP1VP2d(VP1, x)d(VP2, x) 度量空间度量空间 支撑点空间支撑点空间3、大数据可计算原理3) 包络球（包络球（Bounding Sphere）划分）划分 选择中心点C1，以其为圆心、R(C1)为半径画一圆，包含了所有数据； 在上述圆内另选中心点C2、C3，再以其为圆心，以R(C2)和R(C3)为半径画圆，将数据划分成两部分；此两圆均在以C1为圆心的圆内，且所有点均在两圆内； 因为以C2、C3为圆心的圆是从以C1为圆心的圆衍生出来的，划分可能重叠是其明显缺点。15C1C2C3C1,R(C1) C2

16、,R(C2) C3,R(C3) 3、大数据可计算原理(3) 大数据大数据NC-类计算类计算1) NC计算时空复杂度计算时空复杂度并行化所瞄准的问题是具有W(n)=多项式求解时间的P类问题。并行计算的目标是降低求解问题的时间，针对P类问题的并行化，应将其求解时间T(n)减少到低于多项式时间（例如对数多项式时间）。根据P(n)T(n)W(n)，当W(n)为多项式和T(n)低于多项式时，P(n)应选择为多项式的。2) NC类计算类计算并非所有P类问题均可有效地在并行机上求解，其中NC类问题（NC P）被认为能有效地在并行机上求解：它使用了P(n)=多项式数目处理器，T(n)=对数多项式求解时间。常见

17、有NC类问题包括：整数、运算；矩阵运算；前缀计算；选择和排序；图的双连通、连通片、极大匹配；串匹配；计算几何中的一些问题等。许多NC类问题是成本最优的，例如并行扫描T(n)=O(logn)，P(n)=n/logn，W(n)=O(n)；有些成本最优的NC类算法是超快的，例如并行字符串匹配算法T(n)=O(loglogn)，P(n)=n/logn。注：“NC类”一词系由Cook杜撰的，它源于研究均衡电路的Nick Pipenger。163、大数据可计算原理3) P类问题的并行化类问题的并行化P中的有些问题（例如MC2上前缀计算）其并行求解时间是亚线性的（T(n)=O(nx), 0 x1），这类能被

18、并行化的P类问题不在NC类中。例如当n0.5109时，n log3n，此类亚线性的并行算法可能比NC类算法还要快。P中的有些问题具有“固有（天然）的串行性”，例如P完全问题，它不能通过并行显著加速，所以被认为是“难并行化的问题”。常见的P完全问题包括：电路值问题；线性不等式问题；有序深度优先搜索问题；最大流问题；计算几何的凸壳问题等。4) 大数据大数据NC类计算类计算NC类与类与PRAM模型关系模型关系：定义EREWk、CREWk和CRCWk分别由使用多项式数目的处理器、运行时间为O(logkn)对数多项式的并行计算模型PRAM-EREW、PRAM-CREW和PRAM-CRCW可计算的一类函数

19、，它们之间关系如下：NCk EREWk CREWk CRCWk NCk+1大数据大数据NC-类计算类计算：在PRAM模型上，首先将大数据集D划分成多项式数目个子集Di(i=1,2,Polynomial Size)；然后对Di在对数多项式时间（Polylogarithmic time）内施行并行处理。如果上述步骤证明是可行的，则称此类数据计算为NC-类计算。173、大数据可计算原理在小数据时：在小数据时：NC类计算采用巨量处理器（高阶多项式数目个），能快速（低阶对数多项式时间，数秒之内）求解中等大小规模的问题（几十万个输入）。在大数据时：在大数据时：NC类计算面对大规模问题（数百万以上个输入）常

20、采用中等大小数目的处理器（低阶多项式，线性或亚线性数目个）进行很快（高阶对数多项式时间）求解。(4)大数据计算模式大数据计算模式基于MR的流计算：首先把流式数据按到达时间的先后形成一些小的静态数据；然后定期启动MR施行微批处理计算。流计算：流计算是一种易于开发并行性的计算机编程范例，由一组流式的数据和在流数据单元上的一系列操作所组成，编译工具很容易自动优化,在传统的DSP或GPU中广泛应用。增量计算：它仅对变化的输入数据施行重新计算，以节省全部数据计算时间。增量计算预先定义好能被单独处理的最小变化单元，当输入数据在变化区间内，对需要再计算的相关数据元素施行重新计算，以节省计算时间。18小数据小数据大数据大数据处理器数目高阶多项式低阶多项式（线性、亚线性）计算时间低阶对数多项式高阶对数多项式可解性P类问题会成为不可解的（PTime）NC类问题会是可解的（Logtime）4、结论(1) 大数据处理应对策略大数据处理应对策略大容量大容量（Volume）：主要体现数据存储量大和计算量大。为此，要采用采用并行于分布式处理系统架构并行于分布式处理系统架构（Parallel & Distributed Processing System Architecture）。快速率快速率（Velocity）：主要指数据入/出速度快，更新和增长速度快，数据传