Bitmaps and Probabilistic Structures

The structures covered so far keep what they count exactly. For a set to know its member count, every member number sits in memory; for a hash structure to know its field count, every field name sits in memory. This is unavoidable when a member has to be handed back. But not every question asks for the member back: the library’s end-of-day report asks “how many distinct readers took a loan today,” and the answer is a single number — holding hundreds of thousands of reader numbers in memory just to produce it has never been questioned as a decision.

This lesson questions that decision. Two questions are separated: cardinality estimation (“how many distinct readers”) and membership (“did this reader take a loan today”). Each can be answered with a different structure, a different byte budget, and a different degree of certainty.

Two Questions, Four Structures

The library’s loan record accumulates in the in-memory store over the course of the day. At day’s end the report asks for the distinct reader count; during the day the loan screen asks “has this reader already made a transaction today.”

Code	Assumption	Value	Rationale
DS10	registered reader	2,000,000	member number is a dense range starting from 1
DS11	daily loan event	900,000	sum across all branches
DS12	distribution of events	70% from 15% of readers	a core of frequent borrowers exists
DS13	deviation accepted for the report	2%	the end-of-day report does not need an exact count

DS10 is this lesson’s deciding assumption: because the member number is a dense range, the reader number can be used directly as a bit position. A sparse range would give the table’s second row a completely different number; the lesson measures this at the end.

Two Exact Structures

The first setup fills two exact structures with the same data. The exact set is an open-addressed hash table and the bytes it holds are the size of its buffer; the bitmap uses the reader number directly as a bit position.

// distinct-count.mjs — the day's distinct readers who took a loan: exact set vs. bitmap.
// Byte counts are read straight from the structure's own buffer, no estimate; the seed is visible.
const READERS = 2_000_000, EVENTS = 900_000, SEED = 20260731;
let d = SEED;                                         // 32-bit integer generator, no overflow
const rand = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const reader = () => rand() < 0.7                     // 70% of events, from 15% of readers
  ? 1 + Math.floor(rand() * READERS * 0.15) : 1 + Math.floor(rand() * READERS);

class ExactSet {                                      // open addressing, empty slot is 0
  constructor() { this.k = 1024; this.t = new Int32Array(this.k); this.n = 0; }
  slot(t, k, x) { let i = (Math.imul(x, 2654435761) >>> 0) & (k - 1);
    while (t[i] !== 0 && t[i] !== x + 1) i = (i + 1) & (k - 1); return i; }
  add(x) { if ((this.n + 1) * 2 > this.k) this.grow();
    const i = this.slot(this.t, this.k, x);
    if (this.t[i] === 0) { this.t[i] = x + 1; this.n += 1; } }
  contains(x) { return this.t[this.slot(this.t, this.k, x)] !== 0; }
  grow() { const y = new Int32Array(this.k * 2);
    for (const v of this.t) if (v !== 0) y[this.slot(y, this.k * 2, v - 1)] = v;
    this.t = y; this.k *= 2; }
  bytes() { return this.t.byteLength; }
}
class Bitmap {                                        // the reader number is directly the bit position
  constructor(n) { this.b = new Uint8Array(Math.ceil(n / 8)); }
  add(x) { this.b[x >> 3] |= 1 << (x & 7); }
  contains(x) { return (this.b[x >> 3] & (1 << (x & 7))) !== 0; }
  count() { let s = 0; for (let v of this.b) while (v) { s += v & 1; v >>= 1; } return s; }
  bytes() { return this.b.byteLength; }
}

const set = new ExactSet(), bitmap = new Bitmap(READERS + 1);
for (let i = 0; i < EVENTS; i += 1) { const o = reader(); set.add(o); bitmap.add(o); }
const n = set.n, fmt = (x) => x.toLocaleString("en-US");
console.log(`model: ${fmt(READERS)} registered readers, ${fmt(EVENTS)} loan events, seed ${SEED}`);
console.log(`distinct readers: ${fmt(n)} (bitmap gives the same count: ${fmt(bitmap.count())})\n`);
console.log("structure".padEnd(14) + "bytes held".padStart(14) + "per distinct".padStart(14) +
  "membership".padStart(12) + "count".padStart(12));
