KIT | KIT-Bibliothek | Impressum | Datenschutz

Communication efficient algorithms for fundamental big data problems

Sanders, Peter ORCID iD icon 1; Schlag, Sebastian 1; Muller, Ingo 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


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.

DOI: 10.1109/BigData.2013.6691549
Zitationen: 21
Zitationen: 17
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsmonat/-jahr 10.2013
Sprache Englisch
Identifikator ISBN: 978-1-4799-1292-6
KITopen-ID: 1000097565
HGF-Programm 46.12.02 (POF III, LK 01) Data Activities
Erschienen in Proceedings of the 2013 IEEE International Conference on Big Data, Santa Clara, CA, October 6-9, 2013
Verlag Institute of Electrical and Electronics Engineers (IEEE)
Seiten 15–23
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page