# Paolo Ferragina

Paolo Ferràgina (Catanzaro, 27 giugno 1969) è un informatico italiano. Si è occupato principalmente della progettazione e implementazione di algoritmi per l'analisi, la memorizzazione compressa, l'indicizzazione e la ricerca su big data.
Con Giovanni Manzini ha ideato l'FM-index, una struttura dati con numerose applicazioni in bioinformatica; per l'FM-index Ferragina e Manzini hanno ricevuto, insieme con Micheal Burrows, il premio ACM Paris Kanellakis (edizione 2022) con la seguente motivazione:
«For inventing the BW-transform and the FM-index which greatly advanced the field of Compressed Data Structures with fundamental impact on Data Compression and Computational Biology»
«Per aver inventato la trasformata BW e l'FM-index che hanno fatto progredire notevolmente il campo delle strutture di dati compressi con un impatto fondamentale sulla compressione dei dati e sulla biologia computazionale»
(Premio ACM Kanellakis 2022)
Ferragina e Manzini sono stati i primi italiani e quarti europei a ricevere il premio.
Ha svolto la sua carriera accademica presso l'Università di Pisa, fino a diventare professore ordinario dal 2007. Nel 2019 è insignito dell'Ordine del Cherubino, premio conferitogli dall'ateneo pisano per aver «contribuito ad accrescerne il prestigio, per particolari meriti scientifici, e [per aver] fornito un rilevante supporto alla vita e al funzionamento dell’Università, avendo ricoperto al suo interno significative cariche istituzionali ed organizzative»; nel 2021, è nominato ACM Senior member dell'Association of Computing Machinery (USA). Dal 2024 è professore ordinario d'informatica presso il dipartimento EMbeDS della Scuola Superiore Sant'Anna di Pisa.

## Formazione

Paolo Ferragina consegue il dottorato di ricerca in informatica presso l'Università di Pisa (1996), dov'è allievo di Fabrizio Luccio; prosegue poi gli studi con un post-dottorato presso il Max-Planck-Institut für Informatik (1998), sotto la supervisione di Kurt Mehlhorn.
Trascorre periodi di formazione e di ricerca in vari istituti e industrie; oltre a quelli già citati: MGH/Harvard Medical School (Boston, MA), Massachusetts Institute of Technology (Boston, MA), Courant Institute (Università di New York), University of North Texas, IBM Research (Roma), AT&T Shannon Lab (Florham Park, NJ), Yahoo! Research (Barcellona), Google (Zurigo).

## Attività accademica

Dopo aver fatto ritorno all'Università di Pisa, diviene professore ordinario a decorrere dal 2007. I suoi primi anni di attività di ricerca sono sostenuti da un piano di finanziamento quinquennale di Yahoo!, in particolare tramite un Faculty Award, dal 2006 al 2010 — all'epoca il primo in Europa — grazie ai suoi contributi nel campo della compressione dei dati e delle strutture dati efficienti su disco. Dirige un gruppo di ricerca denominato Acube Lab (cioè «Laboratorio A al cubo», perché si occupa di Algoritmi Avanzati e Applicazioni), che ha collaborato con importanti aziende tecnologiche del settore ICT, tra cui Google, l'Unione europea di radiodiffusione (UER/EBU), Bloomberg, Yahoo!, ST Microelectronics, ENEL, CERVED, Tiscali, ecc.
Ha avuto un'intensa produzione scientifica su riviste e conferenze internazionali (sottoposte a revisione tra pari) nell'ambito dell'informatica teorica, dell'Algoritmica e dell'Information Retrieval. Ha pubblicato più di 170 articoli, è stato citato più di 10 mila volte e detiene un indice H pari a 40 (dati di Google Scholar, marzo 2023). Su Scopus, detiene un indice H pari a 36 e più di 6.000 citazioni (dati di marzo 2023). I suoi articoli sono apparsi cinque volte sulla rivista Journal of the ACM, tre volte su SIAM Journal on Computing, quattro su ACM Transactions on Algorithms, sette su Algorithmica, sette su Theoretical Computer Science, due su ACM Transactions on Information Systems. Per quanto riguarda le conferenze, i suoi articoli sono stati pubblicati tre volte sugli atti dell'ACM Symposium on the Theory of Computing (STOC), cinque volte su IEEE Foundations of Computer Science (FOCS), sette volte su ACM-SIAM Symposium on Discrete Algorithms (SODA), tredici volte su European Symposium on Algorithm (ESA), sei volte su World Wide Web Conference (WWW), tre volte su ACM Web Search and Data Mining (WSDM). È co-depositario di quattro brevetti statunitensi, co-autore di cinque libri d'informatica (tre in italiano, pubblicati da Boringhieri, Pisa University Press e Il Mulino, e uno in inglese, pubblicati da Springer. È autore di un testo in lingua inglese sull'ingegneria degli algoritmi pubblicato da Cambridge University Press, e di alcuni capitoli in testi in lingua inglese pubblicati da Springer e da CRC Press.
È tra gli ideatori, oltre che dell'FM-index, anche di TagMe, il primo entity linker per la lingua italiana, multilingue (disponibile anche in inglese e tedesco) e liberamente fruibile sull'infrastruttura di ricerca europea SoBigData. È citato tra i contributori delle ricerche che hanno dato origine al compressore Brotli di Google, il quale è adottato da più del 94% dei browser moderni (marzo 2023). È anche co-autore del PGM-index, struttura dati per l'indicizzazione di sequenze d'interi come, ad esempio, colonne di basi dati o le liste invertite dei motori di ricerca; la libreria software del PGM ha ottenuto 670+ stelle su GitHub e 580+ voti positivi su Hacker News ed è stata adottata nella base dati open source Manticore. È tra gli autori dello String B-tree, la prima struttura dati per la gestione di dizionari di stringhe a lunghezza variabile che ottiene prestazioni ottime in termini di scritture su disco, definita come «elegante» da Donald Knuth a pagina 489 del volume terzo della sua opera The Art of Computer Programming.

