Dictionary encoding: when it pays

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• k = 1,000 → about 1.27 MB against 20 MB (≈ 15×)
• k = 500,000 → about 12.4 MB (1.6×)
• 10 million 20-byte strings, 1,000 distinct → ≈ 16×

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Encoding, Serialization & Compression

  What do we turn our values into when we turn them into bytes, and what does that choice cost?

  $$N\times \lceil {\log }_{2}k\rceil \text{bits}+k\times \text{average value size}$$

  Read it in place →