1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$
    – ABu
    Commented Jan 5 at 11:04
  • $\begingroup$ @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. $\endgroup$
    – ABu
    Commented Jan 5 at 15:53
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jan 5 at 20:58
  • $\begingroup$ @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 $\endgroup$
    – ABu
    Commented Jan 5 at 23:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.