Abstract
Dictionaries have been one of the central questions in data structures. A dictionary data structure maintains a set of key-value pairs under insertions and deletions such that given a query key, the data structure efficiently returns its value. The state-of-the-art dictionaries [4] store n key-value pairs with only O(n log(k) n) bits of redundancy, and support all operations in O(k) time, for k ≤ log∗ n. It was recently shown to be optimal [16]. In this paper, we study the regime where the number of redundant bits is R = o(n), and show that when R is at least n/poly log n, all operations can be supported in O(log∗ n + log(n/R)) time, matching the lower bound in this regime [16]. We present two data structures based on which range R is in. The data structure for R < n/log0.1 n utilizes a generalization of adapters studied in [5, 15]. The data structure for R ≥ n/log0.1 n is based on recursively hashing into buckets with logarithmic sizes.
Original language | English (US) |
---|---|
Pages | 171-207 |
Number of pages | 37 |
DOIs | |
State | Published - 2024 |
Externally published | Yes |
Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: Jan 7 2024 → Jan 10 2024 |
Conference
Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|
Country/Territory | United States |
City | Alexandria |
Period | 1/7/24 → 1/10/24 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics