Efficient clustering of massive data with MapReduce

Fries, Sergej; Rahm, Erhard; Seidl, Thomas

doi:HT018572891

Efficient clustering of massive data with MapReduce = Effizientes Clustering großer Datensätze mit MapReduce

Fries, Sergej

2015

Verantwortlichkeitsangabevorgelegt von Sergej Fries

ImpressumAachen : Publikationsserver der RWTH Aachen University 2015

UmfangIII, 212 S., XXIV : Ill., graph. Darst.

Aachen, Techn. Hochsch., Diss., 2014

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Seidl, Thomas (Thesis advisor) ; Rahm, Erhard (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-12-01

Online
URN: urn:nbn:de:hbz:82-opus-53051
URL: https://publications.rwth-aachen.de/record/463962/files/5305.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Parallelisierung (Genormte SW) ; Cluster-Analyse (Genormte SW) ; Join-Operation (Genormte SW) ; Informatik (frei) ; Selbstähnlichkeits-Join (frei) ; MapReduce (frei) ; similarity self-join (frei) ; connected component in graphs (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Nach der Epoche der Agrargesellschaft und dem Industriezeitalter befindet sich die Menschheit seit einigen Jahrzehnten im Informationszeitalter. Die Information oder was viel wichtiger ist das Wissen wurde zur kostbarsten Ressource. Die bisherigen Ansätze zur Generierung des Wissens ist die Analyse von Beobachtungen oder anderen Rohdaten. Und mit wachsender Vernetzung der Daten wächst auch der Anteil des Wissens, das daraus extrahiert wird. Aus diesem Grund war der Trend des letzten Jahrzehnts die Sammlung aller mölglichen Informationen in allen Bereichen unseres Lebens, sei es in der Industrie, der Wissenschaft oder allgemein der Gesellschaft. Die technologische Entwicklung der Speichermedien und der Sensortechnologien führten zum immer größer werdenden Zuwachs an Daten. So wurde von Peter Hirshberg (global pulse summit) vorhergesagt, dass allein im Jahr 2011 mehr Daten generiert würden als während der gesamten Geschichte der Menschheit vorher. Die Wichtigkeit der Wissensextraktion führte zur Entwicklung des Wissensextraktionsprozesses in Datenbanken (Knowledge Discovery process in Databases) im Jahre 1996. Der KDD-Prozess beschreibt einen Workflow von rohen Daten, über ihre Vorverarbeitung, Analyse bis zur endgültigen Visualisierung für weitere Interpretationen. In den letzten Jahrzehnten dominierte bei der Wissensextraktion das modellgeleitete Vorgehen. D. h., die gesammelten Daten wurden zur Annahme oder zur Ablehnung eines von einem menschlichen Experten erstellten Modells verwendet. Somit hing die Vorhersagegenauigkeit des Modells sehr stark von der Expertise der Spezialisten ab. Sogar gute Modelle berücksichtigen unter Umständen nicht alle Aspekte des gegebenen Problems. In den letzten Jahren rückten datengeleitete Ansätze zur Wissensextraktion mehr in den Vordergrund. Die Idee dabei ist, die Daten „für sich sprechen zu lassen”, d.h. die Modelle direkt aus den Daten zu generieren und diese erst danach zu validieren. Da die Modelle im Vorhinein nicht bekannt sind, ist das Hauptziel, unbekannte Muster in den Daten zu finden. Im KDD Prozess wird diese Aufgabe von sogenannten Clusteranalyse-Techniken des Data Minings gelöst. Die Verfahren der Clusteranalyse haben jedoch oft eine hohe Rechenkomplexität, so dass effiziente Methoden zur Analyse von großen Datenmengen unabdingbar sind. Ein weit verbreiteter Weg dazu ist die Parallelisierung von Algorithmen, die dann auf Multi-Core Computern oder auf Clustern ausgeführt werden können. Der Autor dieser Arbeit verfolgt den gleichen Lösungsweg und stellt neue Techniken zur Analyse von großen Datenmengen im MapReduce-Framework vor. MapReduce ist ein Parallelisierungsframework für datenintensive Anwendungen, das im Jahre 2004 von Google vorgestellt wurde. Seitdem entwickelte sich MapReduce zu einer der wichtigsten Technologien zur Verarbeitung von datenintensiven Aufgaben. Den Schwerpunkt dieser Arbeit stellen zwei Klassen der Clusteranalyse dar, die dichtebasierten und Projected Clustering Verfahren. Dabei werden für jeweils einen Kandidaten aus jeder Klasse - und zwar den DBSCAN- und den P3C-Algorithmus - effiziente Verfahren vorgestellt und evaluiert. Als Teil der dichtebasierten Verfahren wurden in dieser Arbeit des Weiteren effiziente Techniken zum Selbstähnlichkeits-Join in Vektorräumen und ein Verfahren zur Bestimmung der Zusammenhangskomponenten in Graphen vorgestellt.

Since several decades, after the Agrarian society and Machine Age, the mankind approached the Information Age. Information or even much more important knowledge became one of the most valuable resources. The usual way to generate knowledge is the analysis of observation, or of some raw data, and the more and interconnected data is available the more insights can be gained from it. Therefore, in the past decade the trend to gather all possible information in all areas of life, industry and science became overwhelming. Moreover, the technological development of storage and sensor systems allowed an even larger growth of data that are stored. As stated by Peter Hirshberg (global pulse summit) the amount of generated data in the year 2011 alone has exceeded the amount of data generated since the beginning of mankind’s history. The importance of knowledge extraction led to the development of the Knowledge Discovery process in Databases (KDD process) in the year 1996. The KDD process describes a workflow from the raw data gathering, its preprocessing, and analysis to the final visualization for further interpretation. In the last decades, the model-driven approach for knowledge extraction was mainly used. That is, the gathered data was used to accept or to decline a hypothesis that was developed by a human expert. Therefore, the accuracy of the predictive quality of the model highly depended on the expertise of the specialist. Moreover, even good models could miss several aspects of the problem at hand. In the last years, the data-driven approach for knowledge extraction gained a lot of attention. The idea is letting the data "speak for themselves", i.e., to generate novel models based on the given data and to validate them afterwards. As the models are not known in advance, the goal is to find unknown patterns in the data. In the KDD process, this task is usually solved by a group of data mining techniques called unsupervised learning or cluster analysis. However, the cluster analysis task is often computationally expensive and efficient techniques for huge amount of data are indispensable. The usual way for processing large amounts of data is the parallelization of single tasks on multi-core or in cluster environments. In this work, the author follows the parallelization approach and investigates and presents novel techniques for processing and analyzing huge datasets in the widely used MapReduce framework. MapReduce is a parallelization framework for data intensive task that was proposed by Google Inc. in 2004 and developed to one of the most prevalent technologies for batch processing of huge amounts of data. More precisely, this thesis deals with two classes of cluster analysis - the density-based approaches and particularly DBSCAN algorithm, and the projected clustering techniques, where the P3C algorithm was investigated and further developed for processing huge datasets. As part of the density-based approaches, the author of this thesis proposes efficient approaches for similarity self-join technique in vector spaces and determination of connected components in huge graphs in the MapReduce framework.

Fulltext:
PDF
(additional files)