Large-scale graph processing frameworks : analysis and performance evaluation

With the advancement of technology, the speed of content creation is increasing and data sets with high volume, high change velocity and high variety are created. They are named Big Data and in many application scenarios, they involve relations between entities that are naturally modelled by graphs. Some examples are web pages; social networks’ data where users are connected by “follow” or “friendship” relation; or maps, where roads connect different locations. In pursuit of graph processing performance, the systems community has largely abandoned general-purpose distributed dataflow frameworks in favour of specialized graph processing systems that provide tailored programming abstractions and accelerate the execution of iterative graph algorithms. In recent years, many of the distributed systems proposed for large-scale graph analytics are based on the vertex-centric model, whose performance in terms of run time depends on the partitioning and distribution of the graph. Therefore, graph partitioning is a major concern in this field. In this work, we studied frameworks for large-scale graph analysis to compare functioning paradigms and new approaches to strong guarantees in distributed scenarios. We analyzed the differences and common aspects that are emerging and could drive future design patterns. To conduct our analysis systematically we developed a modelling framework.

Con il progresso della tecnologia, la velocità di creazione dei contenuti è in aumento e vengono creati dataset di grandi dimensioni che vengono modificati rapidamente e che contengono un’ampia varietà di dati. Questi vengono chiamati Big Data e in molti scenari applicativi implicano relazioni tra entità che sono naturalmente modellate da grafi. Alcuni esempi sono le pagine web; i dati dei social network in cui gli utenti sono collegati da una relazione "segui" o "amicizia"; o mappe, dove le strade collegano luoghi diversi. Al fine di ottenere prestazioni maggiori per l'analisi di grafi di grandi dimensioni, la comunità dei sistemi ha in gran parte abbandonato sistemi analitici generali a favore di sistemi specializzati che forniscono astrazioni di programmazione personalizzate e accelerano l'esecuzione di algoritmi iterativi su grafi. Negli ultimi anni, molti dei sistemi distribuiti proposti per l'analisi di grafi di grandi dimensioni si basano sul modello vertex-centric, le cui prestazioni in termini di tempo di esecuzione dipendono dal partizionamento e dalla distribuzione del grafico. Pertanto, il partizionamento del grafo è un fattore fondamentale in questo campo. In questo lavoro di tesi abbiamo studiato sistemi per l'analisi di grafi per confrontare paradigmi di funzionamento e nuovi approcci introdotti a supporto di forti garanzie in scenari distribuiti. Abbiamo analizzato le differenze e gli aspetti comuni che stanno emergendo e potrebbero guidare i futuri modelli di progettazione. Per condurre la nostra analisi in modo sistematico, abbiamo sviluppato un framework di modellazione.