KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Volltext
DOI: 10.5445/IR/1000058832

Distributed Duplicate Removal

Schlag, Sebastian

Abstract:
Ziel der verteilten Duplikaterkennung ist die Identifikation von Elementen, welche mehrfach in einer großen, über mehrere Rechenknoten verteilten Datenmenge vorkommen. Sanders et al. [48] präsentieren einen verteilten Algorithmus, welcher dieses Problem in einer besonders kommunikationseffizienten Art und Weise löst. In einer Vorverarbeitungsphase werden mit Hilfe eines verteilten, platz-effizienten Bloom Filters zunächst möglichst viele distinkte Elemente als solche identifiziert und somit die Gesamtmenge der noch zu betrachtenden Elemente stark reduziert. Da hierbei ... mehr

Abstract (englisch):
The distributed duplicate removal problem is concerned with the detection and subsequent elimination of all duplicate elements in a given multiset that is distributed over several computers connected by a network. Sanders et al. [48] outline a communication efficient algorithm solving this problem. It uses distributed compressed single shot Bloom filters to identify distinct elements using minimal communication effort. The filter however produces false positive results. Thus, all elements passing the filter are post processed using a traditional hash-based distributed ... mehr


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2013
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-588321
KITopen-ID: 1000058832
Verlag Karlsruhe
Umfang V, 57 S.
Abschlussart Abschlussarbeit - Master
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page