通信工程文献翻译——摘要---大数据应用程序通常存储或获取分布在由网络连接的许多计算机上的数据。由于网络通常比机器的本地存储器慢，因此以不会发生太多通信的方式处理数据是至关重要的。实际上，只有输入大小中的亚线性的通信量可以是可负担的。我们认为这个研究方向值得更深入的研究。我们给出几个基本算法问题的例子，其中具有子线性通信量的平凡算法是可能的。我们的主要技术贡献是关于分布式布隆过滤器替换，重复检测和数据库连接的几个相关结果。作为一个非常不同的技术家族的例子，我们讨论低维的线性规划。

关键词算法: 通信量;重复检测;数据库;加入;线性规划;

I.引言

高性能计算硬件的开发有一个持续的趋势，使计算几乎是免费的，而通信越来越成为大多数非平凡计算的瓶颈。这对于距离和相应的能量消耗最高的存储器/通信层级的最高级别尤其如此。例如，Borkar [1]认为，只要通信能力（对分宽度）与连接的子系统中的计算量进行高度亚线性比较，一个exascale计算机只能是成本有效的。对于在输入数据元素之间具有非平凡交互的大数据应用，这意味着在通信层次结构的最高级别上所需的通信量对于整体性能是决定性的。因此，我们提出这个问题作为研究大数据算法的一个焦点。在本文中，我们通过许多相关的算法来说明这一点，其涉及在网络或集群计算机的p个机器（处理元件-PE）上分布的每个大小为u比特的n个元素的基本算法问题。

我们从第二部分的基本定义和结果开始。我们的第一个主要贡献是在第三节中介绍的分布式（dSBF）和复制（rSBF）压缩单镜头Bloom过滤器。 dSBF允许具有假阳性概率f +的近似成员查询大致log（p / f +）上的设备的每个元素并查询分布在所有PE上。当对适度大小的集合进行大量查询时，rSBF是好的。在这种情况下，需要nlog（1 / f +）比特的通信量。

在第四节中，我们使用dSBF进行分布式重复检测。使用多次通过，通信量对对象大小的依赖可以做成双对数。第五节将这些技术概括为处理数据库连接，根据连接关系的相对大小仔细优化数据结构的参数和选择。我们的解决方案大致比以前的方法使用更少......

Abstract—Big Data applications often store or obtain their data distributed over many computers connected by a network.Since the network is usually slower than the local memory of the machines, it is crucial to process the data in such a way that not too much communication takes place. Indeed,only communication volume sublinear in the input size may be affordable. We believe that this direction of research deserves more intensive study. We give examples for several fundamental algorithmic problems where nontrivial algorithms with sublinear communication volume are possible. Our main technical contribution are several related results on distributed Bloom filter replacements, duplicate detection, and data base join. As an example of a very different family of techniques,

we discuss linear programming in low dimensions.

Keywords-algorithm; communication volume; duplicate detection; data base; join; linear programming;

I. INTRODUCTION

The development of high performance computing hardware has a continuing tendency to make computation almost free while communication increasingly becomes the bottleneck for most nontrivial computations. This is particularly true for the highest level of the memory/communication hierarchy where distances and corresponding energy consumption are highest. For example, Borkar [1] argues that an exascale computer could only be cost effective if the communication capabilities (bisection width) scale highly sublinearly with the amount of computation done in the connected subsystems. For Big Data applications with nontrivial interactions between the input data elements, this means that the required communication volume at the highest level of the communication hierarchy is decisive for the overall performance. We therefore propose this issue as one focus for the study of algorithms for Big Data. In this paper we exemplify this by a number of related algorithms......