The future of compressed data structures

July 19th - July 20th, 2022


Aim & Scope

In 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, was instrumental in bioinformatics, and indeed it is at the core of two alignment tools. Among them, it is worth mentioning that BWA and Bowtie are widely used in BioMed laboratories worldwide.

After introducing the FM-index, many researchers obtained other significant results for compactly representing different kinds of data and strings, often maintaining optimal search speed. The overall effect 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), new computing architectures to be used (GPUs/TPUs), and sophisticated computational constraints that vary across users, devices and applications, and possibly evolve.

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

Travel and accommodation

Participants will be arranged in comfortable hotels at very special rates. The conference room (located at Hotel Giardino sul Mare, Via Maddalena, Lipari) is air-conditioned and equipped with all conference materials. Special areas are reserved to the students for the afternoon coursework and study. The island of Lipari can be easily reached from Milazzo, Palermo, Naples, Messina, and Reggio Calabria by ferry or hydrofoil (50 minutes from Milazzo).


Participants can apply to the Workshop or the Lipari School on Computational Complex and Social Systems. For details regarding the application to the school, please refer to the website

The registration fee for the workshop participants is 150€, which covers participation in the Workshop, materials, and coffee breaks. Transports and social events are not included.

Applications can be submitted up to July 1st, 2022

Applicants should include an updated link to an official website. In case of cancellation after fees payments, a 25% penalty will be applied. In the case of credit card payment, processing fees cannot be reimbursed. Payment must be received as soon as possible, and in any case, no later than July 1st, 2022. Only wire transfers or credit card payments can be accepted.