research
∙
08/22/2023
Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions
Temporal graphs represent interactions between entities over time. Decid...
share
research
∙
08/18/2023
Wheeler maps
Motivated by challenges in pangenomic read alignment, we propose a gener...
research
∙
07/27/2023
Evaluating Regular Path Queries on Compressed Adjacency Matrices
Regular Path Queries (RPQs), which are essentially regular expressions t...
research
∙
06/07/2023
Maintaining the cycle structure of dynamic permutations
We present a new data structure for maintaining dynamic permutations, wh...
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...
research
∙
10/18/2022
Computing MEMs on Repetitive Text Collections
We consider the problem of computing the Maximal Exact Matches (MEMs) of...
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...
research
∙
06/03/2022
L-systems for Measuring Repetitiveness*
An L-system (for lossless compression) is a CPD0L-system extended with t...
research
∙
06/01/2022
Near-Optimal Search Time in δ-Optimal Space
Two recent lower bounds on the compressiblity of repetitive sequences, δ...
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...
research
∙
03/28/2022
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
As nowadays Machine Learning (ML) techniques are generating huge data co...
research
∙
11/08/2021
Time- and Space-Efficient Regular Path Queries on Graphs
We introduce a time- and space-efficient technique to solve regularpath ...
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...
research
∙
11/02/2021
MillenniumDB: A Persistent, Open-Source, Graph Database
In this systems paper, we present MillenniumDB: a novel graph database e...
research
∙
05/28/2021
On Stricter Reachable Repetitiveness Measures*
The size b of the smallest bidirectional macro scheme, which is arguably...
research
∙
03/29/2021
A Fast and Small Subsampled R-index
The r-index (Gagie et al., JACM 2020) represented a breakthrough in comp...
research
∙
11/25/2020
Grammar Compression By Induced Suffix Sorting
A grammar compression algorithm, called GCIS, is introduced in this work...
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...
research
∙
11/11/2020
PHONI: Streamed Matching Statistics with Multi-Genome References
Computing the matching statistics of patterns with respect to a text is ...
research
∙
10/14/2020
Contextual Pattern Matching
The research on indexing repetitive string collections has focused on th...
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...
research
∙
06/21/2020
PFP Data Structures
Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a p...
research
∙
04/06/2020
Indexing Highly Repetitive String Collections
Two decades ago, a breakthrough in indexing string collections made it p...
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...
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...
research
∙
02/27/2020
Semantrix: A Compressed Semantic Matrix
We present a compact data structure to represent both the duration and l...
research
∙
02/26/2020
Cell cycle and protein complex dynamics in discovering signaling pathways
Signaling pathways are responsible for the regulation of cell processes,...
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...
research
∙
11/21/2019
Implementing the Topological Model Succinctly
We show that the topological model, a semantically rich standard to repr...
research
∙
11/20/2019
Grammar Compressed Sequences with Rank/Select Support
Sequence representations supporting not only direct access to their symb...
research
∙
11/20/2019
Faster Dynamic Compressed d-ary Relations
The k^2-tree is a successful compact representation of binary relations ...
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...
research
∙
11/19/2019
Improved Compressed String Dictionaries
We introduce a new family of compressed data structures to efficiently s...
research
∙
11/11/2019
Dv2v: A Dynamic Variable-to-Variable Compressor
We present Dv2v, a new dynamic (one-pass) variable-to-variable compresso...
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...
research
∙
11/08/2019
On dynamic succinct graph representations
We address the problem of representing dynamic graphs using k^2-trees. T...
research
∙
10/16/2019
Tree-Shape Grammars for Random Access
Shape grammars are well known in the graphics and design communities but...
research
∙
10/04/2019
Towards a Definitive Measure of Repetitiveness
Unlike in statistical compression, where Shannon's entropy is a definiti...
research
∙
08/05/2019
Optimal Joins using Compact Data Structures
Worst-case optimal join algorithms have gained a lot of attention in the...
research
∙
06/03/2019
Rpair: Rescaling RePair with Rsync
Data compression is a powerful tool for managing massive but repetitive ...
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...
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...
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 ...
research
∙
01/29/2019
Simulating the DNA String Graph in Succinct Space
Converting a set of sequencing reads into a lossless compact data struct...
research
∙
11/30/2018
Faster Attractor-Based Indexes
String attractors are a novel combinatorial object encompassing most kno...
research
∙
11/06/2018
Tunneling on Wheeler Graphs
The Burrows-Wheeler Transform (BWT) is an important technique both in da...
research
∙
10/12/2018
Relative compression of trajectories
We present RCT, a new compact data structure to represent trajectories o...
research
∙
09/19/2018
The Read-Optimized Burrows-Wheeler Transform
The advent of high-throughput sequencing has resulted in massive genomic...
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...
research
∙
06/05/2018