Dynamic Dictionary with Subconstant Wasted Bits per Key

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations

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 languageEnglish (US)
Pages171-207
Number of pages37
DOIs
StatePublished - 2024
Externally publishedYes
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024

Conference

Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States
CityAlexandria
Period1/7/241/10/24

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Dynamic Dictionary with Subconstant Wasted Bits per Key'. Together they form a unique fingerprint.

Cite this