Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Pages1842-1862
Number of pages21
ISBN (Electronic)9798350318944
DOIs
StatePublished - 2023
Externally publishedYes
Event64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States
Duration: Nov 6 2023Nov 9 2023

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz
Period11/6/2311/9/23

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • cell-probe model
  • dictionary
  • lower bounds
  • succinct data structures

Fingerprint

Dive into the research topics of 'Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries'. Together they form a unique fingerprint.

Cite this