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 -