SEA 2025

Workshop "25 Years of Compressed Self-Indexes"

On July 25, 2025, there will be a workshop on Compressed Self-Indexes at the same venue. The occasion of the workshop is the 25th anniversary of the following two important data structures:

• FM-index
  Paolo Ferragina, Giovanni Manzini.
  Opportunistic Data Structures with Applications.
  41st Annual Symposium on Foundations of Computer Science (FOCS '00).
  Awarded with the Paris Kanellakis Award '22.
• Compressed Suffix Array
  Roberto Grossi, Jeffrey Scott Vitter.
  Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching.
  32nd Annual ACM Symposium on Theory of Computing (STOC '00).

The workshop will feature invited talks by Giovanni Manzini and Roberto Grossi as well as contributed talks on related topics. The program of the workshop is chaired by Ruben Becker.

Workshop Registration

Participation in the workshop is free, but we kindly ask all attendees to register in advance using the registration link.

Invited Speakers

---

Giovanni Manzini

University of Pisa, Italy

Two-Dimensional Compression and Indexing Revisited ▼

Since the introduction of compressed self-indices for strings, numerous efforts have been made to extend this powerful concept to two-dimensional structures. However, these attempts have encountered significant challenges and limited success. In this talk, we will review the current state of two-dimensional compression and indexing, exploring the complexities that make this problem particularly difficult. Additionally, we will discuss recent ideas that may pave the way for progress on this challenging topic.

Roberto Grossi

University of Pisa, Italy

From Strings to Graphs, and Back Again, in Pattern Matching Algorithms and Data Structures ▼

In recent years, the connections between strings and graphs have driven the design of algorithms and data structures for pattern matching and enumeration. This talk highlights our latest contributions to this interplay, showcasing how some string techniques have been effectively adapted to handle (large-scale) graph enumeration problems, and vice versa.

Program

---

Friday, July 25, 2025

9:00–9:15	Welcome
9:15–10:00	Invited Talk 1 (Chairs: Nicola Prezza and Paolo Ferragina)
Giovanni Manzini Two-Dimensional Compression and Indexing Revisited
10:00–10:20 Contributed Talk 1 10:20–10:40 Contributed Talk 2
10:40–11:20	Coffee Break
Chair: Gonzalo Navarro
11:20–11:40 Contributed Talk 3 11:40–12:00 Contributed Talk 4 12:00–12:20 Contributed Talk 5 12:20–12:40 Contributed Talk 6
12:40–14:15	Lunch (not provided)
14:15–15:15	Invited Talk 2 (Chair: Alessio Conte)
Roberto Grossi From Strings to Graphs, and Back Again, in Pattern Matching Algorithms and Data Structures
15:15–15:35 Contributed Talk 7
15:35–16:15	Coffee Break
Chair: Andrea Marino
16:15–16:35 Contributed Talk 8 16:35–16:55 Contributed Talk 9 16:55–17:15 Contributed Talk 10 17:15–17:35 Contributed Talk 11
19:00	Workshop dinner at OKE Zattere (Filling out this Google Form is required to participate)