Locally Uniform Hashing
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Indsendt manuskript, 526 KB, PDF-dokument
Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical results that often assume access to (unrealistic) uniform/fully-random hash functions. In this paper, we are concerned with designing hash functions that are practical and come with strong theoretical guarantees on their performance.To this end, we present tornado tabulation hashing, which is simple, fast, and exhibits a certain full, local randomness property that provably makes diverse algorithms perform almost as if (abstract) fully-random hashing was used. For example, this includes classic linear probing, the widely used HyperLogLog algorithm of Flajolet, Fusy, Gandouet, Meunier [AOFA'97] for counting distinct elements, and the one-permutation hashing of Li, Owen, and Zhang [NIPS'12] for large-scale machine learning. We also provide a very efficient solution for the classical problem of obtaining fully-random hashing on a fixed (but unknown to the hash function) set of n keys using O(n) space. As a consequence, we get more efficient implementations of the splitting trick of Dietzfelbinger and Rink [ICALP'09] and the succinct space uniform hashing of Pagh and Pagh [SICOMP'08].Tornado tabulation hashing is based on a simple method to systematically break dependencies in tabulation-based hashing techniques.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 |
Forlag | IEEE Computer Society Press |
Publikationsdato | 2023 |
Sider | 1440-1470 |
ISBN (Elektronisk) | 9798350318944 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, USA Varighed: 6 nov. 2023 → 9 nov. 2023 |
Konference
Konference | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 |
---|---|
Land | USA |
By | Santa Cruz |
Periode | 06/11/2023 → 09/11/2023 |
Sponsor | IEEE, IEEE Computer Society, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, NSF |
Bibliografisk note
Funding Information:
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen and Mikkel Thorup are part of Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Lorenzo Beretta receives funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No. 801199.
Funding Information:
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bak Tejs Houen and Mikkel Thorup are part of Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Lorenzo Beretta receives funding from the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No. 801199.
Publisher Copyright:
© 2023 IEEE.
ID: 384069326