logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-06252014-094133


Tipo di tesi
Tesi di laurea magistrale
Autore
ESPOSITO, ANDREA
URN
etd-06252014-094133
Titolo
ONJAG, network overlays supporting distributed graph processing
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Ricci, Laura Emilia Maria
relatore Dott. Dazzi, Patrizio
Parole chiave
  • Apache Spark
  • Balanced Minimum k-way partitioning problem
  • Bulk Synchronous Parallel
  • Distributed Algorithm
  • Graph Processing
  • k mincut
  • k-way cut
  • Min-Cut
  • Overlays
  • Peer-to-Peer
  • Pregel
  • Self Organizing Systems
Data inizio appello
25/07/2014
Consultabilità
Completa
Riassunto
The "Big Data" term refers to the exponential growth that is affecting the production of structured and unstructured data. However, due to the size characterising this data, usually deep analyses are required in order to extract its intrinsic value. Several computational models and various techniques have been studied and employed in order to process this data in a distribute manner, i.e. the capabilities of a single machine can not carry out the computation of this data. Today, a significant part of such data is modelled as a graph. Recently, graph processing frameworks orchestrate the execution as a network simulation where vertices and edges correspond to nodes and links, respectively. In this context the thesis exploits the Peer-to-Peer approach. The overlay concept is introduced and ONJAG ("Overlays Not Just A Graph"), a distributed framework, is developed. ONJAG runs over Spark, a distributed Bulk Synchronous Parallel-like data processing framework. Moreover, a well-known problem in graph theory has studied. It is the balanced minimum k-way partitioning problem, which is also called minimum k-way cut. Finally, a novel algorithm to solve the balanced minimum k-way cut is proposed. The proposal exploits the P2P approach and the overlays in order to improve a pre-existent solution.
File