Next Article in Journal
On Nash Equilibria in Non-Cooperative All-Optical Networks
Previous Article in Journal
Special Issue on Process Mining and Emerging Applications
Previous Article in Special Issue
Re-Pair in Small Space
Open AccessArticle

Subpath Queries on Compressed Graphs: A Survey

Department of Environmental Sciences, Informatics and Statistics, Ca’ Foscari University, Dorsoduro, 3246, 30123 Venice, Italy
Received: 19 November 2020 / Revised: 30 December 2020 / Accepted: 3 January 2021 / Published: 5 January 2021
(This article belongs to the Special Issue Combinatorial Methods for String Processing)
Text indexing is a classical algorithmic problem that has been studied for over four decades: given a text T, pre-process it off-line so that, later, we can quickly count and locate the occurrences of any string (the query pattern) in T in time proportional to the query’s length. The earliest optimal-time solution to the problem, the suffix tree, dates back to 1973 and requires up to two orders of magnitude more space than the plain text just to be stored. In the year 2000, two breakthrough works showed that efficient queries can be achieved without this space overhead: a fast index be stored in a space proportional to the text’s entropy. These contributions had an enormous impact in bioinformatics: today, virtually any DNA aligner employs compressed indexes. Recent trends considered more powerful compression schemes (dictionary compressors) and generalizations of the problem to labeled graphs: after all, texts can be viewed as labeled directed paths. In turn, since finite state automata can be considered as a particular case of labeled graphs, these findings created a bridge between the fields of compressed indexing and regular language theory, ultimately allowing to index regular languages and promising to shed new light on problems, such as regular expression matching. This survey is a gentle introduction to the main landmarks of the fascinating journey that took us from suffix trees to today’s compressed indexes for labeled graphs and regular languages. View Full-Text
Keywords: indexing; compressed data structures; labeled graphs indexing; compressed data structures; labeled graphs
Show Figures

Figure 1

MDPI and ACS Style

Prezza, N. Subpath Queries on Compressed Graphs: A Survey. Algorithms 2021, 14, 14. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010014

AMA Style

Prezza N. Subpath Queries on Compressed Graphs: A Survey. Algorithms. 2021; 14(1):14. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010014

Chicago/Turabian Style

Prezza, Nicola. 2021. "Subpath Queries on Compressed Graphs: A Survey" Algorithms 14, no. 1: 14. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010014

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Search more from Scilit
 
Search
Back to TopTop