Dynamic 'Succincter'

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

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

1 Scopus citations

Abstract

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
Pages1715-1733
Number of pages19
ISBN (Electronic)9798350318944
DOIs
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

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

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

Fingerprint

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

Cite this