ETD

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

Tesi etd-04012021-172650


Tipo di tesi
Tesi di dottorato di ricerca
Autore
VERSARI, LUCA
URN
etd-04012021-172650
Titolo
Compression Techniques for Large Graphs: Theory and Practice
Settore scientifico disciplinare
INF/01
Corso di studi
INFORMATICA
Relatori
tutor Grossi, Roberto
commissario Prof. Chierichetti, Flavio
commissario Prof. Crispo, Bruno
commissario García Sánchez, José Daniel
Parole chiave
  • compression
  • graphs
Data inizio appello
26/04/2021
Consultabilità
Completa
Riassunto
In today’s world, compression is a fundamental technique to let our computers
deal in an efficient manner with the massive amount of available information.
Graphs, and in particular web and social graphs, have been growing exponentially
larger in the last years, increasing the necessity of having efficient compressed
representations for them. In this thesis, we study the compression of graphs from
both a theoretical and a practical point of view. We provide a new technique to
achieve better compression of sequences of large integers, showing its theoretical
and practical properties, as well as new techniques for practical context modeling
in large context spaces. We conduct a theoretical analysis of the compression of
various models of graphs, showing that theoretically optimal compression for each
of those models can be achieved in polynomial time. Finally, we show how to apply
the proposed techniques to practical graph compression to obtain a new scheme
that achieves significant size savings over the state of the art, while still allowing
efficient compression and decompression algorithms.
File