## Cariche accademiche

Nel corso della carriera accademica ha ricoperto diversi ruoli istituzionali presso l’Università di Pisa. Dal 2006 al 2009 è stato vicedirettore del Dipartimento d'Informatica; dal 2010 al 2016, è stato prorettore per «la ricerca applicata e l’innovazione»: in questo periodo è l'ideatore e fautore di due iniziative per la promozione della ricerca di eccellenza (MIT-Italy, col Massachusetts Institute of Technology) e della formazione alla cultura imprenditoriale: il PhD Plus. Dal 2018 al 2020, ha svolto il ruolo di Coordinatore del dottorato (regionale) di ricerca in Informatica, che coinvolge anche le Università di Firenze e Siena, di cui è membro dal 2002; dal 2019 al 2022, è Prorettore per l’Informatica e ha definito la strategia digitale d'ateneo durante l'emergenza legata alla pandemia da COVID-19.

## Comitati scientifici internazionali

Tra gli incarichi scientifici di maggior rilevanza, si segnalano:
* Dal 2011 è membro del comitato editoriale della rivista internazionale Journal on Graph Algorithms and Applications (JGAA);
* Aea editor della (EN) Ming-Yang Kao (a cura di), Encyclopedia of Algorithms, New York, Springer New York, DOI:10.1007/978-1-4939-2864-4.
* Area editor della (EN) Albert Zomaya, Javid Taheri e Sherif Sakr (a cura di), Encyclopedia of Big Data Technologies, Springer Cham, DOI:10.1007/978-3-319-63962-8.
* Co-direttore della scuola estiva internazionale di dottorato Jacob T. Schwartz sul tema Computational Social Sciences, che si tiene annualmente sull'isola di Lipari dal 2016.
* Nel 2019, è membro del comitato di valutazione dei progetti europei di ricerca ERC Advanced Grants per il settore «PE6 - Computer Science and Informatics».
* Membro del comitato direttivo della conferenza Symposium on String Processing and Information Retrieval (SPIRE; dal 2006 al 2009) e dello European Symposium on Algorithms (ESA; dal 2012 al 2014).

## Premi e riconoscimenti

* Best Land Transportation Paper Award, IEEE Vehicular Technology Society (1995);
* Philip Morris Award on Science and Technology (1997);
* EATCS Doctoral Dissertation Thesis Award (1997);
* Research Capital award, assegnato dall’Università di Pisa (2002);
* Yahoo! faculty award (2006-2010);
* Working Capital Award, assegnato da Telecom Italia (2010);
* Top-100 renowned scientists secondo Google EMEA (2012);
* 3 research awards assegnati da Google (2010, 2012 e 2016);
* Bloomberg Data Science research grant (2017);
* Educator grant award assegnato da Google (EMEA) per la disseminazione del pensiero computazionale tra i docenti e gli studenti delle scuole superiori italiane (2018);
* Google Cloud Research Innovator program (2022).
* 2022 ACM Paris Kanellakis Theory and Practice Award

