70 citations · 190 across the 15 of their papers we have counts for
17 papers
Modern Minimal Perfect Hashing: A Survey
Hans-Peter Lehmann, Thomas Mueller, Rasmus Pagh +4
Given a set of keys, a perfect hash function for maps the keys in to the first integers without collisions. It may return an arbitrary result for any key…
U-index: A Universal Indexing Framework for Matching Long Patterns
Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp +4
Text indexing is a fundamental and well-studied problem. Classic solutions either replace the original text with a compressed representation, e.g., the FM-index and its variants, o…
PHOBIC: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding
Stefan Hermann, Hans-Peter Lehmann, Giulio Ermanno Pibiri +2
A minimal perfect hash function (MPHF) maps a set of n keys to {1, ..., n} without collisions. Such functions find widespread application e.g. in bioinformatics and databases. In t…
Verifiable Boosted Tree Ensembles
Stefano Calzavara, Lorenzo Cazzaro, Claudio Lucchese +1
Verifiable learning advocates for training machine learning models amenable to efficient security verification. Prior research demonstrated that specific classes of decision tree e…
Verifiable Learning for Robust Tree Ensembles
Stefano Calzavara, Lorenzo Cazzaro, Giulio Ermanno Pibiri +1
Verifying the robustness of machine learning models against evasion attacks at test time is an important research problem. Unfortunately, prior work established that this problem i…
Locality-Preserving Minimal Perfect Hashing of k-mers
Giulio Ermanno Pibiri, Yoshihiro Shibuya, Antoine Limasset
Minimal perfect hashing is the problem of mapping a static set of distinct keys into the address space bijectively. It is well-known that bits are…
Parallel and External-Memory Construction of Minimal Perfect Hash Functions with PTHash
Giulio Ermanno Pibiri, Roberto Trani
A function is a minimal perfect hash function for a set of size , if bijectively maps into the first natural numbers. Th…
PTHash: Revisiting FCH Minimal Perfect Hashing
Giulio Ermanno Pibiri, Roberto Trani
Given a set of distinct keys, a function that bijectively maps the keys of into the range is called a minimal perfect hash function for . Algo…
Rank/Select Queries over Mutable Bitmaps
Giulio Ermanno Pibiri, Shunsuke Kanda
The problem of answering rank/select queries over a bitmap is of utmost importance for many succinct data structures. When the bitmap does not change, many solutions exist in the t…
Efficient and Effective Query Auto-Completion
Simon Gog, Giulio Ermanno Pibiri, Rossano Venturini
Query Auto-Completion (QAC) is an ubiquitous feature of modern textual search systems, suggesting possible ways of completing the query being typed by the user. Efficiency is cruci…
Practical Trade-Offs for the Prefix-Sum Problem
Giulio Ermanno Pibiri, Rossano Venturini
Given an integer array A, the prefix-sum problem is to answer sum(i) queries that return the sum of the elements in A[0..i], knowing that the integers in A can be changed. It is a…
Succinct Dynamic Ordered Sets with Random Access
Giulio Ermanno Pibiri, Rossano Venturini
The representation of a dynamic ordered set of integer keys drawn from a universe of size is a fundamental data structuring problem. Many solutions to this problem achieve…
Techniques for Inverted Index Compression
Giulio Ermanno Pibiri, Rossano Venturini
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of…
On Slicing Sorted Integer Sequences
Giulio Ermanno Pibiri
Representing sorted integer sequences in small space is a central problem for large-scale retrieval systems such as Web search engines. Efficient query resolution, e.g., intersecti…
Compressed Indexes for Fast Search of Semantic Data
Raffaele Perego, Giulio Ermanno Pibiri, Rossano Venturini
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is devising a compressed data structure to compactly represent RDF triple…
Handling Massive N-Gram Datasets Efficiently
Giulio Ermanno Pibiri, Rossano Venturini
This paper deals with the two fundamental problems concerning the handling of large n-gram language models: indexing, that is compressing the n-gram strings and associated satellit…
On Optimally Partitioning Variable-Byte Codes
Giulio Ermanno Pibiri, Rossano Venturini
The ubiquitous Variable-Byte encoding is one of the fastest compressed representation for integer sequences. However, its compression ratio is usually not competitive with other mo…