Dynamic 'Succincter'

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

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

1 Scopus citations


Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work 'succincter' by Ptraşcu [1] showed that any aB-tree can be stored using only two bits of redundancy, while supporting queries to the tree in time proportional to its depth. It has been a versatile building block for constructing succinct data structures, including rank/select data structures, dictionaries, locally decodable arithmetic coding, storing balanced parenthesis, etc.In this paper, we show how to 'dynamize' an aB-tree. Our main result is the design of dynamic aB-trees (daB-trees) with branching factor two using only three bits of redundancy (with the help of lookup tables that are of negligible size in applications), while supporting updates and queries in time polynomial in its depth. As an application, we present a dynamic rank/select data structure for n-bit arrays, also known as a dynamic fully indexable dictionary (FID) [2]. It supports updates and queries in O(log n/log log n) time, and when the array has m ones, the data structure occupies (Formula Presented). Note that the update and query times are optimal even without space constraints due to a lower bound by Fredman and Saks [3]. Prior to our work, no dynamic FID with near-optimal update and query times and redundancy o(n/log n) was known. We further show that a dynamic sequence supporting insertions, deletions and rank/select queries can be maintained in (optimal) O(log n/log log n) time and with O(n · poly log log n/log 2 n) bits of redundancy.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Number of pages19
ISBN (Electronic)9798350318944
StatePublished - 2023
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


Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • B-trees
  • dynamic data structures
  • succinct data structures


Dive into the research topics of 'Dynamic 'Succincter''. Together they form a unique fingerprint.

Cite this