Communication efficient algorithms for fundamental big data problems

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.