research
∙
08/18/2023
ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
A minimal perfect hash function (MPHF) maps a set S of n keys to the fir...
share
research
∙
07/02/2023
What if we tried Less Power? – Lessons from studying the power of choices in hashing-based data structures
In the first part of this survey, we review how the power of two choices...
research
∙
04/18/2023
Sliding Block Hashing (Slick) – Basic Algorithmic Ideas
We present Sliding Block Hashing (Slick), a simple hash table data struc...
research
∙
04/14/2023
Optimal Uncoordinated Unique IDs
In the Uncoordinated Unique Identifiers Problem (UUIDP) there are n inde...
research
∙
11/07/2022
Simple Set Sketching
Imagine handling collisions in a hash table by storing, in each cell, th...
research
∙
10/04/2022
SicHash – Small Irregular Cuckoo Tables for Perfect Hashing
A Perfect Hash Function (PHF) is a hash function that has no collisions ...
research
∙
02/11/2022
Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold
When it comes to hash tables, the only truly respectable insertion time ...
research
∙
11/12/2021
Approximate Membership Query Filters with a False Positive Free Set
In the last decade, significant efforts have been made to reduce the fal...
research
∙
09/04/2021
Fast Succinct Retrieval and Approximate Membership using Ribbon
A retrieval data structure for a static function f:S→{0,1}^r supports qu...
research
∙
03/03/2021
Ribbon filter: practically smaller than Bloom and Xor
Filter data structures over-approximate a set of hashable keys, i.e. set...
research
∙
01/28/2020
Peeling Close to the Orientability Threshold: Spatial Coupling in Hashing-Based Data Structures
Hypergraphs with random hyperedges underlie various data structures wher...
research
∙
07/10/2019
Dense Peelable Random Uniform Hypergraphs
We describe a new family of k-uniform hypergraphs with independent rando...
research
∙
04/30/2018
