Thesis' proposals

This list is incomplete. If you are interested in my research topics (see here ), contact me for more information.

Proposals for master students (“Laurea Magistrale”)


Analisi del Parlamento Italiano tramite big-data

Molte delle attività del Parlamento Italiano sono digitalizzate e pubblicamente disponibili nei portali web delle due Camere. Ad esempio dati.camera.it e dati.senato.it contengono dati già strutturati su deputati, attività legislativa, interventi nelle assemble, risultati delle votazioni,… Altri dati possono essere ottenuti con un crawling dei siti camera.it e senato.it.

Tramite tecniche di data mining, è possibile estrarre da questi dati informazioni utili sulle attività e dinamiche del sistema parlamentare. Ad esempio è possibile analizzare le somiglianze tra deputati o la formazione di raggruppamenti politici analizzando i risultati delle votazioni, oppure le interazioni tra i deputati studiando gli interventi nelle assemblee.

Il tesista dovrà analizzare i dati disponibili, definire e formalizzare gli obiettivi dell’analisi, effettuare l’analisi utilizzando techniche di data mining.

Alcuni esempi di analisi delle attività politiche con tecniche di data mining sono disponibili qui: analisi del senato americano, clustering di emendamenti, clustering dei voti del Parlamento (slides 10-12).

Prerequisiti: aver positivamente svolto il corso di Data Mining (o corsi equivalenti), buona media dei voti.


Distance Sensitive Bloom Filters (assigned)

Given a set S, a Bloom filter [1] is a data structure that efficiently answers the query “Is an element x in S?”. A Bloom filter requires less space than the trivial solution of storing the entire set S, however it has false positives: for some elements x, the filter returns “Yes” even when the correct answer is “No”.

This kind of errors is acceptable in many applications. For instance, when checking if a new image is already contained in a set S of images: if the answer is “no”, then we can certainly conclude that the image is not in S; if the answer is “yes” we can check the correctness with a (expensive) standard search within S. This approach is efficient when the number of “no” answers is much larger than the “yes” ones. Bloom filters are used in many applications like Google Chrome, Apache HBase, Bitcoin…

A desirable feature that is not supported by Bloom filters is to recognise similar objects: we would like to answer the query “Does set S contain an element similar to x?”. Filters supporting these queries are called ”distance sensitive Bloom filters”. For instance, we would like to recognise if set S contains an image that differs from an image x in a few pixels, or a document that differs from a text x in a few words.

A recent [2] result has shown that such a data structure exists and has theoretical proprieties similar to the standard Bloom filters. The goal of this thesis is to further investigate distance sensitive Bloom filters by studying the filters in some specific settings, providing an efficient implementation and then by experimentally evaluating them.

References:

  1. Wikipedia page on [Bloom filters] (https://en.wikipedia.org/wiki/Bloom_filter).
  2. M. Goswami, R. Pagh, F. Silvestri and J. Sivertsen. Distance Sensitive Bloom Filters Without False Negatives. Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 257-269. 2017. (PDF).


Proposals for bachelor students (“Laurea Triennale”)

Working in progress…