TY - GEN
T1 - Optimal Static Dictionary with Worst-Case Constant Query Time
AU - Hu, Yang
AU - Liang, Jingxun
AU - Yu, Huacheng
AU - Zhang, Junkai
AU - Zhou, Renfei
N1 - Publisher Copyright:
© 2025 Owner/Author.
PY - 2025/6/15
Y1 - 2025/6/15
N2 - 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 ϵ [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 OPT := log(Un) + n logσ. We construct a dictionary that uses OPT + nϵ bits of space, and answers queries in constant time in worst case. Previously, constant-time dictionaries are only known with OPT + n / poly logn space, or with OPT + nϵ space but expected constant query time. 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 OPT + poly logn bits.
AB - 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 ϵ [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 OPT := log(Un) + n logσ. We construct a dictionary that uses OPT + nϵ bits of space, and answers queries in constant time in worst case. Previously, constant-time dictionaries are only known with OPT + n / poly logn space, or with OPT + nϵ space but expected constant query time. 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 OPT + poly logn bits.
KW - Data Structures
KW - Dictionaries
KW - Succinct Data Structures
UR - https://www.scopus.com/pages/publications/105009839889
UR - https://www.scopus.com/pages/publications/105009839889#tab=citedBy
U2 - 10.1145/3717823.3718278
DO - 10.1145/3717823.3718278
M3 - Conference contribution
AN - SCOPUS:105009839889
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 278
EP - 289
BT - STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing
A2 - Koucky, Michal
A2 - Bansal, Nikhil
PB - Association for Computing Machinery
T2 - 57th Annual ACM Symposium on Theory of Computing, STOC 2025
Y2 - 23 June 2025 through 27 June 2025
ER -