aalto1 untyped-item.component.html
Graph Indexing Beyond Wheeler Graphs
Loading...
Access rights
openAccess
CC BY
CC BY
Creative Commons license
Except where otherwised noted, this item's license is described as openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A3 Kirjan tai muun kokoomateoksen osa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
29
Series
OpenAccess Series in Informatics ; Volume 131
Abstract
After the discovery of the FM index, which linked the Burrows-Wheeler transform (BWT) to pattern matching on strings, several contemporaneous strands of research began on indexing more complex structures with the BWT, such as tries, finite languages, de Bruijn graphs, and aligned sequences. These directions can now be viewed as culminating in the theory of Wheeler Graphs, but sometimes they go beyond. This chapter reviews the significant body of “proto Wheeler Graph” indexes, many of which exploit characteristics of their specific case to outperform Wheeler graphs, especially in practice.
Description
Publisher Copyright: © Jarno N. Alanko, Elena Biagi, Massimo Equi, Veli Mäkinen, Simon J. Puglisi, Nicola Rizzo, Kunihiko Sadakane, and Jouni Sirén.
Other note
Citation
Alanko, J N, Biagi, E, Equi, M, Mäkinen, V, Puglisi, S J, Rizzo, N, Sadakane, K & Sirén, J 2025, Graph Indexing Beyond Wheeler Graphs. in P Ferragina, T Gagie & G Navarro (eds), The Expanding World of Compressed Data : A Festschrift for Giovanni Manzini's 60th Birthday., 13, OpenAccess Series in Informatics, vol. 131, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-29, Expanding World of Compressed Data, Venice, Italy, 25/07/2025. https://doi.org/10.4230/OASIcs.Manzini.13