M.Sc. Hans-Peter Lehmann
- Raum: 220
- Tel.: +49 721 608-46781
- Fax: 49 721 608-43088
- hans-peter lehmann ∂does-not-exist.kit edu
- github.com/ByteHamster
Forschungsschwerpunkte
Ich arbeite an kompakten Datenstrukturen, insbesondere verschiedenen Varianten von Perfect Hashing. Eine perfekte Hashfunktion ist eine Funktion h: S → [m], die auf einer bestimmten Eingabemenge S keine Kollisionen hat. Dabei habe ich mich unter Anderem auf folgende Varianten konzentriert:
- Nicht-minimale perfekte Hashfunktionen (|S| > m) mit SicHash
- Parallele Minimale perfekte Hashfunktionen (|S| = m) mit GPURecSplit/SIMDRecSplit
- Perfect Hashing für Objekte variabler Größe mit PaCHash
- Monotone, minimale perfekte Hashfunktionen (Ausgabe ist lexikographisch sortiert) mit LeMonHash
Des Weiteren interessiere ich mich für Indexdatenstrukturen im Allgemeinen, sowie die Beschleunigung mittels GPUs.
| Bild | Titel | Kurzbeschreibung | Quellcode | Zugehöriges Paper |
|---|---|---|---|---|
| SicHash | Perfekte Hashfunktion basierend auf irregulärem Cuckoo-Hashing |
|||
| PaCHash | Externe perfekte Hashtabelle für Objekte variabler Größe |
|||
| GPURecSplit / SIMDRecSplit | Parallelisierung einer platzeffizienten minimalen perfekten Hashfunktion |
|||
| LeMonHash | Monotone minimal-perfekte Hashfunktion basierend auf Retrieval und dem PGM-Index |
|||
| ShockHash | Platzeffiziente perfekte Hashfunktion basierend auf dem Finden von zufälligen Pseudowäldern |
Veröffentlichungen
ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
2024. Proceedings : 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). Ed.: R. Chowdhury, 194–206, Society for Industrial and Applied Mathematics (SIAM). doi:10.1137/1.9781611977929.15
Learned Monotone Minimal Perfect Hashing
2023. 31st Annual European Symposium on Algorithms (ESA 2023), Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Ed.: I. Gørtz, 46:1–46:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI). doi:10.4230/LIPIcs.ESA.2023.46
High Performance Construction of RecSplit Based Minimal Perfect Hash Functions
2023. 31st Annual European Symposium on Algorithms (ESA 2023), Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Ed.: I. Gørtz, 19:1–19:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI). doi:10.4230/LIPIcs.ESA.2023.19
PaCHash: Packed and Compressed Hash Tables
2023. 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 162–175, Society for Industrial and Applied Mathematics (SIAM). doi:10.1137/1.9781611977561.ch14
SicHash - Small Irregular Cuckoo Tables for Perfect Hashing
2023. 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Florence, I, January 22-23,2023, 176–189, Society for Industrial and Applied Mathematics (SIAM). doi:10.1137/1.9781611977561.ch15
Weighted Random Sampling - Alias Tables on the GPU. Masterarbeit
2021. Karlsruher Institut für Technologie (KIT). doi:10.5445/IR/1000133378
| Titel | Autoren | Quelle | Datum |
|---|---|---|---|
| PHOBIC: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding | Stefan Hermann, Hans-Peter Lehmann, Giulio Ermanno Pibiri, Peter Sanders, Stefan Walzer |
April 2024 | |
| Bipartite ShockHash: Pruning ShockHash Search for Efficient Perfect Hashing | Hans-Peter Lehmann, Peter Sanders, Stefan Walzer |
Oktober 2023 | |
| ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force | Hans-Peter Lehmann, Peter Sanders, Stefan Walzer |
August 2023 | |
| Learned Monotone Minimal Perfect Hashing | Paolo Ferragina, Hans-Peter Lehmann, Peter Sanders, Giorgio Vinciguerra |
April 2023 | |
| High Performance Construction of RecSplit Based Minimal Perfect Hash Functions | Dominik Bez, Florian Kurpicz, Hans-Peter Lehmann, Peter Sanders |
December 2022 | |
| SicHash - Small Irregular Cuckoo Tables for Perfect Hashing | Hans-Peter Lehmann, Peter Sanders, Stefan Walzer |
October 2022 | |
| PaCHash: Packed and Compressed Hash Tables | Florian Kurpicz, Hans-Peter Lehmann, Peter Sanders |
May 2022 | |
| Weighted Random Sampling on GPUs | Hans-Peter Lehmann, Lorenz Hübschle-Schneider und Peter Sanders |
June 2021 |
| Titel | Tagung | Autoren |
|---|---|---|
| ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force | Symposium on Algorithm Engineering and Experiments (ALENEX'24) |
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer |
| SicHash – Small Irregular Cuckoo Tables for Perfect Hashing | Symposium on Algorithm Engineering and Experiments (ALENEX'23) |
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer |
| High Performance Construction of RecSplit Based Minimal Perfect Hash Functions | European Symposium on Algorithms (ESA'23) |
Dominik Bez, Florian Kurpicz, Hans-Peter Lehmann, Peter Sanders |
| Titel | Typ | Semester |
|---|---|---|
| Seminar: Proofs from THE BOOK | Seminar (S) | SS 2024 |
| Randomisierte Algorithmik | Vorlesung / Übung (VÜ) | WS 23/24 |
| Karopapier-Rennen | Praxis der Softwareentwicklung | WS 23/24 |
| Seminar: Proofs from THE BOOK | Seminar (S) | SS 2023 |
| Algorithmen II | Vorlesung (V) | WS 22/23 |
| Podcast-Synchronisations-Server | Praxis der Softwareentwicklung | WS 22/23 |
| Cloud Service für NP-schwere Probleme | Praxis der Softwareentwicklung | SS 2022 |
| Algorithmen II | Vorlesung (V) | WS 21/22 |
| Algorithm Engineering | Vorlesung (V) | SS 2021 |
| Titel | Forschungsthema | Betreuer |
|---|---|---|
| ShockHash Minimal Perfect Hash Functions on the GPU | Perfect Hashing | |
| Wavelet Tree Construction on GPUs | Compact Data Structures | |
| Kompakte Datenstrukturen | Compact Data Structures |
| Titel | Forschungsthema | Betreuung | Bearbeitung |
|---|---|---|---|
| Compacting Minimal Perfect Hashing using Symbiotic Random Search | Perfect Hashing | Jonatan Pascal Ziegler |
|
| Engineering k-perfect hashing | Perfect Hashing | Sebastian Kirmayer |
|
| Cuckoo-PTHash: Exploring Cuckoo Hashing in the PTHash Framework | Perfect Hashing | Benedikt Waibel |
| Titel | Forschungsthema | Betreuung | Bearbeitung |
|---|---|---|---|
| Accelerating Minimal Perfect Hash Function Construction using GPU Parallelization | Perfect Hashing | Stefan Hermann |
|
| Engineering Succinct Predecessor Data Structures | Compact Data Structures | Jan Benedikt Schwarz |
|
| Compressed Bit Vectors with Rank and Select Support | Compact Data Structures | Tobias Paweletz |
|
| Perfect Hash Function Generation on the GPU with RecSplit | Perfect Hashing | Dominik Bez |