Gonzalo Navarro

research

∙ 08/22/2023

Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions

Temporal graphs represent interactions between entities over time. Decid...

0 Luiz Fernando Afra Brito, et al. ∙

research

∙ 08/18/2023

Wheeler maps

Motivated by challenges in pangenomic read alignment, we propose a gener...

0 Andrej Balaz, et al. ∙

research

∙ 07/27/2023

Evaluating Regular Path Queries on Compressed Adjacency Matrices

Regular Path Queries (RPQs), which are essentially regular expressions t...

0 Diego Arroyuelo, et al. ∙

research

∙ 06/07/2023

Maintaining the cycle structure of dynamic permutations

We present a new data structure for maintaining dynamic permutations, wh...

0 Zsuzsanna Lipták, et al. ∙

research

∙ 12/05/2022

Space-efficient conversions from SLPs

Given a straight-line program with g rules for a text T [1..n], we can b...

0 Travis Gagie, et al. ∙

research

∙ 10/18/2022

Computing MEMs on Repetitive Text Collections

We consider the problem of computing the Maximal Exact Matches (MEMs) of...

0 Gonzalo Navarro, et al. ∙

research

∙ 06/27/2022

Balancing Run-Length Straight-Line Programs*

It was recently proved that any SLP generating a given string w can be t...

0 Gonzalo Navarro, et al. ∙

research

∙ 06/03/2022

L-systems for Measuring Repetitiveness*

An L-system (for lossless compression) is a CPD0L-system extended with t...

0 Gonzalo Navarro, et al. ∙

research

∙ 06/01/2022

Near-Optimal Search Time in δ-Optimal Space

Two recent lower bounds on the compressiblity of repetitive sequences, δ...

0 Tomasz Kociumaka, et al. ∙

research

∙ 04/12/2022

Efficient Construction of the BWT for Repetitive Text Using String Compression

We present a new semi-external algorithm that builds the Burrows-Wheeler...

0 Diego Díaz-Domínguez, et al. ∙

research

∙ 03/28/2022

Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices

As nowadays Machine Learning (ML) techniques are generating huge data co...

0 Paolo Ferragina, et al. ∙

research

∙ 11/08/2021

Time- and Space-Efficient Regular Path Queries on Graphs

We introduce a time- and space-efficient technique to solve regularpath ...

0 Diego Arroyuelo, et al. ∙

research

∙ 11/03/2021

HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances

We propose a new representation of the offsets of the Lempel-Ziv (LZ) fa...

0 Dominik Köppl, et al. ∙

research

∙ 11/02/2021

MillenniumDB: A Persistent, Open-Source, Graph Database

In this systems paper, we present MillenniumDB: a novel graph database e...

0 Domagoj Vrgoč, et al. ∙

research

∙ 05/28/2021

On Stricter Reachable Repetitiveness Measures*

The size b of the smallest bidirectional macro scheme, which is arguably...

0 Gonzalo Navarro, et al. ∙

research

∙ 03/29/2021

A Fast and Small Subsampled R-index

The r-index (Gagie et al., JACM 2020) represented a breakthrough in comp...

0 Dustin Cobas, et al. ∙

research

∙ 11/25/2020

Grammar Compression By Induced Suffix Sorting

A grammar compression algorithm, called GCIS, is introduced in this work...

0 Daniel S. N. Nunes, et al. ∙

research

∙ 11/13/2020

A grammar compressor for collections of reads with applications to the construction of the BWT

We describe a grammar for DNA sequencing reads from which we can compute...

0 Diego Díaz-Domínguez, et al. ∙

research

∙ 11/11/2020

PHONI: Streamed Matching Statistics with Multi-Genome References

Computing the matching statistics of patterns with respect to a text is ...

0 Christina Boucher, et al. ∙

research

∙ 10/14/2020

Contextual Pattern Matching

The research on indexing repetitive string collections has focused on th...

0 Gonzalo Navarro, et al. ∙

research

∙ 09/21/2020

Space/time-efficient RDF stores based on circular suffix sorting

In recent years, RDF has gained popularity as a format for the standardi...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 06/21/2020

PFP Data Structures

Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a p...

0 Christina Boucher, et al. ∙

research

∙ 04/06/2020

Indexing Highly Repetitive String Collections

Two decades ago, a breakthrough in indexing string collections made it p...

0 Gonzalo Navarro, et al. ∙

research

∙ 04/01/2020

Grammar-Compressed Indexes with Logarithmic Search Time

Let a text T[1..n] be the only string generated by a context-free gramma...

0 Francisco Claude, et al. ∙

research

∙ 03/04/2020

