# Naming for (memory near optimal) datastructres

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).

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