Search Results

Documents authored by Hermann, Stefan

Artifact
Software
DOI: 10.4230/artifacts.27680
RagnarGrootKoerkamp/static-hash-sets

Authors: Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, and Stefan Walzer

Abstract
Cite as

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, Stefan Walzer. RagnarGrootKoerkamp/static-hash-sets (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27680,
   title = {{RagnarGrootKoerkamp/static-hash-sets}}, 
   author = {Groot Koerkamp, Ragnar and Hermann, Stefan and Sanders, Peter and Walzer, Stefan},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:d8b8fa726bc8cc741a074c79b7d9bbf0ef0b69e7;origin=https://github.com/RagnarGrootKoerkamp/static-hash-sets;visit=swh:1:snp:df75020c8884cdf5c6ad5b13010f67c098396447;anchor=swh:1:rev:ca72e3fe2ef47c963fc059d98254ccc23ff8b6d5}{\texttt{swh:1:dir:d8b8fa726bc8cc741a074c79b7d9bbf0ef0b69e7}} (visited on 2026-08-25)},
   url = {https://github.com/RagnarGrootKoerkamp/static-hash-sets},
   doi = {10.4230/artifacts.27680},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.15
Deconstructed "Learned" Indexes and Their Smoothed Analysis

Authors: Stefan Hermann, Mattia Odorisio, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Data structures that maintain a sorted sequence are crucial for many applications. There is a zoo of variants with recent particular interest in "learned" indexes that accelerate operations by learning the distribution of the data. This paper helps to bring some order to this complex situation. We identify important building blocks and model the input using smoothed analysis where an adversary can control the dynamically changing input except for a small amount of noise. Within a resulting design space of data structures, we prove that already a simple 2-level data structure with minimal learning can achieve constant operation times in many situations: PARROT partitions the input into equal size parts, within which keys are approximately uniformly distributed. In many of our experiments, PARROT performs very well compared to state-of-the-art learned indexes, being 2× faster than the well known ALEX and LIPP indexes on large datasets, and 10× faster than a well engineered standard B-Tree.
Cite as

Stefan Hermann, Mattia Odorisio, Peter Sanders, and Stefan Walzer. Deconstructed "Learned" Indexes and Their Smoothed Analysis. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 15:1-15:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hermann_et_al:LIPIcs.ESA.2026.15,
  author =	{Hermann, Stefan and Odorisio, Mattia and Sanders, Peter and Walzer, Stefan},
  title =	{{Deconstructed "Learned" Indexes and Their Smoothed Analysis}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{15:1--15:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.15},
  URN =		{urn:nbn:de:0030-drops-271518},
  doi =		{10.4230/LIPIcs.ESA.2026.15},
  annote =	{Keywords: Learned data structure, sorted sequence, index data structure, smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.20
Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables

Authors: Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of n keys to n bins without collisions. Two natural generalizations are minimal k-PHFs where n keys are mapped to n/k bins of capacity k each, and (non-minimal) PHFs with load factor α < 1 where the number of bins is increased by a factor of 1/α, resulting in spare capacity. While there has been a recent surge of interest in perfect hashing generally, non-minimal k-PHFs have not been systematically studied despite a natural use case of speeding up static hash tables: The idea is that a small cache-resident k-PHF maps each key x to a cache-line-sized bin of capacity k where x resides. Ideally, this yields a branchless lookup operation with a single cache miss working at high load factors for positive and negative queries alike. Our main theoretical contribution is to determine tight space lower bounds for k-PHFs for all pairs of α ∈ (0,1] and k ≥ 1. It turns out that combining α < 1 and k ≥ 2 drastically reduces the space of k-PHFs, e.g. for (k,α) = (16,0.8) the space lower bound is 0.027 bits per key while for (k,α) = (16,1.0) and (k,α) = (1,0.8) the lower bounds are higher by factors of ≈ 8 and ≈ 32, respectively. On the practical side, we develop a k-PHF based on PtrHash and tune it for use in static hash tables. Empirically, our implementation produces k-PHFs of size roughly 50% above the lower bound. A static hash set based on this k-PHF is consistently at least as fast as other hash sets for negative and mixed queries. On two of the three tested architectures it achieves up to 1.5× speedup for large n ≥ 30M where a 1-PHF does not fit in cache.
Cite as

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, and Stefan Walzer. Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.ESA.2026.20,
  author =	{Groot Koerkamp, Ragnar and Hermann, Stefan and Sanders, Peter and Walzer, Stefan},
  title =	{{Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.20},
  URN =		{urn:nbn:de:0030-drops-271565},
  doi =		{10.4230/LIPIcs.ESA.2026.20},
  annote =	{Keywords: Compressed Data Structures, k-Perfect Hashing, Hash Table, Space Lower Bound}
}
Artifact
Software
DOI: 10.4230/artifacts.24698
Engineering Minimal k-Perfect Hash Functions

Authors: Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, and Stefan Walzer

Abstract
Cite as

Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Stefan Walzer. Engineering Minimal k-Perfect Hash Functions (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{sourceCodekPHF,
   title = {{Engineering Minimal k-Perfect Hash Functions}}, 
   author = {Hermann, Stefan and Kirmayer, Sebastian and Lehmann, Hans-Peter and Walzer, Stefan},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:e6756f018691a80adc68d839fd3617d8f5e2d0b0;origin=https://github.com/stefanfred/engineering-k-perfect-hashing;visit=swh:1:snp:8b568d1c8fe1e13f6ef95d3b2774fc59c259d6b5;anchor=swh:1:rev:2c269037dad34b69a68b56fed38c98656f02c133}{\texttt{swh:1:dir:e6756f018691a80adc68d839fd3617d8f5e2d0b0}} (visited on 2025-10-01)},
   url = {https://github.com/stefanfred/engineering-k-perfect-hashing},
   doi = {10.4230/artifacts.24698},
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.9
MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing

Authors: Stefan Hermann

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A minimal perfect hash function (MPHF) maps a set of n keys to unique positions {1, …, n}. Representing an MPHF requires at least log₂(e)≈ 1.443 bits per key. ShockHash is a technique to construct an MPHF and requires just slightly more space. It gives each key two random candidate positions. If each key can be mapped to one of its two candidate positions such that there is exactly one key mapped to each position, then an MPHF is found. If not, ShockHash repeats the process with a new set of random candidate positions. ShockHash has to store how many repetitions were required and for each key to which of the two candidate positions it is mapped. However, when a given set of candidate positions can be used as MPHF then there is not only one but multiple ways of mapping the keys to one of their candidate positions such that the mapping results in an MPHF. This redundancy makes up for the majority of the remaining space overhead in ShockHash. In this paper, we present MorphisHash which almost completely eliminates this redundancy. Our theoretical result is that MorphisHash saves Θ(ln(n)) bits in expectation compared to ShockHash. This corresponds to a factor of 20 less space overhead in practice. Just like ShockHash, MorphisHash can be used as a building block within RecSplit to obtain MorphisHash-RS. When compared for same space consumption, MorphisHash-RS can be constructed up to 21 times faster than ShockHash-RS. The technique to accomplish this might be of a more general interest to compress data structures.
Cite as

Stefan Hermann. MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hermann:LIPIcs.ESA.2025.9,
  author =	{Hermann, Stefan},
  title =	{{MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.9},
  URN =		{urn:nbn:de:0030-drops-244779},
  doi =		{10.4230/LIPIcs.ESA.2025.9},
  annote =	{Keywords: compressed data structure, perfect hashing, random graph, pseudoforest, component}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.99
Engineering Minimal k-Perfect Hash Functions

Authors: Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Given a set S of n keys, a k-perfect hash function (kPHF) is a data structure that maps the keys to the first m integers, where each output integer can be hit by at most k input keys. When m = ⌈n/k⌉, the resulting function is called a minimal k-perfect hash function (MkPHF). Applications of kPHFs can be found in external memory data structures or to create efficient 1-perfect hash functions, which in turn have a wide range of applications from databases to bioinformatics. Several papers from the 1980s look at external memory data structures with small internal memory indexes. However, actual k-perfect hash functions are surprisingly rare, and the area has not seen a lot of research recently. At the same time, recent research in 1-perfect hashing shows that there is a lack of efficient kPHFs. In this paper, we revive the area of k-perfect hashing, presenting four new constructions. Our implementations simultaneously dominate older approaches in space consumption, construction time, and query time. We see this paper as a possible starting point of an active line of research, similar to the area of 1-perfect hashing.
Cite as

Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Peter Sanders, and Stefan Walzer. Engineering Minimal k-Perfect Hash Functions. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 99:1-99:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hermann_et_al:LIPIcs.ESA.2025.99,
  author =	{Hermann, Stefan and Kirmayer, Sebastian and Lehmann, Hans-Peter and Sanders, Peter and Walzer, Stefan},
  title =	{{Engineering Minimal k-Perfect Hash Functions}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{99:1--99:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.99},
  URN =		{urn:nbn:de:0030-drops-245685},
  doi =		{10.4230/LIPIcs.ESA.2025.99},
  annote =	{Keywords: Compressed Data Structures, Perfect Hashing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.69
PHOBIC: Perfect Hashing With Optimized Bucket Sizes and Interleaved Coding

Authors: Stefan Hermann, Hans-Peter Lehmann, Giulio Ermanno Pibiri, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A minimal perfect hash function (or MPHF) maps a set of n keys to [n] : = {1, …, n} without collisions. Such functions find widespread application e.g. in bioinformatics and databases. In this paper we revisit PTHash - a construction technique particularly designed for fast queries. PTHash distributes the input keys into small buckets and, for each bucket, it searches for a hash function seed that places its keys in the output domain without collisions. The collection of all seeds is then stored in a compressed way. Since the first buckets are easier to place, buckets are considered in non-increasing order of size. Additionally, PTHash heuristically produces an imbalanced distribution of bucket sizes by distributing 60% of the keys into 30% of the buckets. Our main contribution is to characterize, up to lower order terms, an optimal choice for the expected bucket sizes, improving construction throughput for space efficient configurations both in theory and practice. Further contributions include a new encoding scheme for seeds that works across partitions of the data structure and a GPU parallelization. Compared to PTHash, PHOBIC is 0.17 bits/key more space efficient for same query time and construction throughput. For a configuration with fast queries, our GPU implementation can construct an MPHF at 2.17 bits/key in 28 ns/key, which can be queried in 37 ns/query on the CPU.
Cite as

Stefan Hermann, Hans-Peter Lehmann, Giulio Ermanno Pibiri, Peter Sanders, and Stefan Walzer. PHOBIC: Perfect Hashing With Optimized Bucket Sizes and Interleaved Coding. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hermann_et_al:LIPIcs.ESA.2024.69,
  author =	{Hermann, Stefan and Lehmann, Hans-Peter and Pibiri, Giulio Ermanno and Sanders, Peter and Walzer, Stefan},
  title =	{{PHOBIC: Perfect Hashing With Optimized Bucket Sizes and Interleaved Coding}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{69:1--69:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.69},
  URN =		{urn:nbn:de:0030-drops-211405},
  doi =		{10.4230/LIPIcs.ESA.2024.69},
  annote =	{Keywords: Compressed Data Structures, Minimal Perfect Hashing, GPU}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact