143 citations · 504 across the 80 of their papers we have counts for
96 papers · 1 filter
Wheeler maps
Andrej Baláz, Travis Gagie, Adrián Goga +4
Motivated by challenges in pangenomic read alignment, we propose a generalization of Wheeler graphs that we call Wheeler maps. A Wheeler map stores a text and an assignme…
Evaluating Regular Path Queries on Compressed Adjacency Matrices
Diego Arroyuelo, Adrián Gómez-Brandón, Gonzalo Navarro
Regular Path Queries (RPQs), which are essentially regular expressions to be matched against the labels of paths in labeled graphs, are at the core of graph database query language…
Maintaining the cycle structure of dynamic permutations
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro
We present a new data structure for maintaining dynamic permutations, which we call a . The FST allows one to efficiently maintain the cycle s…
Computing MEMs and Relatives on Repetitive Text Collections
Gonzalo Navarro
We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern on a large repetitive text collection , which is represented as a (h…
Balancing Run-Length Straight-Line Programs*
Gonzalo Navarro, Francisco Olivares, Cristian Urbina
It was recently proved that any SLP generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We show that this r…
L-systems for Measuring Repetitiveness*
Gonzalo Navarro, Cristian Urbina
An L-system (for lossless compression) is a CPD0L-system extended with two parameters and , which determines unambiguously a string , where is the mo…
Near-Optimal Search Time in -Optimal Space, and Vice Versa
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares
Two recent lower bounds on the compressibility of repetitive sequences, , have received much attention. It has been shown that a length- string over an alphabet of s…
Efficient Construction of the BWT for Repetitive Text Using String Compression
Diego Díaz-Domínguez, Gonzalo Navarro
We present a new semi-external algorithm that builds the Burrows--Wheeler transform variant of Bauer et al. (a.k.a., BCR BWT) in linear expected time. Our method uses compression t…
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
Paolo Ferragina, Travis Gagie, Dominik Köppl +4
As nowadays Machine Learning (ML) techniques are generating huge data collections, the problem of how to efficiently engineer their storage and operations is becoming of paramount…
HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
Dominik Köppl, Gonzalo Navarro, Nicola Prezza
We propose a new representation of the offsets of the Lempel-Ziv (LZ) factorization based on the co-lexicographic order of the processed prefixes. The selected offsets tend to appr…
On Stricter Reachable Repetitiveness Measures*
Gonzalo Navarro, Cristian Urbina
The size of the smallest bidirectional macro scheme, which is arguably the most general copy-paste scheme to generate a given sequence, is considered to be the strictest reacha…
A Fast and Small Subsampled R-index
Dustin Cobas, Travis Gagie, Gonzalo Navarro
The -index (Gagie et al., JACM 2020) represented a breakthrough in compressed indexing of repetitive text collections, outperforming its alternatives by orders of magnitude. Its…
Grammar Compression By Induced Suffix Sorting
Daniel S. N. Nunes, Felipe A. Louza, Simon Gog +2
A grammar compression algorithm, called GCIS, is introduced in this work. GCIS is based on the induced suffix sorting algorithm SAIS, presented by Nong et al. in 2009. The proposed…
A grammar compressor for collections of reads with applications to the construction of the BWT
Diego Díaz-Domínguez, Gonzalo Navarro
We describe a grammar for DNA sequencing reads from which we can compute the BWT directly. Our motivation is to perform in succinct space genomic analyses that require complex stri…
PHONI: Streamed Matching Statistics with Multi-Genome References
Christina Boucher, Travis Gagie, Tomohiro I +6
Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic data…
Contextual Pattern Matching
Gonzalo Navarro
The research on indexing repetitive string collections has focused on the same search problems used for regular string collections, though they can make little sense in this scenar…
Space/time-efficient RDF stores based on circular suffix sorting
Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo +2
In recent years, RDF has gained popularity as a format for the standardized publication and exchange of information in the Web of Data. In this paper we introduce RDFCSA, a data st…
PFP Data Structures
Christina Boucher, Ondřej Cvacho, Travis Gagie +4
Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a…
Indexing Highly Repetitive String Collections
Gonzalo Navarro
Two decades ago, a breakthrough in indexing string collections made it possible to represent them within their compressed space while at the same time offering indexed search funct…
Grammar-Compressed Indexes with Logarithmic Search Time
Francisco Claude, Gonzalo Navarro, Alejandro Pacheco
Let a text be the only string generated by a context-free grammar with (terminal and nonterminal) symbols, and of size (measured as the sum of the lengths of the…
Approximating Optimal Bidirectional Macro Schemes
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro +1
Lempel-Ziv is an easy-to-compute member of a wide family of so-called macro schemes; it restricts pointers to go in one direction only. Optimal bidirectional macro schemes are NP-c…
Semantrix: A Compressed Semantic Matrix
Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro +1
We present a compact data structure to represent both the duration and length of homogeneous segments of trajectories from moving objects in a way that, as a data warehouse, it all…
On the Reproducibility of Experiments of Indexing Repetitive Document Collections
Antonio Fariña, Miguel A. Martínez-Prieto, Francisco Claude +4
This work introduces a companion reproducible paper with the aim of allowing the exact replication of the methods, experiments, and results discussed in a previous work [5]. In tha…
On dynamic succinct graph representations
Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo +3
We address the problem of representing dynamic graphs using -trees. The -tree data structure is one of the succinct data structures proposed for representing static graph…