wma:large_graph_processing
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| wma:large_graph_processing [02/06/2014 alle 22:58 (11 anni fa)] – creata Dino Pedreschi | wma:large_graph_processing [02/06/2014 alle 23:18 (11 anni fa)] (versione attuale) – Dino Pedreschi | ||
|---|---|---|---|
| Linea 1: | Linea 1: | ||
| - | Franco Piccinno: Large Graph Processing | + | **Franco Piccinno: Large Graph Processing** |
| The main topic of this seminar is large graph processing. We will try to understand what are the problems that arise when dealing with large datasets and which are the most used solutions today. Specifically we will introduce the Bulk Synchronous Parallel (BSP) model that allows us to process extremely large graphs by distributing the computation to cluster of machines. We will then move our attention to graph compression. We will survey two interesting graph compression techniques, namely K2-trees and WebGraph. The former approach exploits the sparsity of adjacency matrices to achieve compression through a recursive spatial decomposition. The latter technique exploits, similarly to LZ77 compression family, exploits repetitions in the adjacency list achieving a good compression ration and fast decompression. At the end we will briefly discuss how the WebGraph compression algorithm coupled with HyperLogLog counters was used to obtain the famous "4 degree of separation" | The main topic of this seminar is large graph processing. We will try to understand what are the problems that arise when dealing with large datasets and which are the most used solutions today. Specifically we will introduce the Bulk Synchronous Parallel (BSP) model that allows us to process extremely large graphs by distributing the computation to cluster of machines. We will then move our attention to graph compression. We will survey two interesting graph compression techniques, namely K2-trees and WebGraph. The former approach exploits the sparsity of adjacency matrices to achieve compression through a recursive spatial decomposition. The latter technique exploits, similarly to LZ77 compression family, exploits repetitions in the adjacency list achieving a good compression ration and fast decompression. At the end we will briefly discuss how the WebGraph compression algorithm coupled with HyperLogLog counters was used to obtain the famous "4 degree of separation" | ||
wma/large_graph_processing.1401749908.txt.gz · Ultima modifica: 02/06/2014 alle 22:58 (11 anni fa) da Dino Pedreschi