大数据计算理论基础201405陈国良

大数据计算理论基础

ComputingTheory

FoundationsofBigData2014年5月陈国良，陆克中，毛睿深圳大学计算机与软件学院2摘要：

大数据是当前IT信息技术研究和应用的热点。但是，目前的研究多集中于系统和应用层面，理论基础方面的探讨相对较少。本文从计算机科学讲起，以计算复杂性理论为基础，着重研究大数据的计算复杂性（ComputationalComplexity）和大数据本身的复杂性（DataComplexity）：前者包括大数据统一化抽象表示；大数据划分技术；大数据NC类计算理论；大数据计算模式等。后者包括大数据复杂性表示；大数据复杂性度量；大数据复杂性模型等。最后，根据大数据的4V特性，提出大数据处理应对策略和变革思维方法研究大数据。3目录计算机科学与计算问题分类计算机科学的经典定义计算机科学定义的数学解释计算机科学的历史演变计算问题分类计算理论可计算性与计算复杂性图灵计算模型串行复杂计算类：P，NP，NPC，NPH并行复杂计算类：NC，PC归约大数据可计算性可(能)解与不可(用)解问题大数据可(能)解与不可(用)解问题数据库查询类的可(能)解与不可(用)解问题度量空间：大数据统一化抽象表示大数据统一化抽象表示的基本思路距离和度量的概念数据的度量空间表示度量空间举例支撑点空间：度量空间的坐标化度量空间的坐标化支撑点空间的定义举例完全支撑点空间数据的划分技术超平面划分有利点划分包络球划分大数据NC计算理论NCi类的电路定义NCi类的层次大数据NC-类计算大数据计算模式基于MR的流计算流计算实例研究：Storm流计算增量计算大数据的复杂性大数据复杂性表示大数据复杂性度量大计算复杂性模型结论大数据处理应对策略变革思维研究大数据1、计算机科学与计算问题分类

41、计算机科学与计算问题分类计算机科学的历史演变计算机科学的形式化研究起源于数学的基础研究：Cantor的集合论与Russell悖论：数学家们在集合论中发现了逻辑矛盾LetR={x|x∉x}thenR∈R↔R∉RHilbert纲领：即在通用的形式逻辑系统中可以机械地判定任何给定命题的真伪（完备性），证明每一形式系统的相容性，从而导出全部数学的相容性。Gödel提出了形式系统的不完备性，它不能穷举全部数学命题，任何足够强的相容形式系统中均存在着该系统中所不能判定真伪的命题。Hilbert纲领的失败启发人们不要花费大量精力去证明那些不能判定的问题，而应集中精力研究“可计算求解性”问题。在此思想指引下，A.M.Turing从计算一个数的一般过程入手，将可计算性概念与机械程序的执行过程统一起来，此即有名的图灵计算模型。51、计算机科学与计算问题分类计算问题分类6计算问题不可判定问题可判定问题难解(不可能)解问题易解(可解，多项式时间)问题不可近似问题可近似问题大数据可解(BD-Tractable)问题大数据不可解(BD-Intractable)问题大数据不可近似问题大数据可近似问题2、计算理论（Theoryofcomputation）可计算性与计算复杂性可计算性：对于一个问题，如果存在一个机械过程，对给定的输入，能够在有限步内给出结果，则称此问题是可计算的。所谓机械的过程，系指在描述计算的某种设备上，实施该计算过程，而给出计算结果。可计算性特征：确定性：对相同的初始输入产生相同的输出。有限性：在有限设备上能在有限时间内求解。构造性：每一计算过程的执行都是“机械的”或“构造性的”。数学描述性：计算的过程可以用严格的数学进行描述。停机问题：对于任意的图灵机和输入，是否存在一个算法，用于判定图灵机在接收初始输入后可到达停机状态。若能找到此算法，停机问题可解，否则不可解。计算复杂性：用数学方法研究各类问题计算的复杂性质。也可理解为利用计算机求解问题的难易程度。算法复杂性：算法复杂性是对算法效率的度量，系指运行算法所耗费的时间和空间（存储量）。72、计算理论（Theoryofcomputation）图灵计算模型将可计算性概念与机械程序的执行过程统一起来，确认任一机械执行过程均可在一台机器（即图灵机）上实现。图灵机：图灵机就是对一条两端可无限延长的纸带上的0和1执行操作，一步一步地改变纸带上的0或1值，经此有限步骤最终得到一个满足预先要求的符号串变换。图灵机的作用：图灵的研究成果认为“可计算性＝图灵可计算性”，即任何在图灵机上可求解的问题都是可计算的！82、计算理论（Theoryofcomputation）串行计算类：P，NP，NPC，NPHP类问题：在确定图灵机上多项式（Polynomial）时间内可求解的一类问题。NP类问题：在非确定图灵机上多项式时间内可求解的一类问题（所有NP问题均必须在有限步内是可判定的）。NPC问题：对于L∈NP的问题，且NP类中的每一个L’均可在多项式时间内归约（转换）到L，L’≤PL，则称L为NPC（NP完全）的（第一个被证明是NPC问题的是布尔满足性问题：BooleanSatisfiabilityProblem，SAT）。NPH（难）问题：一个问题H称为NP难的，当且仅当存在着一个NPC问题L，L可在多项式时间内图灵归约（Turing-Reduction）到H。简记之为：L(NPC)

