(Pro-)Seminar Modern Minimal Perfect Hashing: A Survey

Dear all, 

next week there will be a presentation at the MPI on perfect hashing (see abstract below). As the topic is very closely related to our seminar, we recommend that you attend or listen to it online (but of course attendance is not mandatory).
  

This month, Guy Even will give the talk:

"How to Manage a Hotel Desk? Stable Perfect Hashing
in the Incremental Setting"

The talk will take place Wednesday, November 5, 2025
at 12:15 p.m. in room 002 (building E1 5)

or via Zoom:
https://zoom.us/j/99715655535?pwd=MHAxdnU5WE1BeEVUQUw5R041Ry9XUT09

Abstract:

Many modern applications—from large-scale databases to network routers
and genome repositories—depend on maintaining large dynamic sets of
elements. Efficient management of these sets requires data structures
that can quickly support insertions and deletions, answer queries such
as “Is this element in the set?” or “What is the value associated with
this element?”, and assign distinct short keys to elements as the set
grows.

The field of data structures is concerned with specifying functionality,
abstracting computational models, designing efficient representations,
and analyzing the running time and memory requirements of algorithms
over these representations. Classical data structures developed for
representing sets include dictionaries, retrieval data structures,
filters, and perfect hashing.

In this talk, I will explore these issues through the lens of perfect
hashing, a method for assigning each element a distinct identifier, or
hashcode, with no collisions. We will focus on how to simultaneously
satisfy several competing design goals:

Small space: using near-optimal memory proportional to the set’s size.
Fast operations: supporting constant-time insertions, deletions, and
queries.
Low redundancy: keeping the range of hashcodes close to the set’s size.
Stability: ensuring that each element’s hashcode remains unchanged while
it stays in the set.
Extendability: adapting automatically to unknown or growing data sizes.
This talk is based on joint work with Ioana Bercea.