Reproduce “Compressing Dynamic Fully Indexable Dictionaries in Word-RAM” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Gabriel Marques Domingues

A deterministic Word-RAM construction combines compact small-set rank indices with a reduction and memory-management framework to support dynamic fully indexable dictionaries (FIDs). It achieves redundancy of O(nw^ε/ε) with worst-case rank, select, and update times, and also gives a trade-off using lg binom(u,n) + O(n log w) bits with slower operations.

Key insights

  • A small-set rank index can serve as the core of a larger dynamic FID when paired with a general reduction that adds O(log_w n) time and controlled redundancy.
  • The construction treats memory allocation as part of the data-structure design: dynamically changing components must be laid out so their address space remains within the claimed bound.
  • The redundancy-time trade-off is adjustable: smaller ε reduces redundancy but increases operation time, while a separate index design yields near information-theoretic space with slower operations.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.