英文文献译文

1、英文文献译文第12章Bigdata的一种新的计算模型摘要：自从几年前BigData一直是一个热门词汇。但是，什么是完全对应的（理论值）的计算机模型？可以做些什么并且不能以这样的模式来完成？这些都要求答案的问题。最近，一个模型提出通过模拟受限制，以解决这个问题版本PRAM模型。在本文中，我们提出了所谓的理论模型主/从多处理器（MSM简称），这是非常类似于一个实际使用MapReduce的但有额外的限制有关BigData系统处理。此模型捕获一些最重要的属性的实用的粗粒度多处理器（CGM）模型（而不是PRAM）。该在这样的主/从模式最重要的思想是：（1）即使主只能在任何给定访问所有的数据的一小部分在其

2、从属处理器时间，（2）大量的从节点之间的数据传输的被认为是不可能或成本过高，和（3）一个额外的从属处理器，与数据一起它携带，可以很容易地集成到系统支持的可扩展性。在这样的一个模型捕获实际的MapReduce的最重要的特征系统，一些标准问题，如排序，成为难以解决的问题。然后，我们提出了一种自适应MSM模型，其中主节点仍具有有限的工作内存，但大中专storage.We演示如何这两款车型的MSM可以用来解决一些基本问题，当数据量是巨大的。12.1简介 自从几年前BigData一直是一个热门词汇。几乎在每一个行业，我们听说有人在谈论BigData，一个突出的例子就是庞大的数据allWalmart交易量

3、，或搜索查询谷歌已经处理，或视频监控系统监控所有的道路交叉口在纽约市，所有只是在一个单一的一天。在不同的国家资助机构设立研究项目针对不同地区处理BigData。总之，BigData在那里并且将改变我们lives.We需要正确地处理它们，如果没有，它们将变得我们的负担。 尽管如此，似乎不存在一个普遍接受的模型BigData计算。由于并行一定程度必须被用来处理BigData，让我们先简要回顾一下已知的并行计算模型（2）。最流行的并行模型是PRAM（PRAM模型）这是提出了20世纪70年代，但不幸的是一个通用的实用PRAM从未建，虽然最近有一些努力做到这一点17。另一方面，出现了大量的基于PRAM算

4、法的研究，见11，13。但在PRAM算法理论和实践工作的系统之间的差距仍然巨大。见此差距，在20世纪90年代初，的LogP 3和BSP（散装同步并行）模型16提出，在本质上有一个分布式的内存，整体异步并行机。在90年代初期，粗粒度多处理器（CGM），它可以被看作是和的LogP BSP的受限版本，提出了建议。总之，CGM是一组处理器中，每个有足够的本地存储器和足够的计算能力，并且该同步是通过点对点通信。事实上，两个实际系统，PVM-平行的虚拟机，和MPI消息传递接口，被实现并通过在并行计算的专业人员广泛使用。事实上，CGM算法两个特殊的问题已发表在科学期刊5,6。然而，CGM需要实时应用的高通信

5、带宽和系统连接，因此，是不是太昂贵，或者不是真正的实际应用的许多商业应用中，尤其是当数据量是巨大的，当一个全连接网络不能保证。出人意料的是，主/从模式，calledMapReduce，于1990年底通过由谷歌，成为大规模网页搜索，几乎普遍4。的MapReduce的思想如下。 （1）主节点的地图和把一个任务分解成几个部分，并将它们分配给它的从属节点（图进程），以及（2）从节点完成子任务和主节点为结合返回结果进一步计算（缩小的过程）。注意，此过程可在多轮来完成，并可以递归进行，即，从节点可以进一步划分任务到一组子从节点。在这种模式下，通信只是一个主节点和它的奴隶之间，奴隶不能直接彼此通信。在图12

6、.1，P1是从主节点节点P2; P3和P4;递归P4是P5和P6主节点。一MapReduce的系统的最显著特性，从应用的角度来看，是可扩展性。即，当一个有一个额外的从属节点可用的（有一些相关的数据一起），很容易将其添加在现有下主，而不改变系统的总体拓扑结构。在图12.1，当节点P7加入作为下P4从属节点，所有其他节点，除了P4，不受影响。对于CGM，一会到新的节点之间加入了一个沟通渠道到所有的现有节点，这是更为昂贵实现。它仍然告诉能做什么和不能使用的MapReduce高效地完成系统。 MapReduce的实际成功主要是搜索和查询侧（见10一个最近的调查）。有了这个动力，在2010年，卡洛夫，苏

