KIT | KIT-Bibliothek | Impressum | Datenschutz

Communication efficient algorithms for fundamental big data problems

Sanders, Peter; Schlag, Sebastian; Muller, Ingo

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.



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