KIT | KIT-Bibliothek | Impressum | Datenschutz

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 jedoch auch falsch positive Ergebnisse auftreten, müssen alle als potentiell nicht distinkt erkannten Elemente in einer zweiten Phase noch einmal überprüft werden. ... 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 duplicate removal algorithm in order to distinguish real duplicates from false positives. ... mehr

Open Access Logo


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