7、芮，并提出Vassilvitskii MapReduce的一个模型，它是基于模拟PRAM12的受限版本。在这种模式下，许多图问题可以有效地解决了14。然而，由于这种模式继承了一些PRAM的弊端，我们认为它可能是太强大（或实际成本太高），与任何现有的实际MapReduce的系统相比。图12.1实际的MapReduce系统图12.2主/从多处理器模式打算，而不是PRAM以获得基于的LogP和BSP系统，在本文中，我们提出了一种基于MapReduce的主/从模式多处理器（MSM）来处理大数据集（或BigData）。从使用的MapReduce模型一些现有实际系统抽象，我们假设这个MSM具有主节点M和P

8、从节点S1： S2; ：; SP;此外，主节点M的内部存储器是在同一顺序的那些从属节点。 （在实践中，这意味着它是容易更换的主节点，当它出现故障）。为了能够分析的算法的效率，我们假设每个Si和M具有大小为O（n/ p），其中的一个存储器n是输入的大小。注意，这里p应该不被看作是一个很小的常数。参照图12.2的一个例子。本文安排如下。在第二节。12.2介绍模型。 在教派。 12.3我们展示了如何使用这个模型来解决一些根本性的问题，还留下了一些有待解决的问题。此外，我们展示了这样的一个自适应版本模型。在第二节。 12.4，我们认为纸张。12.2 MSM：主/从模式多处理器在本节中，我们讨论了MSM

9、模型的一些技术方面的问题，特别是但从BigData点的处理。算法复杂的模型MSM下的测量包括#C：通信轮的数量，其中每个循环包括HMASTER，slavei和hslave，马斯特里沟通，可能包括派遣O（N / P）数据，其中n是输入大小和p的量是从节点的数量。T：一次通信中的本地计算成本。D：信息的最大数量的主机和之间交换从一次通信中的节点。该算法的计算复杂度（成本）是O（#CT）。总数该算法的通信成本就是O（#C P（D）。从一些实际的MapReduce系统，如Hadoop的不同，我们假设主节点M和所有从节点具有O（N / P）的本地内部存储器。当数据集很大，例如，在谷歌的所有数据不能被存储

10、在任何单个计算机这个假设是有效的。我们假设整个纸张N P2。另外，在实践中的通信成本高;因此，它很可能是一个实际的算法只允许通信轮小（优选恒定）的编号，并在每一轮的信息量有限是交换。最后一个约束意味着它是硬交换大量数据的一个主节点和从属节点之间。实际上，没有这种限制，可以总是模拟与MSM一个CGM算法，作为之间的通信两（从）节点可以通过主节点来完成。观察1.如果沟通没有限制，那么CGM算法可与MSM系统进行模拟，其中一个点对点通信可以是至多一对hslave，马斯特里和HMASTER，slavei通信的模拟，和广播通信可以在最多一个hslave，马斯特里通信，一个圆HMASTER，slavei通

11、信的模拟。从现在起，我们禁止从节点之间的数据传输。在此假设（也是主节点的有限的工作存储器），我们注意到许多标准的问题变得难以解决，例如，排序存储在p个处理器n个元素。其原因在于减少一步需要完全排序的数据项发送在p回主节点，这是不可能的，除非我们可以存储所有的主节点n个数据项，或者我们允许大量的信息交换。这给了我们以下观察。观察2. MSM系统可以有效地解决大小n，其中的一个问题有通信轮有限数量，并在每轮问题可被划分成p个独立的部分，并在下解各结果大小O（N / P）。以上基本的观察表明，很多算法仿真天真在一个MSM是行不通的。例如，你可以在O.n2 /时间用穷举法的任何固定尺寸解决直径的问题。

12、有计算/通信的n个轮：每一轮主询问从属节点来计算到固定点的最大距离，并始终保持当前最大。当然，轮数，正，将太大。但是，存在一些问题可以有效地利用此MSM模型来解决。对于例如，在谷歌搜索可以模拟最好作为k近邻搜索问题上的MSM（其中，k通常是一个很小的常数），其中只有一个圆形的通信：主节点分配搜索为p从属节点，每个节点的回报在每一个从节点的k最近邻居。然后，这些邻居都返回到主节点，以便它可以结合这些结果来计算k最近邻居在整个系统中，根据查询对象之间的距离和搜索的对象。请注意，在这个阶段的一些结果可能如果被截断返回的p套的部分结果是太大。在下一节中，我们试图解决使用这个几个基本（几何）问题MSM模

13、式。12.3处理大型数据集与MSM在本节中，我们说明了如何使用MSM模式来解决一些基本的当数据量（即，n）是问题巨大。 （我们尽量保持纸整装的，但读者可以参考15有关计算什么几何。）我们假定数据大致存储在相等大小在每个从属节点;然而，我们不承担所存储的数据的任何其它属性，例如，在本地分布式或组织成一些数据结构，后者可以在实践中整流，如在本地建立一些复杂的数据结构不是来自太大的不同定期计算。这个假设是本文的其余部分的关键，我们相信这是实际的，在实践中可能被产生的数据集，维护，并更新以不同的方式与存储在本地。事实上，如果我们允许以任意的方式输入数据集的改组，许多问题可以很容易地通过调整现有的CGM

