2013/10/01 by Peter Sanders, Sebastian Schlag, Ingo Müller · 1 citation
Computer Science · #Caching and Content Delivery #Advanced Data Storage Technologies #Cloud Computing and Resource Management #Computer science #Big data #Algorithm #Data mining
paper · doi:10.1109/bigdata.2013.6691549
openalex publication_date 2013/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.