Syllabus del corso
Obiettivi
Il corso presente alcuni approcci recenti al disegno di strutture dati per trattare sfide computazionali moderne relative alla computazione su grandi moli di dati. Obiettivo del corso è l'acquisizione di alcune tecniche e di alcuni concetti che consentono di affrontare sfide emergenti nell'ambito Computer Science.
In particolare il focus è su:
- memorizzare e interrogare strutture dati succinte
- le applicazioni moderne che richiedono queste strutture dati (es. Web, Bioinformatica, Data Mining)
- Algoritmi su testi e data streaming
Contenuti sintetici
Alcune lezioni sono tenute da esperti dell'ambito
In particolare secondo il seguente calendario:
Travis Gagie terrà un seminario il 9 Marzo -
Lezioni principali - terza e quarta settimana di Marzo -
Introduzione
- Nuove strutture dati e loro utilizzo in diverse applicazioni
- cosa si intende per indicizzazione di big data?
quali sono le principali query sull'indice?
Che cosa è il data streaming?
• Introduzione ai Bloom Filters e la loro applicazione per gestire big data in poco spazio
PARTE 2 (data prevista il 25 Marzo)
Tecniche di hashing con applicazioni al WEB
( Web crawling and indexing, Web graphs)
(parte tenuta da Paolo Boldi http://boldi.di.unimi.it/)
MPHF (minimum perfect hashing function)
• Prima parte: (M)PHF
◦ Il problema generale (principale applicazione: la costruzione del grafo)
◦ funzioni di hash
◦ L'algoritmo MWHC per array sparsi
◦ MWHC per costruire (M)PHF
• Seconda parte: MMPHF
◦ Introduzione
◦ Primo tipo di costruzione: LCP
◦ Secondo tipo di costruzione : Z-fast tries
PARTE 3 (dal 24 Marzo)
Strutture dati per il pattern matching
Suffix-trees e suffix-arrays
(parte tenuta da Gregory Kucherov, docente del collegio di dottorato
https://www-igm.univ-mlv.fr/~koutcher )Materiale didattico
Slides distribuite a lezione e usate per le lezioni + eventuali articoli
Modalità di verifica del profitto e valutazione
L'esame consistente nel fare una breve presentazione specifica su un argomento di interesse che è stato svolto durante il corso
Aims
- The course presents the most recent approaches to the design of data structures for dealing with the challenges of modern computing on big collections of text data. The goal of the course is the acquisition of techniques and concepts that allow to face emerging challenges in the field of computer science.
- Topics include:
- - storing and querying by succinct data structures and how to design efficient algorithms for building such succinct data structures,
- Modern applications.
- Data streaming and algorithms for dealing with text data
Contents
Some of the lectures are given by experts in the field and there will be a seminar from Travis Gagie in the second week of March (9th of March).
The main lectures will be in the third and last week of March.
Introduction
- A list of novel data structures and their uses in different applications
- What is indexing of big data and what are the main queries? What is data streaming?
• Introduction to Bloom
Filters and their applications to manage
big data in small space
Tecniche di hashing con applicazioni al WEB
Web crawling and indexing
Web graphs
(Paolo Boldi http://boldi.di.unimi.it/)
MPHF (minimum perfect hashing function)
• First part: (M)PHF
◦ The general problem (intended application: graph construction)
◦ Interlude: hash functions
◦ The MWHC algorithm for sparse arrays
◦ The MWHC to build (M)PHF
• Second part: MMPHF
◦ Introduction
◦ First construction: LCPs
◦ Second construction: Z-fast tries
Data structures for pattern
matching (24th of March)
Suffix-trees and suffix-arrays
(Gregory Kucherov, docente del collegio di dottorato
https://www-igm.univ-mlv.fr/~koutcherTextbook and teaching resource
Slides from the lectures + some references to selected papers
Assessment method
It is requested to give a presentation on a topic presented during the course