≤T

H(NPH)

（例如判定停机问题是NPH问题）。9NPHNPCNPP

NPPNPC当P≠NP时，NPH问题不能在多项式时间内求解。当P≠NP时，NPC问题不能在多项式时间内求解。注：①所有NPC问题均能在多项式时间内归约到NPH而求解之。

②NPC中的每个元素均必须是NP中的元素。

③NPH问题中不一定必须是NP中的元素。2、计算理论（Theoryofcomputation）并行计算类：NC，PCNC-类问题：在PRAM模型上，使用多项式数目（Polynomialsize）的处理器，运行在对数多项式时间（Polylogtime）内的一类问题。（此类问题包括整数加法、乘法、除法，矩阵乘，行列式，找最大匹配（RNC问题）等）。NC-算法：在PRAM模型上，一个求解问题的算法使用了多项式数目的处理器，花费了对数多项式时间，则称此算法为NC-算法。NC-归约形式定义：对于问题L1和L2，如果存在一个NC-算法，可将L1的求解转换成L2的求解，则称L1可NC-归约到L2，简记为L1

≤NCL2。P完全（PC）问题：对于L∈P，且P中的任意L’均可NC-归约到L，则称L是P完全的。10PNCPC

当P≠NC时，PC问题不能在多项式时间内求解。2、计算理论（Theoryofcomputation）

113、大数据可计算性可（能）解（Tractable）与不可（用）解（Intractable）可（能）解（Tractable:meaning“easilymanaged”）问题：经典定义是在多项式时间内可以解决的问题。不可（用）解（Intractable）问题：系指理论上能够解（在无限长时间内），但实际上求解时间太长而无法用的问题。因此缺乏多项式时间解的问题被视为不可（用）解的问题。完全问题不可解性：在P≠NP时，NPC问题是不可（用）解的问题；在P≠NC时，PC问题是不可（用）解的问题。大数据可（能）解与不可（用）解问题在大数据时有些问题是可（能）解的，例如布尔选择查询（在数据集D中，是否存在某一列的元组值为指定值，在B+树[1]索引上可在O(log(|D|))时间内解决）；但很多问题是不可（能）解的，例如图的宽度优先搜索[2]（是P完全的）。在大数据时，传统的可（能）解问题，可能成为不可（用）解问题：例如采用速度可达6Gbps的快速硬盘，线性扫描1EB（E=1018字节）的数据，这本是线性复杂度的可（能）解问题，但实际需要长达5.28年时间，这就变成了不可（用）解问题了。12注1：B+树是B树的变形，关键字与数据值（键/值）成对存储在树的同一节点中，其中所有数据值存在树的叶节点中，只将关键字与子女节点的指针存在树的内节点中。注2：宽度优先搜索（BFS：Breadth-First-Search）从根节点开始，沿着树的宽度遍历其所有子节点，这些子节点被加入一个先进先出FIFO的队列中。然后从FIFO队列中取出先进入的子节点，重复上述宽度遍历过程，直到所有节点均被访问过。BFS问题是个P完全问题。

3、大数据可计算性13PTIME(ΠTQ)BD-IntractableBD-Tractable(ΠTQ0)P(ΠTQ)NCPCΠTQ0大数据统一化抽象表示的基本思路类型和距离函数：这是数据表示的两个基本参数，其中类型可以是一维数据、多维数据、字符串、图片等；对于复杂数据，除了精确匹配以外，更多要以距离衡量彼此的相似性。多维数据作为统一化抽象表示的局限性：使用多维数据作为统一表示时，数据本身必须能表示成特征向量（FeatureVector），且数据间的相似性用特征向量的欧式距离等衡量。但对有些数据和应用无法满足上述条件，例如文本字符串往往使用编辑距离，蛋白质序列只能使用比对（Alignment）距离，图片等只能使用Hausdorff距离等等。统一化抽象表示：针对上述情况，可将Variety数据抽象成统一的数据类型，将Variety距离抽象成统一的距离函数，此即下述的度量空间表示。4、度量空间：大数据统一化抽象表示14