for (const [label, y] of [["exact set", set], ["bitmap", bitmap]])
  console.log(label.padEnd(14) + fmt(y.bytes()).padStart(14) + (y.bytes() / n).toFixed(2).padStart(14) +
    "exact".padStart(12) + "exact".padStart(12));

let mismatches = 0;                                   // do both structures give the same answer
for (let x = 1; x <= READERS; x += 7) if (set.contains(x) !== bitmap.contains(x)) mismatches += 1;
console.log(`\n${fmt(Math.ceil(READERS / 7))} membership queries where the two structures differ: ${mismatches}`);
const SPARSE = 1_000_000_000;                         // if a 9-digit member number were used
console.log(`the bitmap depends on the number range: 1..${fmt(READERS)} takes ${fmt(bitmap.bytes())} bytes, ` +
  `1..${fmt(SPARSE)} takes ${fmt(Math.ceil(SPARSE / 8))} bytes (exact set unchanged: ${fmt(set.bytes())})`);

model: 2,000,000 registered readers, 900,000 loan events, seed 20260731
distinct readers: 482,085 (bitmap gives the same count: 482,085)

structure         bytes held  per distinct  membership       count
exact set          4,194,304          8.70       exact       exact
bitmap               250,001          0.52       exact       exact

285,715 membership queries where the two structures differ: 0
the bitmap depends on the number range: 1..2,000,000 takes 250,001 bytes, 1..1,000,000,000 takes 125,000,000 bytes (exact set unchanged: 4,194,304)

These numbers are in the measurement class: the distinct reader count depends on the seed, the bytes held do not — that number is the buffer’s size and stays constant across runs with the same entry count.

The bitmap holds sixteen times less space than the exact set (250,001 against 4,194,304 bytes) and loses nothing: the distinct count is the same, and the two structures never differ across the 285,715 membership queries. The reason: the bitmap uses the reader number as an address, not as data. The exact set has to store the number, because which number occupies a slot is only known if it was written; in a bitmap, where the number sits is already the number, so nothing is left to store, and cost per entry drops from 8.70 bytes to 0.52.

What is lost shows up in the last line: the bitmap’s cost depends not on how many readers took a loan, but on how wide the number range is. If the library switched to a nine-digit member number, the same 482,085 readers would need 125,000,000 bytes instead of 250,001; the exact set’s cost would not change. A bitmap is free where the range is dense and unaffordable where it is sparse.

Giving Up Certainty

Both exact structures represent every reader individually. The next step is to abandon that representation: answering the same question with structures that leave uncertain which reader is inside.

// probabilistic-count.mjs — the same day, the same two questions, this time giving up certainty.
// Membership structure and cardinality estimate; a full list is also kept for the accuracy measure.
const READERS = 2_000_000, EVENTS = 900_000, SEED = 20260731, QUERIES = 300_000;
let d = SEED;
const rand = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const reader = () => rand() < 0.7
  ? 1 + Math.floor(rand() * READERS * 0.15) : 1 + Math.floor(rand() * READERS);
const hash = (x, seed) => { let h = Math.imul(x ^ seed, 0x85ebca6b) >>> 0;
  h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35) >>> 0; return (h ^ (h >>> 16)) >>> 0; };

const truth = new Uint8Array(READERS + 1);            // accuracy measure only, not the measured structure
for (let i = 0; i < EVENTS; i += 1) truth[reader()] = 1;
const members = [], outsiders = [];
for (let x = 1; x <= READERS; x += 1) (truth[x] ? members : outsiders).push(x);
const queries = outsiders.slice(0, QUERIES), n = members.length;
const fmt = (x) => x.toLocaleString("en-US");
console.log(`model: ${fmt(n)} distinct readers, ${fmt(QUERIES)} negative membership queries, seed ${SEED}\n`);

