La progressiva disponibilità di sempre più ingenti quantità di dati (Big Data) dovuta ai processi di informatizzazione e digitalizzazione in atto a livello mondiale nei campi più disparati della società e dell'economia motiva, in modo sempre più prepotente, la necessità di sviluppare algoritmi efficienti non solo teoricamente ma anche, e soprattutto, nella pratica. Questo trend sta rivoluzionando il modo stesso con cui si concepiscono e sviluppano gli algoritmi, favorendo l'ingresso di fattori che consentano di meglio predire e stimare l'efficienza sperimentale di un algoritmo. Si diffondono poi nuovi paradigmi di calcolo basati su sistemi distribuiti per risolvere determinati problemi ad una frazione del tempo necessario rispetto ad un sistema tradizionale.
Il progetto sviluppa queste tematiche secondo tre direttrici:
1. Estrazione efficiente di k-mers da sequenze genomiche. Si considera un problema algoritmico comune in ambito bioinformatico e per il quale esistono soluzioni teoricamente efficienti. Per tale problema si intendono sviluppare degli algoritmi basati sul calcolo distribuito per abbattere i tempi di risoluzione rispetto agli approcci tradizionali
2. Complessità computazionale della soddisfacibilità e di
problemi su grafi. Lo studio della complessità di un algoritmo può fallire nello stimare il tempo di esecuzione dello stesso su istanze reali. Si considera una particolare tipologia di problemi, basati su grafi, per i quali si intende studiare la possibilità di ottenere una stima più fedele dell'efficienza di un algoritmo, pur senza implementarlo, mediante l'uso della proof complexity.
3. Misure di vitalità su grafi planari. Numerosi dei problemi computazionalmente più complessi fanno riferimento a strutture modellabili come grafi di grandi dimensioni, quali reti di TLC o reti sociali. Si intendono studiare delle misure di vitalità che consentano di determinare la robustezza di un grafo planare rispetto ad eventi di disconnessione di nodi o archi.
Punto 1. Estrazione efficiente di k-mers da sequenze genomiche
Come precedentemente riassunto, negli ultimi anni si sta portando avanti un tentativo di ridurre significativamente i tempi di risposta degli algoritmi di k-mers counting mediante l'uso di un approccio distribuito. Tuttavia, le proposte sinora avanzate si sono rivelate deludenti, migliorando le prestazioni dei sistemi tradizionali ma senza sfruttare appieno le potenzialità di calcolo offerte dai sistemi distribuiti.
La ricerca che si intende portare avanti intende migliorare significativamente l'efficienza in pratica dei sistemi distribuiti di k-mers counting mediante un approccio multi-laterale. In particolare, si intende studiare come i sistemi distribuiti di k-mers counting attualmente esistenti interagiscono con il sistema sottostante allo scopo di individuare colli di bottiglia ed inefficienze che potrebbero essere imputati, nell'ordine, all'approccio algoritmico, al middleware (e.g., Spark, Hadoop) al sistema operativo, all'hardware. Scopo di questa attività di profiling è raccogliere informazioni utili a formulare una nuova proposta di approccio distribuito che possa consentire di sfruttare fino in fondo le capacità di calcolo del sistema sottostante.
Particolare attenzione sarà dedicata all'aspetto del task scheduling, andando a verificare la capacità del sistema realizzato di adoperare, in modo uniforme, tutte le risorse di calcolo disponibili ed, eventualmente, rischedulare dinamicamente dei tasks laddove ci dovessero esseri nodi del sistema distribuiti inutilizzati rispetto ad altri.
L'impatto della soluzione realizzata sarà misurato andando a confrontarne le prestazioni sperimentali con quelle di altri sistemi già noti in letteratura per mezzo di dataset standard.
Punto 2. Complessità computazionale della soddisfacibilità e di
problemi su grafi
Per risolvere problemi computazionali si cercano algoritmi sempre più
veloci. D'altra parte la complessità computazionale cerca di
dimostrare matematicamente che certi problemi non hanno algoritmi
efficienti. Ottenere questi risultati è complesso: come si fa infatti
ad affermare che nessuno tra gli algoritmi ancora da scoprire è
efficiente? Un'opzione è usare l'ipotesi non dimostrata "P diverso da
NP", ma il nostro progetto vuole superare questa scelta.
Le tecniche della proof complexity che verranno usate in questo
progetto, provenienti dallo studio della logica proposizionale, vanno
sviluppate se si vogliono applicare a problemi su grafi. Sono pochi i
risultati già noti, che riguardano principalmente proprietà di grafi
espresse da CSP. Per il problema della k-clique invece ci sono
risultati molto parziali (ad esempio Atserias et al, 2018).
La proof complexity si concentra su formule ad hoc e artificiali,
fatte apposta per non avere dimostrazioni brevi. Nel nostro caso il
problema iniziale proveniente dalla teoria dei grafi deve essere
codificato in una formula che non possiamo controllare completamente.
Questo aumenta la difficoltà nel dimostrare lower bound. Oltretutto
più l'algoritmo da studiare è utile e complesso, più il proof system
usato per modellarlo deve essere espressivo, e l'analisi diventa più
difficile. Tuttavia questa linea di ricerca identifica molto
precisamente quali sono i difetti e le inefficienze di questa o quella
tecnica algoritmica, quindi può dare lo spunto per implementarne di
nuove.
3. Misure di vitalità su grafi planari
La determinazione delle caratteristiche di robustezza di una rete rispetto a particolari proprietà riveste una importanza crescente, ad esempio nella realizzazione di infrastrutture critiche. Il gruppo di lavoro mostra una elevata esperienza nello studio di tecniche algoritmiche [bfs, hyper] per la soluzione di problemi di ottimizzazione su reti, anche in contesti dinamici [faultspanners, dynspanner, resilient]. Applicando tali tecniche è possibile ottenere soluzioni particolarmente efficienti rispetto a quelle ottenibili con metodologie generali di modellazione e ottimizzazione di problemi combinatori.
I risultati ottenuti fin'ora su casi particolari sono molto promettenti, e l'esperienza acquisita sul problema del massimo flusso potrebbe avere ricadute anche su problemi di ottimizzazione collegati, come flussi con più sorgenti e pozzi.
[faultspanners] G. Ausiello, P. G. Franciosa, G. F. Italiano, A. Ribichini.
Computing graph spanners in small memory: fault-tolerance and streaming. Discrete Mathematics, Algorithms and Applications, 2(4):591-605, 2010.
[dynspanner] G. Ausiello, P. G. Franciosa, G. F. Italiano.
Small stretch spanners on dynamic graphs.
Journal of Graph Algorithms and Applications, 10(2):365-385, 2006.
[hyper] G. Ausiello, P. G. Franciosa, and D. Frigioni.
Partially Dynamic Maintenance of Minimum Weight Hyperpaths.
J. of Discrete Algorithms, 3(1):27-46, 2005.
[bfs] P. G. Franciosa, D. Frigioni, and R. Giaccio.
Semi-dynamic breadth-first search in digraphs.
Theoret. Comput. Sci., 250:202-217, 2001