Approximating Optimal Bidirectional Macro Schemes

Lempel-Ziv is an easy-to-compute member of a wide family of so-called ma...

0 Luís M. S. Russo, et al. ∙

research

∙ 02/27/2020

Semantrix: A Compressed Semantic Matrix

We present a compact data structure to represent both the duration and l...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 02/26/2020

Cell cycle and protein complex dynamics in discovering signaling pathways

Signaling pathways are responsible for the regulation of cell processes,...

0 Daniel Inostroza, et al. ∙

research

∙ 12/26/2019

On the Reproducibility of Experiments of Indexing Repetitive Document Collections

This work introduces a companion reproducible paper with the aim of allo...

0 Antonio Fariña, et al. ∙

research

∙ 11/21/2019

Implementing the Topological Model Succinctly

We show that the topological model, a semantically rich standard to repr...

0 José Fuentes-Sepúlveda, et al. ∙

research

∙ 11/20/2019

Grammar Compressed Sequences with Rank/Select Support

Sequence representations supporting not only direct access to their symb...

0 Alberto Ordóñez, et al. ∙

research

∙ 11/20/2019

Faster Dynamic Compressed d-ary Relations

The k^2-tree is a successful compact representation of binary relations ...

0 Diego Arroyuelo, et al. ∙

research

∙ 11/19/2019

Extending General Compact Querieable Representations to GIS Applications

The raster model is commonly used for the representation of images in ma...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 11/19/2019

Improved Compressed String Dictionaries

We introduce a new family of compressed data structures to efficiently s...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 11/11/2019

Dv2v: A Dynamic Variable-to-Variable Compressor

We present Dv2v, a new dynamic (one-pass) variable-to-variable compresso...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 11/11/2019

GraCT: A Grammar-based Compressed Index for Trajectory Data

We introduce a compressed data structure for the storage of free traject...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 11/08/2019

On dynamic succinct graph representations

We address the problem of representing dynamic graphs using k^2-trees. T...

0 Miguel E. Coimbra, et al. ∙

research

∙ 10/16/2019

Tree-Shape Grammars for Random Access

Shape grammars are well known in the graphics and design communities but...

0 Travis Gagie, et al. ∙

research

∙ 10/04/2019

Towards a Definitive Measure of Repetitiveness

Unlike in statistical compression, where Shannon's entropy is a definiti...

0 Tomasz Kociumaka, et al. ∙

research

∙ 08/05/2019

Optimal Joins using Compact Data Structures

Worst-case optimal join algorithms have gained a lot of attention in the...

0 Gonzalo Navarro, et al. ∙

research

∙ 06/03/2019

Rpair: Rescaling RePair with Rsync

Data compression is a powerful tool for managing massive but repetitive ...

0 Travis Gagie, et al. ∙

research

∙ 03/05/2019

Lempel-Ziv-like Parsing in Small Space

Lempel-Ziv (LZ77 or, briefly, LZ) is one of the most effective and widel...

0 Daniel Valenzuela, et al. ∙

research

∙ 02/20/2019

Fast, Small, and Simple Document Listing on Repetitive Text Collections

Document listing on string collections is the task of finding all docume...

0 Dustin Cobas, et al. ∙

research

∙ 02/08/2019

Faster Repetition-Aware Compressed Suffix Trees based on Block Trees

Suffix trees are a fundamental data structure in stringology, but their ...

0 Manuel Cáceres, et al. ∙

research

∙ 01/29/2019

Simulating the DNA String Graph in Succinct Space

Converting a set of sequencing reads into a lossless compact data struct...

0 Diego Díaz-Domínguez, et al. ∙

research

∙ 11/30/2018

Faster Attractor-Based Indexes

String attractors are a novel combinatorial object encompassing most kno...

0 Gonzalo Navarro, et al. ∙

research

∙ 11/06/2018

Tunneling on Wheeler Graphs

The Burrows-Wheeler Transform (BWT) is an important technique both in da...

0 Jarno Alanko, et al. ∙

research

∙ 10/12/2018

Relative compression of trajectories

We present RCT, a new compact data structure to represent trajectories o...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 09/19/2018

The Read-Optimized Burrows-Wheeler Transform

The advent of high-throughput sequencing has resulted in massive genomic...

0 Travis Gagie, et al. ∙

research

∙ 09/08/2018

Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space

Indexing highly repetitive texts --- such as genomic databases, software...

0 Travis Gagie, et al. ∙

research

∙ 06/05/2018

Tree Path Majority Data Structures

We present the first solution to τ-majorities on tree paths. Given a tre...

0 Travis Gagie, et al. ∙

Gonzalo Navarro

Featured Co-authors