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 )


Programma esteso

Prerequisiti

Modalità didattica

Materiale didattico

Slides distribuite a lezione e usate per le lezioni + eventuali articoli

Periodo di erogazione dell'insegnamento

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


Orario di ricevimento

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/~koutcher

Detailed program

Prerequisites

Teaching form

Textbook and teaching resource

Slides from the lectures + some references to selected papers

Semester

Assessment method

It is requested to give a presentation on a topic presented during the course

Office hours

Enrolment methods

  • Manual enrolments
  • Iscrizione spontanea con approvazione docente

Staff

    Teacher

  • Picture of Paola Bonizzoni
    Paola Bonizzoni