Clustering-based Algorithms for Big Data Computations

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.