Zobrazeno 1 - 10
of 238
pro vyhledávání: '"Manzini, Giovanni"'
Autor:
Tosoni, Francesco, Bille, Philip, Brunacci, Valerio, De Angelis, Alessio, Ferragina, Paolo, Manzini, Giovanni
Sparse matrix-vector multiplication (SpMV) is a fundamental operation in machine learning, scientific computing, and graph algorithms. In this paper, we investigate the space, time, and energy efficiency of SpMV using various compressed formats for l
Externí odkaz:
http://arxiv.org/abs/2409.18620
Given a text $T [1..n]$ over an alphabet of size $\sigma$ whose BWT has $r$ runs, we can store $T$ in $O \left( r \log \frac{n}{r} + r \log \sigma \right)$ bits such that we can answer $\psi$ queries in constant time.
Externí odkaz:
http://arxiv.org/abs/2408.04537
Autor:
Alanko, Jarno, Cenzato, Davide, Cotumaccio, Nicola, Kim, Sung-Hwan, Manzini, Giovanni, Prezza, Nicola
The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al. [DCC 2023] and Cotumaccio et al. [SPIRE 2023] extended the definition
Externí odkaz:
http://arxiv.org/abs/2404.14235
Autor:
Draesslerová, Dominika, Ahmed, Omar, Gagie, Travis, Holub, Jan, Langmead, Ben, Manzini, Giovanni, Navarro, Gonzalo
For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read, we can quickly choose a small subtree likely to contain the genome from which that read was drawn. Although popular classifiers
Externí odkaz:
http://arxiv.org/abs/2402.06935
We define a suffixient set for a text $T [1..n]$ to be a set $S$ of positions between 1 and $n$ such that, for any edge descending from a node $u$ to a node $v$ in the suffix tree of $T$, there is an element $s \in S$ such that $u$'s path label is a
Externí odkaz:
http://arxiv.org/abs/2312.01359
Autor:
Carfagna, Lorenzo, Manzini, Giovanni
In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the $\gamma$ measure defined in terms of the smallest string attractor, and the $\delta$ measure defined in terms of the number of disti
Externí odkaz:
http://arxiv.org/abs/2307.02629
Autor:
Conte, Alessio, Cotumaccio, Nicola, Gagie, Travis, Manzini, Giovanni, Prezza, Nicola, Sciortino, Marinella
Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPIRE 2010] proposed a time and space efficient algorithm for computing m
Externí odkaz:
http://arxiv.org/abs/2301.05338
The Burrows-Wheeler Transform (BWT) is often taught in undergraduate courses on algorithmic bioinformatics, because it underlies the FM-index and thus important tools such as Bowtie and BWA. Its admirers consider the BWT a thing of beauty but, despit
Externí odkaz:
http://arxiv.org/abs/2208.09840
Autor:
Giancarlo, Raffaele, Manzini, Giovanni, Restivo, Antonio, Rosone, Giovanna, Sciortino, Marinella
Introduced about thirty years ago in the field of Data Compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of e
Externí odkaz:
http://arxiv.org/abs/2205.05643
Autor:
Ferragina, Paolo, Gagie, Travis, Köppl, Dominik, Manzini, Giovanni, Navarro, Gonzalo, Striani, Manuel, Tosoni, Francesco
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 importance. In this article we propose a new lossless compression sche
Externí odkaz:
http://arxiv.org/abs/2203.14540