The future of compressed data structures


July 21 - 22, 2020


Lipari Island, Italy

On November 2000, at the 41st Annual Symposium on Foundations of Computer Science, the paper “Opportunistic Data Structures with Applications” showed how the Burrows-Wheeler Transform (BWT), a powerful data transformation introduced in 1994 for data compression, could also be used for efficiently searching patterns in the BWT-compressed string. This result established for the first time that it is possible to compress a dataset up to the theoretical limit of its entropy and efficiently search for the occurrences of arbitrary substrings in it. The resulting data structure, called FM-index, turned out to be extremely useful in bioinformatics and indeed it is at the core of two alignment tools, among them it is worth mentioning BWA and Bowtie are widely used in BioMed laboratories around the world.

After the introduction of the FM-index, many researchers obtained other important results for compactly representing other kinds of data, in addition to strings, often maintaining optimal search speed. The overall outcome has been a flourish of theoretical results, algorithms, and software libraries that have provided solid theoretical and practical foundations for the field of Algorithmics which is now called Compressed Data Structures. In this era of big data the need for compressing them is even more stringent and challenging because of new types of data to be managed (as Neural Networks), of new computing architectures to be used (GPUs/TPUs), and of new sophisticated computational constraints that vary across users, devices and applications, and possibly evolve over time.

The goal of this event is to present current state-of-the-art and future challenges on this topic by bringing to the Lipari PhD School the topmost researchers in the field; we foresee strong interactions between audience and speakers in order to widen the knowledge of these powerful algorithmic techniques and identify new applications and open problems.

Workshop Organizers

Paolo Ferragina University of Pisa, Italy
Giovanni Manzini University of Piemonte Orientale, Italy


Lipari School Committee

Prof. Alfredo Ferro
Prof. Alfredo Pulvirenti
Prof. Rosalba Giugno
Dr. Salvatore Alaimo
Dr. Giovanni Micale

Lipari School Contacts

Prof. Alfredo Ferro
Università degli Studi di Catania
Dipartimento di Medicina Clinica e Sperimentale c/o Dipartimento di Matematica e Informatica
Viale A. Doria 6 - 95125 Catania - ITALY

+39 095 7383071
+39 095 7383087