--- title: 'Bitmaps and Probabilistic Structures' source: 'https://academia.sh/en/courses/in-memory-stores/bitmaps-and-probabilistic-structures' course: 'In-Memory Stores and Caching Systems' language: en updated: '2026-08-23T07:00:43+00:00' license: 'CC BY-SA 4.0' --- # Bitmaps and Probabilistic Structures The cost of keeping a member list when the number alone would do: the same distinct-reader question solved with an exact set, a bitmap, a probabilistic membership structure, and a cardinality estimate, the bytes each of the four structures holds read from its own buffer, the false positive rate measured, and how many bytes giving up certainty buys counted out. 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. ```js // 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. ```js // 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.