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: Paolo Ferragina and Travis Gagie)
Giovanni Manzini Two-Dimensional Compression and Indexing Revisited
10:00–10:10	Handover of Feschriften
Chairs: Paolo Ferragina, Travis Gagie and Nicola Prezza
10:10–10:30 Paolo Ferragina, Raffaele Giancarlo, Roberto Grossi, Giovanni Manzini, Giovanna Rosone, Rossano Venturini, Jeffrey Scott Vitter. Wavelet Tree 10:30–10:50 Diego Díaz-Domínguez, Lavinia Egidi, Veronica Guerrini, Felipe A. Louza, Giovanna Rosone. Algorithms for Computing Very Large BWTs: a Short Survey
10:50–11:20	Coffee Break
Chair: Gonzalo Navarro
11:20–11:40 Gabriele Fici, Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, Marinella Sciortino. BWT and Combinatorics on Words 11:40–12:00 Nicola Cotumaccio, Giovanna D’Agostino, Alberto Policriti, Daniel Gibney, Nicola Prezza, Sharma V. Thankachan. Wheeler Graphs and Wheeler Languages 12:00–12:20 Jarno N. Alanko, Elena Biagi, Massimo Equi, Veli Mäkinen, Simon J. Puglisi, Nicola Rizzo, Kunihiko Sadakane, Jouni Sirén. Graph Indexing beyond Wheeler Graphs 12:20–12:40 Diego Arroyuelo, Gonzalo Navarro. BWT Indexes for Optimal Joins in Graph Databases
12:40–14:15	Lunch (not provided)
14:15–15:15	Invited Talk 2 (Chair: Alessio Conte and Jeffrey Scott Vitter)
Roberto Grossi From Strings to Graphs, and Back Again, in Pattern Matching Algorithms and Data Structures
15:15–15:35 Nathaniel K. Brown, Travis Gagie, Giovanni Manzini, Gonzalo Navarro, Marinella Sciortino. Faster run-length compressed suffix arrays
15:35–16:15	Coffee Break
Chair: Andrea Marino
16:15–16:35 Jarno N. Alanko, Philip Bille, Inge Li Gørtz, Gonzalo Navarro, Simon J. Puglisi. Compact Data Structures for Collections of Sets 16:35–16:55 Xiaoyang Chen, Yujia Wang, Hongwei Huo, Jeffrey Scott Vitter. An Efficient Heuristic for Graph Edit Distance 16:55–17:15 Massimo Equi. Conditional Lower Bounds for String Matching in Labelled Graphs 17:15–17:35 Alessio Conte, Kazuhiro Kurita, Andrea Marino, Giulia Punzi, Takeaki Uno, Kunihiro Wasa. Designing Output Sensitive Algorithms for Maximal Subgraph Enumeration
19:00	Workshop dinner at OKE Zattere (participants pay individually) (Filling out this Google Form is required to participate)

Pictures

---