# Succint data structure for storing n numbers using a mask-based partition

I've a set $$N$$ of $$n$$ distinct numbers of $$d$$-bits each; call them words ($$1\leq n\leq 2^d$$, with $$d\geq 1$$). I want to store $$N$$ using as least space as possible, by partitioning $$N$$ and factoring out the common bits within each group. The problem is finding the optimal partition, taking into account group payloads. For example, given the following set of 6-bit words (in binary):

000010 000110 010110 101000 110000 110100 111100

This requires 42 bits of storage, but that can be reduced by partitioning this set into two groups:

000010 000110 010110        => 0x0x10, 3: 00 01 11
101000 110000 110100 111100 => 1xxx00, 4: 010 100 101 111


The 0x0x10 and 1xxx00 are informal masks (the physical representation is explained later), which tells the positions of the free-bits (the x's), and the positions and values of the fixed-bits. It's followed by the size of the group, and the list of sketches (named taken from fusion trees): words with the fixed-bits removed.

For the $$i$$-th group, $$x_i$$ is the amount of free-bits (x's) of the mask and $$n_i$$ the amount of sketches ($$n_i\leq 2^{x_i}$$). In our case: $$(x_1, n_1)=(2, 3)$$ and $$(x_2, n_2)=(3, 4)$$. An extra optimization is possible: if $$n_i$$ is more than half of the $$2^{x_i}$$ possible sketches, you only need to store the missing ones. The original representation can then be turned into:

000010 000110 010110        => 0x0x10, 3: 10
101000 110000 110100 111100 => 1xxx00, 4: 010 100 101 111


Lastly, the informal mask and $$n_i$$ can be stored using two words:

• Word 1: the formal mask $$m_i$$ (a kind of one-hot vector), which contains a 1 in the positions where the informal mask have an x, and 0 otherwise.
• Word 2: the fixed-values, requiring $$d-x_i$$ bits, followed by $$n_i$$, requiring $$x_i$$ bits (because $$n_i\leq 2^{x_i}$$).

All together:

000010 000110 010110        => 0x0x10, 3: 10
101000 110000 110100 111100 => 1xxx00, 4: 010 100 101 111

stored as a contiguous bitarray gives (blanks and comments added for clarity):

010100 001011 10              # b0010 in the 2nd word are the fixed-bits, and b011 = 3
011100 100100 010 100 101 111 # b100 the fixed-values, and b100 = 4.


The original set required 7*6=42 bits, and this 4*6+2+3*4=36; 14.29% shorter.

Given $$n_i\geq 2$$ words, for these to be worth compressing into a single group with $$x_i\in[1, d]$$:

• If $$n_i\leq 2^{x_i-1}$$, then $$2d+x_i n_i\leq dn_i\Longrightarrow x_i\leq d\frac{n_i-2}{n_i}$$ and $$x_i\in[3, d-1]$$ and $$d\geq 4$$ and $$n_i\geq 3$$.
• If $$n_i\geq 2^{x_i-1}+1$$, then $$2d+x_i (2^{x_i}-n_i)\leq dn_i$$, which is always satisfied.

The problem is that I'm not able to figure out the algorithm of how to find the optimal partition using those facts and how to build a worst-case for the strategy (so that I'm able to calculate a upper bound of the storage savings respect to $$d\times n$$). It smells like some variant of a bin-packaging problem.

• @D.W. It's counted in the second word of each bucket. The two words payload per bucket contains all the required meta info of the bucket.
– ABu
Commented Jan 5 at 11:04
• @D.W. I mean, I store $n_i$, which is the amount of numbers that belongs to the bucket, but not necessarily the amount of sketches that are physically stored. As I said, if $n_i$ is more than half of the possible number of sketches ($n_i\geq 2^{x_i-1}+1$), I store the missing ones (I store $2^{x_i} - n_i$ sketches). How to know in which storage mode you are? Well, you know $x_i$ (the popcount of the actual mask; the first word), and $n_i$ (the last $x_i$ bits of the second word), so you only have to check if $x_i\leq 2^{x_i-1}$ to know.
– ABu
Commented Jan 5 at 15:53
• Sorry for misunderstanding your idea. Thank you for explaining and setting me straight. Nitpick: Defining the formal mask as the xor of the words in the bucket doesn't seem quite right to me; that only works when there are an odd number of values in the bucket. I think it's a one-hot vector, with 1's in the positions where x's appear.
– D.W.
Commented Jan 5 at 20:58
• @D.W. oh damn you are right, it can't be a straight xor. And yes, I didn't know the concept of a one-hot vector, but that's what I meant, a mask. I will fix the question right away. thank you
– ABu
Commented Jan 5 at 23:14