273 citations · 562 across the 24 of their papers we have counts for
14 papers · 1 filter
Extended Depth-First Representations of -trees
Gabriel Carmona, Paolo Ferragina, Giovanni Manzini +1
In this paper, we study static, computation-friendly, lossless compression formats for graphs, focusing on memory locality and operational efficiency of -trees. We observe tha…
Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
Paolo Ferragina, Filippo Lari
We study the problem of deriving compressibility measures for Piecewise Linear Approximations (PLAs), i.e., error-bounded approximations of a set of two-dimensional increasing data…
Toward Greener Matrix Operations by Lossless Compressed Formats
Francesco Tosoni, Philip Bille, Valerio Brunacci +3
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…
Balanced Learned Sort: a new learned model for fast and balanced item bucketing
Paolo Ferragina, Mattia Odorisio
This paper aims to better understand the strengths and limitations of adopting learned-based approaches in sequential sorting numerical data, via two main research steps. First, we…
Grafite: Taming Adversarial Queries with Optimal Range Filters
Marco Costa, Paolo Ferragina, Giorgio Vinciguerra
Range filters allow checking whether a query range intersects a given set of keys with a chance of returning a false positive answer, thus generalising the functionality of Bloom f…
Learned Monotone Minimal Perfect Hashing
Paolo Ferragina, Hans-Peter Lehmann, Peter Sanders +1
A Monotone Minimal Perfect Hash Function (MMPHF) constructed on a set S of keys is a function that maps each key in S to its rank. On keys not in S, the function returns an arbitra…
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…
The PGM-index: a multicriteria, compressed and learned approach to data indexing
Paolo Ferragina, Giorgio Vinciguerra
The recent introduction of learned indexes has shaken the foundations of the decades-old field of indexing data structures. Combining, or even replacing, classic design elements su…
Superseding traditional indexes by orchestrating learning and geometry
Giorgio Vinciguerra, Paolo Ferragina, Michele Miccinesi
We design the first learned index that solves the dictionary problem with time and space complexity provably better than classic data structures for hierarchical memories, such as…
Lightweight Data Indexing and Compression in External Memory
Paolo Ferragina, Travis Gagie, Giovanni Manzini
In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are light…
On optimally partitioning a text to improve its compression
Paolo Ferragina, Igor Nitto, Rossano Venturini
In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output th…
Bit-Optimal Lempel-Ziv compression
Paolo Ferragina, Igor Nitto, Rossano Venturini
One of the most famous and investigated lossless data-compression scheme is the one introduced by Lempel and Ziv about 40 years ago. This compression scheme is known as "dictionary…
String algorithms and data structures
Paolo Ferragina
The string-matching field has grown at a such complicated stage that various issues come into play when studying it: data structure and algorithmic design, database principles, com…
Compressed Text Indexes:From Theory to Practice!
Paolo Ferragina, Rodrigo Gonzalez, Gonzalo Navarro +1
A compressed full-text self-index represents a text in a compressed form and still answers queries efficiently. This technology represents a breakthrough over the text indexing tec…