TY - GEN
T1 - Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
AU - Li, Tianxiao
AU - Liang, Jingxun
AU - Yu, Huacheng
AU - Zhou, Renfei
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - A dictionary data structure maintains a set of at most n keys from the universe [U] under key insertions and deletions, such that given a query x ∈[U], it returns if x is in the set. Some variants also store values associated to the keys such that given a query x, the value associated to x is returned when x is in the set.This fundamental data structure problem has been studied for six decades since the introduction of hash tables in 1953. A hash table occupies O(n log U) bits of space with constant time per operation in expectation. There has been a vast literature on improving its time and space usage. The state-of-the-art dictionary by Bender, Farach-Colton, Kuszmaul, Kuszmaul and Liu [1] has space consumption close to the information-theoretic optimum, using a total of (Formula Presented) bits, while supporting all operations in O(k) time, for any parameter k ≤ log*n. The term (Formula Presented) is referred to as the wasted bits per key.In this paper, we prove a matching cell-probe lower bound: For U=n1+Θ(1), any dictionary with O(log (k) n) wasted bits per key must have expected operational time Ω(k), in the cell-probe model with word-size w=Θ(log U). Furthermore, if a dictionary stores values of Θ(log U) bits, we show that regardless of the query time, it must have Ω(k) expected update time. It is worth noting that this is the first cell-probe lower bound on the trade-off between space and update time for general data structures.
AB - A dictionary data structure maintains a set of at most n keys from the universe [U] under key insertions and deletions, such that given a query x ∈[U], it returns if x is in the set. Some variants also store values associated to the keys such that given a query x, the value associated to x is returned when x is in the set.This fundamental data structure problem has been studied for six decades since the introduction of hash tables in 1953. A hash table occupies O(n log U) bits of space with constant time per operation in expectation. There has been a vast literature on improving its time and space usage. The state-of-the-art dictionary by Bender, Farach-Colton, Kuszmaul, Kuszmaul and Liu [1] has space consumption close to the information-theoretic optimum, using a total of (Formula Presented) bits, while supporting all operations in O(k) time, for any parameter k ≤ log*n. The term (Formula Presented) is referred to as the wasted bits per key.In this paper, we prove a matching cell-probe lower bound: For U=n1+Θ(1), any dictionary with O(log (k) n) wasted bits per key must have expected operational time Ω(k), in the cell-probe model with word-size w=Θ(log U). Furthermore, if a dictionary stores values of Θ(log U) bits, we show that regardless of the query time, it must have Ω(k) expected update time. It is worth noting that this is the first cell-probe lower bound on the trade-off between space and update time for general data structures.
KW - cell-probe model
KW - dictionary
KW - lower bounds
KW - succinct data structures
UR - http://www.scopus.com/inward/record.url?scp=85182403450&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85182403450&partnerID=8YFLogxK
U2 - 10.1109/FOCS57990.2023.00112
DO - 10.1109/FOCS57990.2023.00112
M3 - Conference contribution
AN - SCOPUS:85182403450
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1842
EP - 1862
BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PB - IEEE Computer Society
T2 - 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Y2 - 6 November 2023 through 9 November 2023
ER -