Loading…
Scaling data mining in massively parallel dataflow systems
Schelter, Sebastian
This thesis lays the ground work for enabling scalable data mining in massively parallel dataflow systems, using large datasets. Such datasets have become ubiquitous. We illustrate common fallacies with respect to scalable data mining: It is in no way sufficient to naively implement textbook algorithms on parallel systems; bottlenecks on all layers of the stack prevent the scalability of such naive implementations. We argue that scalability in data mining is a multi-leveled problem and must therefore be approached on the interplay of algorithms, systems, and applications. We therefore discuss a selection of scalability problems on these different levels.
We investigate algorithm-specific scalability aspects of collaborative filtering algorithms for computing recommendations, a popular data mining use case with many industry deployments. We show how to efficiently execute the two most common approaches, namely neighborhood methods and latent factor models on MapReduce, and describe a specialized architecture for scaling collaborative filtering to extremely large datasets which we implemented at Twitter. We turn to system-specific scalability aspects, where we improve system performance during the distributed execution of a special class of iterative algorithms by drastically reducing the overhead required for guaranteeing fault tolerance. Therefore we propose a novel optimistic approach to fault-tolerance which exploits the robust convergence properties of a large class of fixpoint algorithms and does not incur measurable overhead in failure-free cases. Finally, we present work on an application-specific scalability aspect of scalable data mining. A common problem when deploying machine learning applications in real-world scenarios is that the prediction quality of ML models heavily depends on hyperparameters that have to be chosen in advance. We propose an algorithmic framework for an important subproblem occuring during hyperparameter search at scale: efficiently generating samples from block-partitioned matrices in a shared-nothing environment.
For every selected problem, we show how to execute the resulting computation automatically in a parallel and scalable manner, and evaluate our proposed solution on large datasets with billions of datapoints.
Diese Doktorarbeit befasst sich mit den technischen Grundlagen, die notwendig sind, um skalierbares Data Mining auf heutigen, großen Datensätzen mithilfe massiv-paralleler Datenflusssysteme zu ermöglichen. Sie beschreibt gängige Fehlannahmen im Bezug auf skalierbares Data Mining. Es reicht in keinster Weise aus, Algorithmen in ihrer herkömmlichen Formulierung auf parallelen Systemen zu implementieren. Engpässe auf allen Schichten verhindern die Skalierbarkeit solch naiver Implementierungen. Die Arbeit legt dar, dass Skalierbarkeit im Data Mining ein mehrschichtiges Problem ist und daher im Zusammenspiel von Algorithmen, Systemen und Anwendungen angegangen werden muss. Deshalb befasst sich diese Arbeit mit einer Auswahl von Skalierbarkeitsproblemen in verschiedenen Schichten.
Die Arbeit untersucht algorithmus-spezifische Skalierbarkeitsaspekte von "Collaborative Filtering"-Algorithmen zur Empfehlungsberechnung, eine beliebte Data Mining-Technik, die häufig in der Industrie Anwendung findet. Es wird dargelegt, wie die beiden vorherrschenden Ansätze, "Neighborhood Methods" und "Latent Factor Models" mithilfe des MapReduce Paradigmas skaliert werden können. Desweiteren beschreibt die Arbeit ein spezialisierte Architektur, die bei Twitter implementiert wurde, um Collaborative Filtering auf extrem große Datensätze anwenden zu können. Im Folgenden wird sich mit system-spezischen Skalierbarkeitsaspekten befasst: die Arbeit beschreibt, wie man die Systemleistung während der verteilten Ausführung einer speziellen Klasse iterativer Algorithmen verbessern kann, indem man den Mehraufwand drastisch reduziert, der für die Garantie von Fehlertoleranz notwendig ist. Die Arbeit führt einen neuartigen optimistischen Ansatz zur Fehlertoleranz ein, der die robusten Konvergenzeigenschaften einer großen Klasse von Fixpunktalgorithmen ausnutzt und während fehlerfreier Ausführung keinen messbaren Mehraufwand verursacht. Schlussendlich widmet sich die Arbeit einem anwendungsspezifischen Skalierbarkeitsaspekt. Ein gängiges Problem beim Einsatz von Anwendungen des Maschinellen Lernens ist, dass die Vorhersagequalität der Modelle häufig stark von Hyperparametern abhängt, die im Vorhinein gewählt werden müssen. Die Arbeit beschreibt ein algorithmisches Framework für ein wichtiges Unterproblem bei der Suche nach Hyperparameter auf großen Datensätzen: die effiziente Generierung von Stichproben aus block-partitionierten Matrizen in verteilten Systemen.
Für jedes ausgewählte Problem legt die Arbeit dar, wie die zugrundeliegenden Berechnungen automatisch auf eine parallele und skalierbare Weise ausgeführt werden können. Die präsentierten Lösungen werden experimentell auf großen Datensätzen bestehend aus Milliarden einzelner Datenpunkte evaluiert.
