2026-07-22T04:43:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21140 2024-09-23T09:13:17Z ddc:004 open_access

PHOBIC: Perfect Hashing With Optimized Bucket Sizes and Interleaved Coding Hermann, Stefan Lehmann, Hans-Peter Pibiri, Giulio Ermanno Sanders, Peter Walzer, Stefan Compressed Data Structures Minimal Perfect Hashing GPU 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Hermann and Hans-Peter Lehmann and Giulio Ermanno Pibiri and Peter Sanders and Stefan Walzer 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.69 urn:nbn:de:0030-drops-211405 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.69 eng https://creativecommons.org/licenses/by/4.0/legalcode