console.log("probabilistic membership structure (k = 3 hashes)");
console.log("bits".padEnd(10) + "bytes held".padStart(14) + "per distinct".padStart(14) +
  "false positive".padStart(15) + "expected".padStart(10) + "missed".padStart(11));
for (const p of [17, 18, 19, 20, 21, 22]) {
  const m = 1 << p, K = 3, b = new Uint8Array(m / 8);
  const positions = (x) => Array.from({ length: K }, (_, i) => hash(x, 0x1000 + i * 0x9e3779b1) % m);
  for (const x of members) for (const i of positions(x)) b[i >> 3] |= 1 << (i & 7);
  const contains = (x) => positions(x).every((i) => (b[i >> 3] & (1 << (i & 7))) !== 0);
  let fp = 0, missed = 0;
  for (const x of queries) if (contains(x)) fp += 1;
  for (const x of members) if (!contains(x)) missed += 1;
  const expected = (1 - Math.exp((-K * n) / m)) ** K;
  console.log(`2^${p}`.padEnd(10) + fmt(b.byteLength).padStart(14) +
    (b.byteLength / n).toFixed(2).padStart(14) +
    `%${((fp / QUERIES) * 100).toFixed(2)}`.padStart(15) +
    `%${(expected * 100).toFixed(2)}`.padStart(10) + `${missed}`.padStart(11));
}

console.log("\ncardinality estimate (count only; does not answer membership)");
console.log("register".padEnd(10) + "bytes held".padStart(14) + "per distinct".padStart(14) +
  "estimate".padStart(12) + "deviation".padStart(11) + "theoretical".padStart(13));
for (const p of [8, 10, 12, 14]) {
  const m = 1 << p, R = new Uint8Array(m);
  for (const x of members) { const h = hash(x, 0x9e37), i = h >>> (32 - p), w = (h << p) >>> 0;
    const r = w === 0 ? 33 - p : Math.clz32(w) + 1; if (r > R[i]) R[i] = r; }
  let z = 0, zeros = 0;
  for (const v of R) { z += 2 ** -v; if (v === 0) zeros += 1; }
  let e = (0.7213 / (1 + 1.079 / m)) * m * m / z;
  if (e <= 2.5 * m && zeros > 0) e = m * Math.log(m / zeros);   // linear counting correction
  console.log(`2^${p}`.padEnd(10) + fmt(R.byteLength).padStart(14) +
    (R.byteLength / n).toFixed(4).padStart(14) + fmt(Math.round(e)).padStart(12) +
    `%${(((e - n) / n) * 100).toFixed(2)}`.padStart(11) +
    `%${((1.04 / Math.sqrt(m)) * 100).toFixed(2)}`.padStart(13));
}

model: 482,085 distinct readers, 300,000 negative membership queries, seed 20260731

probabilistic membership structure (k = 3 hashes)
bits          bytes held  per distinct false positive  expected     missed
2^17              16,384          0.03         %99.99   %100.00          0
2^18              32,768          0.07         %98.83    %98.80          0
2^19              65,536          0.14         %82.26    %82.16          0
2^20             131,072          0.27         %42.09    %41.89          0
2^21             262,144          0.54         %12.41    %12.37          0
2^22             524,288          1.09          %2.53     %2.48          0

cardinality estimate (count only; does not answer membership)
register      bytes held  per distinct    estimate  deviation  theoretical
2^8                  256        0.0005     476,215     %-1.22        %6.50
2^10               1,024        0.0021     481,111     %-0.20        %3.25
2^12               4,096        0.0085     474,849     %-1.50        %1.63
2^14              16,384        0.0340     478,877     %-0.67        %0.81