4、度量空间：大数据统一化抽象表示15度量空间拓扑与拓扑空间：如果非空集合X的子集族τ，它满足以下条件：Ø和X在τ中；τ的任意子族之元素的“并”（∪）在τ中；τ的任意子族之元素的“交”（∩）在τ中。则称τ为X上的一个拓扑（Topology），偶对（X,τ）称为X上的一个拓扑空间（TopologySpace）。度量与度量空间：设X为非空集合，d:X×X

→R，(x,y)→d(x,y)为映射，如果∀x,y,z∈X满足：

d(x,y)=d(y,x)（对称性）；

d(x,y)≥0和d(x,y)=0iffx=y（半正定性）；

d(x,z)≤d(x,y)+d(y,z)（三角不等式）。则称d为X上的一个度量（距离），偶对（X,d）为度量空间，d(x,y)称为是x与y间的距离。注：度量空间是一类特殊的拓扑空间；而n维欧氏空间是一类特殊的度量空间。4、度量空间：大数据统一化抽象表示16度量空间举例字符串：数据类型可用文本类型（如ASCII码等）数组表示；其距离函数可用编辑距离（EditDistance）表示：即将两个字符串相互转换所需的编辑动作（插入、删除、替换等）的总开销。蛋白质序列：数据类型可用字节（蛋白质的序列由20种氨基酸表示，每一种氨基酸用一个字节表示）数组表示；其距离函数可用全局比对（GlobalAlignment）表示：即加权的编辑距离。基因序列：数据类型可用字节（基因序列由4种碱基表示，每一种碱基用一个字节表示）数组表示；其距离函数可用海明距离（HammingDistance：对应位不相同的数目）表示。图片：数据类型可用长度为66的实数数组表示，用以表征图片的结构、纹理、颜色等特征；其距离函数可用“结构距离（欧几里得）+纹理距离（欧几里得）+颜色距离（曼哈顿：Σ|xi-yi|）”三种距离的代数和表示。4、度量空间：大数据统一化抽象表示17度量空间的坐标化度量空间的问题：度量空间是个数据集合，集合中的诸元素没有坐标，这样就无法对集合中的诸元素按远近施行划分（Partitioning）操作。约定：令（M,d）是一个度量空间，S={xi|xi∈M,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),…,d(x,pk)),x∈S

其中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)),x∈S}解释：支撑点空间就是度量空间中元素集合S在多维实数空间中的映象，其每个元素的各个坐标是相应的度量空间中数据到各个支撑点的距离。5、支撑点空间：度量空间的坐标化18

5、支撑点空间：度量空间的坐标化19编号原坐标(x,y)映射后坐标(d(A,p1),d(A,p2))1(0,0)(0,1.414)2(0,1)(1,1)3(1,1)(1.414,0)4(1,0)(1,1)5(0.5,0.5)(0.707,0.707)支撑点A支撑点B支撑点C初始值012101210123ABCd(x,A)d(x,B)d(x,C)x完全支撑点空间把所有的点都选为支撑点：P=S，M→Rn

IS,d(S)={xS|xS

=IS,d(x)=(d(x,x1),d(x,x2),…,d(x,xk)),x∈S}5、支撑点空间：度量空间的坐标化20x1x2……xnx1d(x1,x1)d(x1,x2)……d(x1,xn)x2d(x2,x1)d(x2,x2)……d(x2,xn)………………………………………………xnd(xn,x1)d(xn,x2)……d(xn,xn)6、数据划分技术在度量空间中，我们可按数据到支撑点的远近距离进行如下3种划分超平面（Hyper-plane）划分选择中心点C1和C2；划一超平面L（将C1和C2的连线垂直平分）；数据按距离C1和C2的远近划分之。21C1C2LLeftofLRightofLC1,C2

6、数据划分技术有利点（VantagePoint）划分选择有利点VP1，以VP1为圆心、R1为半径画圆；数据按位于圆内、外划分之；再从圆内、外分别选择有利点VP21、VP22，分别以R21和R22为圆心画圆。22d(VP1,x)≤R1d(VP1,x)>R1VP1,R1

d(VP22,x)≤R22d(VP22,x)>R22VP22,R22

……VP21,R21

R22

R1

VP1R21VP21VP22qr6、数据划分技术包络球（BoundingSphere）划分选择中心点C1，以其为圆心、R(C1)为半径画一圆，包含了所有数据；在上述圆内另选中心点C2、C3，再以其为圆心，以R(C2)和R(C3)为半径画圆，将数据划分成两部分；此两圆均在以C1为圆心的圆内，且所有点均在两圆内；因为以C2、C3为圆心的圆是从以C1为圆心的圆衍生出来的，划分可能重叠是其明显缺点。23C1C2C3C1,R(C1)C2,R(C2)

C3,R(C3)

