Clustering-based Algorithms for Big Data Computations

In the age of big data, the amount of information that applications need to process often exceeds the computational capabilities of single machines. To cope with this deluge of data, new computational models have been defined. The MapReduce model allows the development of distributed algorithms targeted at large clusters, where each machine can only store a small fraction of the data. In the streaming model a single processor processes on-the-fly an incoming stream of data, using only limited memory. The specific characteristics of these models combined with the necessity of processing very large datasets rule out, in many cases, the adoption of known algorithmic strategies, prompting the development of new ones. In this context, clustering, the process of grouping together elements according to some proximity measure, is a valuable tool, which allows to build succinct summaries of the input data. In this thesis we develop novel algorithms for some fundamental problems, where clustering is a key ingredient to cope with very large instances or is itself the ultimate target. First, we consider the problem of approximating the diameter of an undirected graph, a fundamental metric in graph analytics, for which the known exact algorithms are too costly to use for very large inputs. We develop a MapReduce algorithm for this problem which, for the important class of graphs of bounded doubling dimension, features a polylogarithmic approximation guarantee, uses linear memory and executes in a number of parallel rounds that can be made sublinear in the input graph's diameter. To the best of our knowledge, ours is the first parallel algorithm with these guarantees. Our algorithm leverages a novel clustering primitive to extract a concise summary of the input graph on which to compute the diameter approximation. We complement our theoretical analysis with an extensive experimental evaluation, finding that our algorithm features an approximation quality significantly better than the theoretical upper bound and high scalability. Next, we consider the problem of clustering uncertain graphs, that is, graphs where each edge has a probability of existence, specified as part of the input. These graphs, whose applications range from biology to privacy in social networks, have an exponential number of possible deterministic realizations, which impose a big-data perspective. We develop the first algorithms for clustering uncertain graphs with provable approximation guarantees which aim at maximizing the probability that nodes be connected to the centers of their assigned clusters. A preliminary suite of experiments, provides evidence that the quality of the clusterings returned by our algorithms compare very favorably with respect to previous approaches with no theoretical guarantees. Finally, we deal with the problem of diversity maximization, which is a fundamental primitive in big data analytics: given a set of points in a metric space we are asked to provide a small subset maximizing some notion of diversity. We provide efficient streaming and MapReduce algorithms with approximation guarantees that can be made arbitrarily close to the ones of the best sequential algorithms available. The algorithms crucially rely on the use of a k-center clustering primitive to extract a succinct summary of the data and their analysis is expressed in terms of the doubling dimension of the input point set. Moreover, unlike previously known algorithms, ours feature an interesting tradeoff between approximation quality and memory requirements. Our theoretical findings are supported by the first experimental analysis of diversity maximization algorithms in streaming and MapReduce, which highlights the tradeoffs of our algorithms on both real-world and synthetic datasets. Moreover, our algorithms exhibit good scalability, and a significantly better performance than the approaches proposed in previous works.

Nell'era dei "big data", le capacità dei singoli computer non sono sufficienti a elaborare la quantità di informazioni disponibile. Per elaborare queste grandi moli di dati sono stati introdotti nuovi modelli di calcolo. Il modello MapReduce consente di sviluppare algoritmi distribuiti su grandi cluster, dove ogni macchina memorizza solo una piccola porzione dei dati. Nel modello streaming un singolo processore con memoria limitata elabora in tempo reale il flusso di dati. Le caratteristiche e limitazioni di questi modelli impediscono l'applicazione di strategie algoritmiche note, imponendo lo sviluppo di nuovi algoritmi. In questo contesto uno strumento molto utilizzato è il clustering, ovvero il raggruppare elementi dell'input in base a qualche metrica di vicinanza. Tale approccio consente di costruire rappresentazioni compatte dei dati in ingresso. In questa tesi sviluppiamo nuovi algoritmi per alcuni problemi fondamentali, dove il clustering è una componente chiave per gestire grandi moli di dati o è esso stesso l'obiettivo finale. Il primo problema che affrontiamo è l'approssimazione del diametro di grafi non diretti, una metrica fondamentale nell'analisi dei grafi, per la quale gli algoritmi conosciuti sono troppo costosi per essere usati su grandi input. Sviluppiamo un algoritmo MapReduce per questo problema. Tale algoritmo, per l'importante classe di grafi a "doubling dimension" limitata, ha un fattore di approssimazione polilogaritmico, usa memoria lineare ed esegue in un numero di round che può essere reso sublineare rispetto al diametro del grafo in ingresso. A nostra conoscenza, il nostro è il primo algoritmo parallelo con queste garanzie. Il nostro algoritmo utilizza una nuova primitiva di clustering per costruire una rappresentazione succinta del grafo di input, sulla quale viene calcolata l'approssimazione del diametro. La nostra analisi teorica è affiancata da una approfondita valutazione sperimentale, che mostra che il nostro algoritmo ha in pratica un fattore di approssimazione molto migliore di quello predetto dalla teoria e una elevata scalabilità. Il secondo problema considerato è quello del clustering di grafi uncertain, ovvero grafi il cui ogni arco ha una probabilità di esistenza. Questi grafi, che trovano applicazioni dalla biologia alla privacy nei social network, hanno una dimensione intrinseca molto elevata a causa del numero esponenziale di potenziali realizzazioni. Sviluppiamo i primi algoritmi per il clustering di questi grafi con garanzie teoriche con l'obiettivo di massimizzare la probabilità che i nodi siano connessi con i centri dei loro cluster. Degli esperimenti preliminari mostrano che la qualità del clustering trovato dai nostri algoritmi è comparabile, e in alcuni casi migliore, con approcci presenti in letteratura e mancanti di garanzie teoriche. Infine, ci interessiamo al problema della "diversity maximization", una primitiva fondamentale nell'analisi dei "big data": dato un insieme di punti in uno spazio metrico l'obiettivo è trovare un piccolo sottoinsieme che massimizzi una qualche nozione di diversità. Sviluppiamo algoritmi efficienti in streaming e MapReduce con garanzie teoriche che possono essere rese arbitrariamente vicine a quelle dei migliori algoritmi sequenziali. I nostri algoritmi si basano sull'utilizzo di una primitiva di clustering per estrarre una rappresentazione concisa dei dati. L'analisi è basata sulla doubling dimension dell'insieme in input. Inoltre, contrariamente ad altri approcci presenti in letteratura, il nostro mostra un interessante tradeoff tra la qualità dell'approssimazione e la richiesta di memoria. La nostra analisi teorica è supportata dalla prima analisi sperimentale di algoritmi di diversity maximization in streaming e MapReduce. Questa analisi mostra i tradeoff dei nostri algoritmi sia su dataset sintetici che reali. Inoltre, i nostri algoritmi hanno una buona scalabilità, e prestazioni decisamente migliori di quelli proposti in letteratura.