In the upper table, the missed column reads zero on every row: the probabilistic membership structure never answers “no” for a member, because the bits of every added member are set and never cleared. The error runs in one direction only, and its name is false positive: even for a reader that was never added, the structure can find all three bits set. The measured ratio tracks the theoretical ratio row by row (12.41% against 12.37% at 2^21), so this ratio is not a surprise — it is a quantity chosen by the structure’s size.

The same pair of words also appears in software testing; there, a false alarm is a fixable defect of a test that flags correct code as broken, while the false positive rate measured here is written into the structure’s definition — lowered by adding bytes, never zeroed.

The lower table is the sharpest form of the trade-off. A register array holding 4,096 bytes counts 482,085 distinct readers with a 1.50% deviation: it holds one thousand and twenty-four times less space than the exact set, sixty-one times less than the bitmap. The size to pick is read from the last column, not from the measured deviation. The 256-byte array came out at 1.22% deviation on this run, but its theoretical margin of error is 6.50%; the first size that safely meets DS13’s 2% tolerance is the 4,096-byte one, whose theoretical margin is 1.63%. What it gives up in return is absolute: this structure cannot answer “did this reader take a loan” at any degree of certainty, because the reader itself is never represented — only how many leading zeros its hash has is kept.

Which Structure Buys What

The four structures hold 4,194,304, 250,001, 524,288, and 4,096 bytes for the same day, respectively. The ranking breaks in a surprising place: in a dense number range, the probabilistic membership structure loses to the bitmap. The structure running at 2.53% false positive wants 524,288 bytes, the exact bitmap wants 250,001. So under these conditions, giving up certainty does not save memory — it costs more.

The probabilistic membership structure wins where the range is sparse. The library’s second question is this: which book ID changed hands at least once today? A book ID is not a dense number but a thirteen-digit string, and a bitmap has no address to use. There the exact set has to hold the string itself, while the probabilistic structure uses the string’s hash and its size stays tied to the member count. The rule for choosing is not in the structure’s name — it is in the density of the key space.

There is also merging. The weekly distinct-reader question requires combining seven days of results. Bitmaps merge with a bitwise OR and stay exact; cardinality estimates merge by taking the maximum per register and the deviation does not grow; exact sets, when merged, touch every member again and the cost multiplies by the number of days. A daily 4,096-byte register array, kept for a year, holds 1,495,040 bytes — still smaller than a single day’s exact set, and it can still answer separately for any sub-range within the year.

Summary

• Cardinality and membership are two separate questions answered by separate structures: cardinality estimation gives a count but cannot answer membership at any certainty, since it does not represent the member.
• In a dense number range, a bitmap holds sixteen times less space than an exact set (250,001 against 4,194,304 bytes) and loses nothing; its cost depends on the width of the range, not the entry count, and rises to 125,000,000 bytes for a nine-digit number.
• The probabilistic membership structure’s error runs in one direction only: missed members are zero, and the false positive rate is chosen by the structure’s size — 42.09% at 131,072 bytes, 2.53% at 524,288 bytes, and the measured ratio tracks the theoretical ratio.
• Giving up certainty does not save memory in a dense range: the structure with 2.53% error wants 524,288 bytes, the exact bitmap wants 250,001. The probabilistic structure only wins once the key space is sparse.
• Cardinality estimation gives a 1.50% deviation at 4,096 bytes; it holds one thousand and twenty-four times less space than the exact set, and in return it irreversibly gives up which reader was counted.

Next Step

The structures measured in this lesson never cared about time. The bitmap answers “did they take a loan today” but does not know when; cardinality estimation produces a number at day’s end but cannot say in what order it was collected. One more question has to be read within the same day: the library’s shelving team, its overdue-notice job, and its search-index update each have to see events in the order they happened, each from its own last position. None of the structures so far provide this — a set does not keep order, a counter does not keep history, and a list does not help each reading side remember its own position separately. The next lesson takes up the structure that stores events in order and keeps every reader’s position inside the structure itself.