7、大数据NC计算理论NCi类（Nick’sClass）的电路定义：NCi类均衡电路定义：NCi可定义为可计算的一组函数，可由一簇均衡电路输出的一组布尔函数值表示，其中电路有多项式数目个门（至多两输入），深度为O(login)，i≥1。（电路越深，表示电路的级数越多）RNC（RandomizedNC）类概率电路定义：它是由一簇概率电路可计算的一组函数，此电路中除了通常的门以外，还有一个具有随机概率“正确”与“错误”的输出门，电路计算正确的概率至少是1/2。NC类的层次NCi类层次可定义如下：NC1

⊆

NC2

⊆

…⊆

NCi，NC类一般定义：NC=∪k≥1NCk247、大数据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,···,PolynomialSize)；然后对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-BatchMR：首先把流式数据按到达时间的先后形成一些小的静态数据；然后定期启动MR施行微批处理计算。流水MR：通过作业内或作业间数据传输的流水线，实现OnlineHadoop，即实现了Map到Reduce之间数据的Pipeline，使得Map产生部分数据后就可送到Reduce端，以便Reduce可提前或定期计算。动态加入输入：数据未完全到位时，提前向运行中的作业加入新的输入数据，这样将数据流切成较小的datasegment，可大大减少处理大作业的等待时间。268、大数据计算模式流计算（StreamComputing）定义：流处理是一种易于开发并行性的计算机编程范例，勿需显式管理计算的任务调度、同步和通信等。组成：流处理系由一组流式的数据和在流数据单元上的一系列操作（称之为KernelFunction）所组成。其中KernelFunction通常是流水线式的。优点：因为Kernel和Stream抽象揭示了数据的相关性和使用数据的局部性，所以编译工具很容易自动优化。流处理在传统的DSP或GPU中广泛应用。注释：早在上世纪80年代开发的数据流语言SISAL(StreamandInteractioninSingleAssignmentLanguage)就是一种流处理语言。278、大数据计算模式实例研究：Storm流计算Storm系由函数式程序设计语言开发的。Storm系统架构：系统采用主-从结构，由三种节点组成：主节点（类似Hadoop的Jobtracker）统管全局，负责接收作业，分配任务；监控节点（类似Hadoop的Tasktracker）负责接收任务，起/停工作进程；工作节点执行进程，负责处理数据。Storm计算模型：该模型系由Spout（负责产生事件Event）和Bolt（负责接收并处理事件）组成。事件Event流会在Spout和Bolt之间动态流动，以计算出所需的结果。Storm主要优点：Storm具有Scale-out能力，计算所需的各种状态均是自满足的，可以简单地加入新的计算节点以满足系统计算能力的提升；另外，Storm可以维持分布式计算涉及到的多进程间通信、同步和正确性依赖关系，确保信息会被完整处理。288、大数据计算模式增量计算（IncrementalComputing）定义：增量计算系指仅对变化的输入数据施行重新计算，以节省全部数据计算时间。增量计算前提：增量计算需要预先定义好能被单独处理的最小变化单元（SmallestUnitofChange）。如果一个变化在定义好的最小变化单元区间（Scope）内，则可施行增量计算。增量计算的实现：构造所有需要再计算的数据元素的相关图（DependencyGraph）；需要修改的数据元素可由相关图的传递闭包（TransitiveClosure）给出。也就是说，如果从一变化的元素到另一元素存在着一条路径，则后者将要被修改。应用实例：采用增量计算处理渗流（过滤）器（Percolator:IncrementalProcessingUsingDistributedTransactions），获得比采用MR方法更好的性能，其延迟时间改善了好几个数量级（OSDI,2010）。299、大数据的复杂性大数据复杂性表示探索大数据的本征特征（IntrinsicProperty）：寻找大数据间的本征结构（IntrinsicStructure）；研究大数据间的跨时空连接模式（ConnectionPatterns）。量化大数据的特征表示：用抽样、抽象和特征提取方法量化特征数据；将量化的特征数据表示成高维稀疏特征矩阵。大数据复杂性度量计算语义距离：通过上下文语义分析计算语义距离；使用测度函数（如欧式距离等）和基于机器学习模型度量语义距离。复杂性度量：选取度量参数，包括数据的多维度性（D）、多样性（S）、不确定性（U）和间断性（I）等；构建复杂性函数f(D,S,U,I)=aD+bS+cU+dI。309、大数据复杂性大数据复杂性模型（BenjaminW.Wah）基于结构的概率图模型：概率图模型（ProbabilisticGraphicalModel）是一类利用图形模式（GraphicalModel）表达基于概率相关关系的模型。在此模型中表达变量（数据）之间的关系时，通常使用了贝叶斯网络（BayesianNetwork）和马尔科夫随机场（MarkovRandomField），其主要区别