Distributed Duplicate Removal

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. ... mehrHierzu wird ein klassischer Hash-basierter Algorithmus zur verteilten Duplikaterkennung angewendet. Die vorliegende Arbeit ergänzt die theoretische Analyse durch eine praktische Evaluation. Wir erarbeiten hierzu eine effiziente Implementierung für Shared-Nothing Systeme. Besonders rechenintensive Schritte des Algorithmus werden zusätzlich durch Shared-Memory-Programmierung innerhalb eines Knotens parallelisiert. Die Ergebnisse unserer experimentellen Untersuchung untermauern die durch die Theorie vorhergesagten Vorteile des Algorithmus. Unsere Implementierung ist signifikant schneller als der am besten geeignete klassische Ansatz solange die Eingabedaten zu weniger als 50% aus Duplikaten bestehen. Wird der Algorithmus auf Datensätzen ausgeführt, die zu weniger als 10% aus Duplikaten bestehen, so ist das gesamte Kommunikationsvolumen zudem mehr als eine Größenordnung kleiner als das des klassischen Konkurrenten.

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. ... mehrThis thesis complements the theoretical analysis with an experimental evaluation. We transform the high-level description of the algorithm into an efficient implementation than runs on a shared-nothing system and exploits the shared memory parallelism capabilities of its nodes for all computationally intensive operations. The results of our analysis substantiate the benefits predicted by theory. Our implementation outperforms the best-suited traditional algorithm up to the point where the input data contains 50% duplicates. When executed on datasets that contain less than 10% duplicates, our implementation achieves a communication volume that is more than one order of magnitude smaller than that of its competitor. Zusammenfassung Ziel der verteilten Duplikaterkennung ist die Identifikation von Elementen, welche mehrfach