2026-07-25T02:34:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12077 2024-03-06T10:49:17Z ddc:004 open_access

Indexing Compressed Text: A Tale of Time and Space (Invited Talk) Prezza, Nicola Compressed Text Indexing Text indexing is a classical algorithmic problem that has been studied for over four decades. The earliest optimal-time solution to the problem, the suffix tree [Weiner, 1973], dates back to 1973 and requires up to two orders of magnitude more space than the text to be stored. In the year 2000, two breakthrough works [Grossi and Vitter, 2000; Ferragina and Manzini, 2000] showed that this space overhead is not necessary: both the index and the text can be stored in a space proportional to the text’s entropy. These contributions had an enormous impact in bioinformatics: nowadays, the two most widely-used DNA aligners employ compressed indexes [Li and Durbin, 2009; Langmead et al., 2009]. In recent years, it became apparent that entropy had reached its limits: modern datasets (for example, collections of thousands of human genomes) are extremely large but very repetitive and, by its very definition, entropy cannot compress repetitive texts [S. Kreft and G. Navarro, 2013]. To overcome this problem, a new generation of indexes based on dictionary compressors (for example, LZ77 and run-length BWT) emerged [S. Kreft and G. Navarro, 2013; Gagie et al., 2020; F. Claude and G. Navarro, 2012], together with generalizations of the indexing problem to labeled graphs [Ferragina et al., 2009; Sirén et al., 2014; Travis Gagie et al., 2017]. This talk is a short and friendly survey of the landmarks of this fascinating path that took us from suffix trees to the most modern compressed indexes on labeled graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicola Prezza 2020 Is Part Of LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2020.3 urn:nbn:de:0030-drops-120772 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.3 eng https://creativecommons.org/licenses/by/3.0/legalcode