70 citations · 190 across the 15 of their papers we have counts for
9 papers · 1 filter
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…
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…
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…