succinct-data-structure · shipping · also Succinct data structures

Succinct data structure

A succinct data structure supports specified operations using the information-theoretic minimum space for its object class plus a lower-order redundancy.

Bound: If U is the class of possible objects, the worst-case distinguishing budget is ceil(log2(|U|)) bits. Succinct space adds o(log2(|U|)) redundancy; compact space only requires the same asymptotic order. The object class must be stated. [1]

Bitvectors: For all length-n binary strings, |U| = 2^n and the succinct target is n + o(n) bits. Fixing the number of ones to k changes the class size to choose(n,k). A bound with o(n) redundancy need not be lower-order relative to log2(choose(n,k)) for very sparse inputs. [1] [2]

Queries: Rank/select support enables navigation without expanding an entire bitmap. Succinctness describes space, not a universal query-time guarantee; operation costs and the computational model are separate parts of the contract. [1] [3]

Engineering: Lower-order does not mean negligible at deployed sizes. Count samples, pointers, lookup tables and boundary handling alongside encoded data. A theorem about a data structure is not a measured serialized-file size or a promise that every input shrinks. [3]

Relations

related
RRR bitvector, Rank/select

Citations

  1. Bille, Gortz and Tarnow: Succinct Data Structures for Segments, CPM 2025, section 2; DOI 10.4230/LIPIcs.CPM.2025.27 (accessed 2026-11-17)
  2. Raman, Raman and Rao: Succinct Indexable Dictionaries, arXiv:0705.0552v1 (2007), sections 1.1.3 and 4.1 (accessed 2026-11-17)
  3. Navarro and Providel: Fast, Small, Simple Rank/Select on Bitmaps, SEA 2012, sections 1 and 3 (accessed 2026-11-17)
Sources & caveats
  • Primary-source synthesis of space accounting. No new compression algorithm, native benchmark or measured storage saving is claimed.
  • The formula is asymptotic over a growing object class; degenerate singleton classes and fixed tiny inputs are not runtime size guarantees.

JSON: /data/terms/succinct-data-structure.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Succinct data structure. Hesela. 2026-11-17. https://hesela.dev/terms/succinct-data-structure/