## Opere
### Libri

* Paolo Ferragina e Fabrizio Luccio, Crittografia, Boringhieri, 2001, ISBN 9788833956657.
* Anna Bernasconi, Paolo Ferragina e Fabrizio Luccio, Elementi di crittografia, Pisa University Press, 2015, ISBN 9788867414604.
* Paolo Ferragina e Fabrizio Luccio, Il Pensiero Computazionale: Dagli algoritmi al coding, collana Le vie della civiltà, Il Mulino, 2017, ISBN 9788815272867.
* (EN) Paolo Ferragina e Fabrizio Luccio, Computational Thinking ‒ First Algorithms, Then Code, Springer Cham, 2019, DOI:10.1007/978-3-319-97940-3, ISBN 978-3-030-07424-1.
* (EN) Paolo Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, ISBN 978-1009123280.

### Pubblicazioni su rivista

* (EN) Paolo Ferragina e Roberto Grossi, The String B-tree: a new data structure for string search in external memory and its applications, in Journal of the ACM, vol. 46, n. 2, 1999, pp. 236-280, DOI:10.1145/301970.301973. La versione su conferenza è apparsa in Procs ACM STOC 2005.
* (EN) Martin Farach-Colton, Paolo Ferragina e S. Muthukrishnan, On the sorting complexity of suffix tree construction, in Journal of the ACM, vol. 47, n. 6, 2000, DOI:10.1145/355541.355547. La versione su conferenza è apparsa in Procs IEEE FOCS 1998
* (EN) P. Ferragina e G. Manzini, Indexing compressed texts, in Journal of the ACM, vol. 52, n. 4, 2005, DOI:10.1145/1082036.1082039. La versione su conferenza è apparsa in Procs IEEE FOCS 2000
* (EN) P. Ferragina, F. Luccio, G. Manzini e S. Muthukrishnan, Compressing and indexing labeled trees, with applications, in Journal of the ACM, vol. 57, n. 1, 2009, DOI:10.1145/1613676.1613680. La versione su conferenza è apparsa in Procs IEEE FOCS 2005 en in Procs WWW 2006.
* (EN) P. Ferragina, F. Piccinno e R. Venturini, Compressed indexes for string-searching in labeled graphs, in Procs WWW, 2015, DOI:10.1145/2736277.2741140.
* (EN) P. Ferragina, R. Giancarlo, G. Manzini e M. Sciortino, Boosting textual compression in optimal linear time, in Journal of the ACM, vol. 52, n. 4, 2005, DOI:10.1145/1082036.1082043. La versione su conferenza è apparsa in Procs ACM-SIAM SODA 2004.
* (EN) A. Farruggia, P. Ferragina, A. Frangioni e R. Venturini, Bicriteria data compression, in SIAM Journal on Computing, 2019, DOI:10.1137/17M1121457. La versione su conferenza è apparsa in Procs ACM-SIAM SODA, 2014 (parte teorica), e in Procs European Symposim on Algorithms (ESA), 2014 (parte sperimentale)
* (EN) J. Alakuijala, A. Farruggia, P. Ferragina e altri, Brotli: A general-purpose data compressor, in ACM Transactions on Information Systems, 2018, DOI:10.1145/3231935.
* (EN) P. Ferragina e U. Scaiella, Fast and accurate annotation of short texts with Wikipedia pages, in IEEE Software, vol. 29, n. 1, 2012, DOI:10.1109/MS.2011.122. La versione su conferenza è apparsa in Procs ACM CIKM 2010
* (EN) M. Cornolti, P. Ferragina, M. Ciaramita, S. Rued e H. Schutze, SMAPH: A Piggyback Approach for Entity-Linking in Web Queries, in ACM Transactions on Information Systems, 2018, DOI:10.1145/3284102. La versione su conferenza è apparsa in Procs WWW, 2016. (Vincitore del concorso, sezione Short-Track, presso il laboratorio ERD, ospitato da ACM SIGIR 2014.)