Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.10655 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in $[U]$ and values in $[σ]$, such that given a query $x\in [U]$, it quickly returns if $x$ is one of the input keys, and if so, also returns its associated value. The textbook solution to dictionaries is hash tables. On the other hand, the (information-theoretical) optimal space to encode such a set of key-value pairs is only $\text{OPT} := \log\binom{U}{n}+n\log σ$. We construct a dictionary that uses $\text{OPT} + n^ε$ bits of space, and answers queries in constant time in worst case. Previously, constant-time dictionaries are only known with $\text{OPT} + n/\text{poly}\log n$ space [Pǎtraşcu 2008], or with $\text{OPT}+n^ε$ space but expected constant query time [Yu 2020]. We emphasize that most of the extra $n^ε$ bits are used to store a lookup table that does not depend on the input, and random bits for hash functions. The "main" data structure only occupies $\text{OPT}+\text{poly}\log n$ bits.