Assume that we wish to solve some problem that has a information theoretic memory lower bound of $\mathcal B$ bits.

In computer science, there are a few classes for data structures which are close to the memory lower bound of the problem that they solve:

  • Compact data structure is one that uses $O(\mathcal B)$ bits (i.e., it is asymptotically optimal).
  • Succinct data structure uses $\mathcal B(1+o(1))$ bits (e.g. $\mathcal B + 7{\mathcal B \over \log \mathcal B}$).
  • Implicit data structure uses $\mathcal B+O(1)$ bits (e.g., $\mathcal B + 38$).

I couldn't find a name for the following classes, and wondering if such naming exist:

1. Data structures that use $\mathcal B + \text{polylog}(\mathcal B)$ bits.

2. Data structures that for every fixed $\epsilon>0$ uses less than $\mathcal B (1+\epsilon)$ bits (the data structure takes $\epsilon$ as a parameter that may influence its runtime).

  • $\begingroup$ If the truth is that these things have no names, what would a good answer to this on StackExchange look like? $\endgroup$ – jbapple Jan 18 '17 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.