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).
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 has 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.