14、算法求解。例如，如果我们假设主站可以产生一个随机样本并使用样品进行分区和映射的剩余数据到相应的从节点，我们就可以更有效地与随机抽样通过调谐现有的CGM算法解决很多问题，为例如，三维凸包（2D Voronoi图）7，或为线段2D Voronoi图9。事实上，即使在图问题8一些CGM算法，可以在这样大的通信开销的MSM模型进行仿真。但是，我们认为这不适合大多数应用程序在处理BigData，其中，在许多情况下数据被生成和第一存储，但我们不知道我们想从数据来计算直到稍后。出于实际的考虑，我们只允许少数几轮沟通，并尝试绑定的沟通成本尽可能我们可以。由于这个原因，考虑最多的问题，我们只能设计出近似算法。1

15、2.3.1选择很容易地看到，与通信中的一个轮存储在MSM N 1-D取值X的最小值，最大值可以在O.计算（N / P）的时间。每一个从节点只需要进行极端的选择（MIN或MAX）值以及NP返回的值可以在主节点被组合以获得该组X的整体极端（最小或最大）值。我们接下来表明X的k个最小值的选择可以解决有效上的MSM。这里k是不一定是一个很小的常数，否则问题也就容易解决了。定理12.1.给定n个1-D值的集合X，用最小LOGR，N轮通信，共为O（分钟LOGR，N P /）通讯费用，第k的X最小的元素可以在O计算（N / P）分钟LOGR，N）的时间上的MSM具有p从属处理器，其中R是MIN1和MAX1，

16、N = N（1-1 /对之间的距离）被MIN1和MAX1之间元件的数目，MIN1是在最小元素X和MAX1是在p从节点的最低的K-最小元素，分别证明。在步骤2中的本地计算成本显然为O（n / p）的1。的数量。通信轮首先通过为O（log R）为界，在最坏的情况下可能是算法12.11.中号在计算集合X中的最小值分钟2.米分配找到k个最小值到所有从节点S1的任务; ：; SP。3.各硅返回第k值最小XK I; I 2 OE1; P，为M.4. M选择在p之间的最小值从从节点返回的值。让价值最大。事实上，我们可以构造MIN1和MAX1使得之间的点的集合成倍增长，因此该算法将达到每点一个额外的一轮通信。

17、对于实际数据，称该数据是均匀分布或均匀分布在恒定数量簇，它声O(logR )=O(log N)是安全的。开放式问题1.对于选择问题，有没有可能设计一个算法根据与O(n/p)的本地计算成本的MSM和O(log n)轮通信？12.3.2直径任何固定尺寸 定在任何固定维数n点的集合P，内径是在体育两点之间的最大距离如前面所讨论的，如果我们允许的n轮通信，那么问题可以容易地最佳解决。我们讨论如何与几个回合的通信设计的算法。定理12.2给定的n个点中的任何固定尺寸的集合P，与圆O(p)通信成本的沟通和总的，的一个2-近似磷直径可在O(n/p)时间计算上的MSM与对从处理器。在此，目的仅仅是显示MSM模型

18、的应用。12.3.3排序和唯一性元素 在约束下，即使是主节点只能存储数据的O(n/p)量。排序成为上MSM一个难题。事实上，即使相关元素算法12.21.中号选取任意点Q D PS; T和分配寻求所有从从Q上的最大距离的任务节点S1; ：; SP。2.各Si返回的最远点PI; I0; I 2 OE1;磷; I02 OE1; NP到M.3。 M选择从Q上的最远点之间在p从从属节点返回点。唯一性的问题，即，确定是否有两个相等的元素（可能存储在不同的从节点），变得坚硬。我们离开这个作为一个开放问题。开放式问题2.为元素的唯一性问题，有没有一个有效的解决方案下MSM？12.3.4放宽主内存限制在MSM

19、正如我们前面所讨论的，如果一个MSM主节点仅具有一个尺寸O(n/p)，甚至排序问题变得困难。另一方面，如果主节点的尺寸有大小的存储O(n),这是它的所有从站的大致尺寸的节点），则该模型是不现实的（虽然许多问题可以有效地解决了）。在这里，我们试图让模型稍微适应。我们假设主节点具有O(n/p)的（工作）存储器，但具有一些额外的成本二次存储可扩展到主节点，用于存储最终计算结果。我们接下来说明这一自适应模型下解决排序问题的一个简单的例子。我们评价，该自适应模型仍然是从实际的MapReduce模型，如Hadoop的，不同的，其中主节点的（工作）存储器可以比O(n/p)大得多。 如果主节点具有辅助存储其大小开O(n)，则分拣变得可解 - 即使在主级工作存储器仍O(n/p).然后可以在每个节点存储在每个从节点的所有元素