When an approximate answer is worth an infinite speedup: Bloom filters, Count-Min sketches, and HyperLogLog

A standard hash set stores every key it has ever seen. If you want to answer the question “have I seen this user ID before?”, a hash set holds all $n$ identifiers in memory. At ten thousand items, that is a few kilobytes. At ten million items, it is hundreds of megabytes. At ten billion items in a high-velocity telemetry pipeline, the exact answer demands gigabytes or terabytes of RAM - and eventually a distributed database cluster just to answer basic membership, frequency, or cardinality queries.

Most large-scale distributed systems do not need exactness. They need bounded memory budgets.

When a database engine checks whether a key might exist on disk before issuing a slow NVMe read, an occasional false positive costs a single wasted I/O, but a false negative would corrupt query semantics. When a network router detects denial-of-service traffic or tracks heavy hitters among millions of IP packets per second, it cannot allocate a dynamic hash map entry for every new connection. When an analytics engine counts unique visitors across billions of daily log events, a 1% error margin is completely acceptable, whereas gigabytes of hash tables per query will exhaust worker memory.

This is the fundamental trade-off: trading 100% precision for exponential space reduction and deterministic O(1) update and query time.

Three probabilistic data structures form the backbone of modern distributed infrastructure:

1. Bloom Filter: answers set membership queries (“might this item be in the set, or is it definitely not?”) in a tiny bit array with zero false negatives.
2. Count-Min Sketch: answers frequency queries (“approximately how many times has this event occurred?”) in a 2D counter matrix with bounded over-estimation and zero under-estimation.
3. HyperLogLog: answers cardinality queries (“how many distinct items are in this massive stream?”) using the distribution of leading zeros in hashed bit patterns, requiring only kilobytes to count billions of items.

---

Bloom Filters: Set Membership Without False Negatives

A Bloom filter, introduced by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure designed to test whether an element is a member of a set.

How It Works

A Bloom filter consists of:

• A bit array of size $m$, initially all set to 0.
• $k$ independent, uniform hash functions $h_1, h_2, \dots, h_k$, each mapping an input element to one of the $m$ array indices: $\{0, 1, \dots, m - 1\}$.

Bit array (m = 10, k = 3):
Index:   0   1   2   3   4   5   6   7   8   9
Bits:  [ 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 ]

Insert "alice":
  h1("alice") = 1 -> set bit 1
  h2("alice") = 4 -> set bit 4
  h3("alice") = 7 -> set bit 7

Bits:  [ 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 ]

Insert "bob":
  h1("bob") = 4 -> bit 4 already 1
  h2("bob") = 5 -> set bit 5
  h3("bob") = 9 -> set bit 9

Bits:  [ 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 ]

• Insertion: To insert an item $x$, compute $h_1(x), h_2(x), \dots, h_k(x)$ and set all $k$ corresponding bits in the array to 1.
• Query: To check if an item $y$ is in the set, compute $h_1(y), h_2(y), \dots, h_k(y)$. If all $k$ bits are 1, return true (probably present). If any of the $k$ bits is 0, return false (definitely absent).

Structural Invariant: Zero False Negatives

A Bloom filter guarantees that false negatives are strictly impossible.

Why? When an element is inserted, its $k$ hash positions are unconditionally set to 1. Because standard Bloom filters only set bits and never clear them (bits are never reset to 0), any element that was genuinely inserted will always find all $k$ of its hash positions set to 1 on subsequent queries.

However, false positives are possible. Distinct items may happen to set overlapping bits. If the bits at $h_1(y), h_2(y), \dots, h_k(y)$ were previously set to 1 by a combination of other inserted elements, the filter will report that $y$ is present even if $y$ was never added.

Optimal Bit-Array Sizing and Hash Count

Given an expected number of elements $n$ and a target false-positive probability $p$, what is the optimal bit-array size $m$ and number of hash functions $k$?

The false-positive probability $p$ after inserting $n$ elements into an $m$-bit array with $k$ hash functions is approximated by:

$$p \approx \left(1 - e^{-kn/m}\right)^k$$

Minimizing this expression with respect to $k$ yields the optimal number of hash functions:

$$k = \frac{m}{n} \ln(2) \approx 0.693 \cdot \frac{m}{n}$$

Substituting this optimal $k$ back into the formula gives the optimal bit array size $m$:

$$m = -\frac{n \cdot \ln(p)}{(\ln(2))^2} \approx -\frac{n \cdot \ln(p)}{0.480453}$$

For example, to store $n = 10,000,000$ elements with a false-positive rate of $p = 0.01$ (1%):

• $m = -(10^7 \cdot \ln(0.01)) / (\ln(2))^2 \approx 95,850,584$ bits $\approx 11.42$ MB (less than 10 bits per element).
• $k = (95,850,584 / 10,000,000) \cdot \ln(2) \approx 6.64 \approx 7$ hash functions.

Storing 10 million 64-bit integers in an exact hash set would take at least 80 MB (plus hash table bucket overhead, often 150 - 200 MB). The Bloom filter accomplishes membership testing with a 1% error rate in just 11.4 MB.

Elixir Implementation

In practice, computing $k$ distinct cryptographic hashes is expensive. Instead, we use Kirsch-Mitzenmacher optimization: two independent 32-bit hash functions $h_1(x)$ and $h_2(x)$ simulate $k$ independent hash functions via:

$$g_i(x) = (h_1(x) + i \cdot h_2(x)) \pmod m \quad \text{for } i \in \{0, 1, \dots, k - 1\}$$

defmodule BloomFilter do
  @moduledoc """
  A memory-efficient Bloom filter using Kirsch-Mitzenmacher hash simulation.
  """

  defstruct [:size, :hash_count, :bits]

  @spec new(size :: pos_integer(), hash_count :: pos_integer()) :: %__MODULE__{}
  def new(size, hash_count) when size > 0 and hash_count > 0 do
    %__MODULE__{
      size: size,
      hash_count: hash_count,
      bits: MapSet.new()
    }
  end

  @spec put(%__MODULE__{}, String.t()) :: %__MODULE__{}
  def put(%__MODULE__{size: size, hash_count: k, bits: bits} = filter, item) do
    h1 = hash_djb2(item)
    h2 = hash_djb2b(item)

    new_bits =
      Enum.reduce(0..(k - 1), bits, fn i, acc ->
        idx = rem(h1 + i * h2, size)
        MapSet.put(acc, idx)
      end)

    %{filter | bits: new_bits}
  end

  @spec member?(%__MODULE__{}, String.t()) :: boolean()
  def member?(%__MODULE__{size: size, hash_count: k, bits: bits}, item) do
    h1 = hash_djb2(item)
    h2 = hash_djb2b(item)

    Enum.all?(0..(k - 1), fn i ->
      idx = rem(h1 + i * h2, size)
      MapSet.member?(bits, idx)
    end)
  end

  # djb2 hash: init = 5381, multiplier = 33
  defp hash_djb2(str) do
    str
    |> :binary.bin_to_list()
    |> Enum.reduce(5381, fn byte, acc ->
      rem(acc * 33 + byte, 0x1_0000_0000)
    end)
  end

  # djb2b hash: init = 0, multiplier = 31, add = 1
  defp hash_djb2b(str) do
    str
    |> :binary.bin_to_list()
    |> Enum.reduce(0, fn byte, acc ->
      rem(acc * 31 + byte + 1, 0x1_0000_0000)
    end)
  end
end

---

Count-Min Sketch: Frequency Estimation in Streaming Data

While a Bloom filter tracks set membership (a boolean 0 or 1), a Count-Min Sketch (developed by Graham Cormode and S. Muthu Muthukrishnan in 2005) tracks frequencies (event counts) in continuous data streams.

How It Works

A Count-Min Sketch consists of a 2D array of counters with $d$ rows (depth) and $w$ columns (width):

• Array dimensions: $d \times w$.
• $d$ independent hash functions: $h_1, h_2, \dots, h_d$, where each $h_i$ maps input keys to a column index in $\{0, 1, \dots, w - 1\}$.

Counter Table (depth d = 3, width w = 5):
Row 0 (h0): [ 0 | 0 | 0 | 0 | 0 ]
Row 1 (h1): [ 0 | 0 | 0 | 0 | 0 ]
Row 2 (h2): [ 0 | 0 | 0 | 0 | 0 ]

Update event "ip_192_168_1_1":
  h0("ip_192_168_1_1") = 1 -> increment Table[0][1]
  h1("ip_192_168_1_1") = 4 -> increment Table[1][4]
  h2("ip_192_168_1_1") = 2 -> increment Table[2][2]

Query frequency for "ip_192_168_1_1":
  Look up Table[0][1], Table[1][4], Table[2][2]
  Result = min(Table[0][1], Table[1][4], Table[2][2])

• Update: When an event key $x$ arrives with count $c$ (typically $c = 1$), compute $h_i(x)$ for each row $i \in \{0, \dots, d - 1\}$ and add $c$ to table cell Table[i][h_i(x)].
• Query (Point Query): To estimate the frequency of key $x$, calculate all row cells Table[i][h_i(x)] and return the minimum value across all $d$ rows:

$$\hat{a}_x = \min_{0 \le i < d} \text{Table}[i][h_i(x)]$$

Why the Minimum? (Zero Under-Estimation)

Each counter in row $i$ collects increments from $x$ as well as any other elements that collide at column $h_i(x)$. Therefore, every individual counter is an upper bound on the true count $a_x$:

$$\text{Table}[i][h_i(x)] \ge a_x$$

Because collisions can only increase a counter and never decrease it, taking the minimum across all independent rows gives the closest upper bound to the true value. The Count-Min Sketch never under-estimates the true frequency ($\hat{a}_x \ge a_x$).

Error Bounds: Epsilon and Delta

The dimensions $w$ (width) and $d$ (depth) determine the precision and confidence guarantees:

• Error factor $\varepsilon$ (epsilon): The estimated count $\hat{a}_x$ exceeds the true count $a_x$ by at most $\varepsilon N$, where $N = \sum a_i$ is the total number of events processed: $\hat{a}_x \le a_x + \varepsilon N$.
• Failure probability $\delta$ (delta): The probability that the error exceeds $\varepsilon N$ is at most $\delta$: $\Pr(\hat{a}_x > a_x + \varepsilon N) \le \delta$.

The formulas for sizing the sketch are:

$$w = \left\lceil \frac{e}{\varepsilon} \right\rceil \approx \left\lceil \frac{2.718}{\varepsilon} \right\rceil, \qquad d = \left\lceil \ln\left(\frac{1}{\delta}\right) \right\rceil$$

For example, to guarantee that the error is within $0.1\%$ of the total stream ($\varepsilon = 0.001$) with $99\%$ certainty ($\delta = 0.01$):

• $w = \lceil 2.718 / 0.001 \rceil = 2719$ columns.
• $d = \lceil \ln(1 / 0.01) \rceil = \lceil 4.605 \rceil = 5$ rows.
• Total counters: $2719 \times 5 = 13,595$ 32-bit integers $\approx 54.4$ KB of memory.

A 54 KB sketch can monitor a stream of 1 billion network packets and answer frequency queries with $99\%$ confidence that no count is inflated by more than $0.1\%$ of total traffic.

Conservative Update Optimization

In standard updates, every row counter is incremented. Under conservative update, when updating key $x$, we first determine the current estimate $\hat{a}_x = \min_i \text{Table}[i][h_i(x)]$. Then, for each row $i$, we only update $\text{Table}[i][h_i(x)]$ if its current value equals $\hat{a}_x$ (incrementing it to $\hat{a}_x + 1$). Counters that are already higher are left unchanged. This drastically reduces over-estimation caused by hash collisions with high-frequency items without violating the upper-bound guarantee.

Elixir Implementation

defmodule CountMinSketch do
  @moduledoc """
  A 2D Count-Min Sketch frequency estimator.
  """

  defstruct [:width, :depth, :table]

  @spec new(width :: pos_integer(), depth :: pos_integer()) :: %__MODULE__{}
  def new(width, depth) when width > 0 and depth > 0 do
    %__MODULE__{
      width: width,
      depth: depth,
      table: %{}
    }
  end

  @spec add(%__MODULE__{}, String.t(), pos_integer()) :: %__MODULE__{}
  def add(%__MODULE__{width: width, depth: depth, table: table} = sketch, item, count \\ 1) do
    h1 = hash_djb2(item)
    h2 = hash_djb2b(item)

    new_table =
      Enum.reduce(0..(depth - 1), table, fn row, acc ->
        col = rem(h1 + row * h2, width)
        Map.update(acc, {row, col}, count, &(&1 + count))
      end)

    %{sketch | table: new_table}
  end

  @spec estimate(%__MODULE__{}, String.t()) :: non_neg_integer()
  def estimate(%__MODULE__{width: width, depth: depth, table: table}, item) do
    h1 = hash_djb2(item)
    h2 = hash_djb2b(item)

    0..(depth - 1)
    |> Enum.map(fn row ->
      col = rem(h1 + row * h2, width)
      Map.get(table, {row, col}, 0)
    end)
    |> Enum.min()
  end

  defp hash_djb2(str) do
    str
    |> :binary.bin_to_list()
    |> Enum.reduce(5381, fn byte, acc ->
      rem(acc * 33 + byte, 0x1_0000_0000)
    end)
  end

  defp hash_djb2b(str) do
    str
    |> :binary.bin_to_list()
    |> Enum.reduce(0, fn byte, acc ->
      rem(acc * 31 + byte + 1, 0x1_0000_0000)
    end)
  end
end

---

HyperLogLog: Cardinality Estimation in Kilobytes

A HyperLogLog (HLL) algorithm (Flajolet, Fusy, Gandouet, and Meunier, 2007) solves the count-distinct problem: estimating the number of unique elements in a dataset using tiny, fixed memory.

The Intuition: Coin Tosses and Leading Zeros

Imagine flipping a fair coin repeatedly until it lands on heads.

• The probability of getting heads on the 1st toss (H...) is $1/2$.
• The probability of getting 1 tail before heads (TH...) is $1/4$.
• The probability of seeing $k - 1$ tails before the first head ($k$ leading flips: $000\dots1$) is $1/2^k$.

If someone tells you that their longest run of coin flips before seeing heads was $k = 10$, you can reasonably estimate that they flipped coins roughly $2^{10} = 1024$ times.

HyperLogLog applies this exact principle to hash bits:

1. Hash an incoming item into a uniform 32-bit or 64-bit binary integer.
2. If the hash function is uniform, each bit in the output is effectively an independent fair coin flip ($0$ or $1$ with probability $0.5$).
3. The position of the first 1 bit (the number of leading zeros plus one, known as the rank $\rho(x)$) gives an exponential indicator of the number of unique items seen.

If the maximum rank observed across all hashed items is $R = \max \rho(x)$, the distinct count is roughly $2^R$.

Reducing Variance: Stochastic Averaging into Registers

Relying on a single observed maximum rank has massive variance. An unlucky first item could hash to a value with 20 leading zeros, throwing the estimate off by a factor of a million.

To reduce variance, HyperLogLog partitions the stream across $m = 2^p$ registers (where $p$ is the precision parameter, typically between 4 and 16):

• Use the first $p$ bits (or $h \pmod m$) to select which of the $m$ registers to update.
• Use the remaining bits to compute the rank $\rho$ (leading zeros of the remaining hash $+ 1$).
• Update register $M[j]$ to store the maximum rank seen for bucket $j$: $M[j] \leftarrow \max(M[j], \rho)$.

Hash output (32-bit integer):
[ 0 1 0 1 | 0 0 0 0 1 1 0 1 1 0 1 0 1 ... ]
  ^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  Bucket    Remaining bits: 4 leading zeros -> Rank = 5
  (p = 4 -> Bucket = 5)

Register array M (m = 16 registers):
M[5] = max(M[5], 5)

Harmonic Mean Aggregation

How should we combine the values across all $m$ registers? An arithmetic mean is ruined by extreme outliers (a single lucky hash with many leading zeros). HyperLogLog uses the harmonic mean of $2^{-M[j]}$, which dampens outlier spikes:

$$Z = \left( \sum_{j=0}^{m-1} 2^{-M[j]} \right)^{-1}$$

The raw cardinality estimate $E$ is given by:

$$E = \alpha_m \cdot m^2 \cdot Z = \frac{\alpha_m \cdot m^2}{\sum_{j=0}^{m-1} 2^{-M[j]}}$$

where $\alpha_m$ is a bias-correction constant:

• For $m = 16$ ($p = 4$): $\alpha_{16} \approx 0.673$
• For $m = 32$ ($p = 5$): $\alpha_{32} \approx 0.697$
• For $m = 64$ ($p = 6$): $\alpha_{64} \approx 0.709$
• For $m \ge 128$: $\alpha_m = \frac{0.7213}{1 + 1.079 / m} \approx 0.7213$

Small Range Correction (Linear Counting)

When the total number of unique elements is small relative to $m$, many registers remain empty ($M[j] = 0$). In this regime, raw HyperLogLog exhibits non-linear bias.

If the number of empty registers $V = |\{j : M[j] = 0\}|$ is greater than 0, HyperLogLog switches to Linear Counting:

$$E^* = m \cdot \ln\left(\frac{m}{V}\right)$$

Standard Error

The standard error of HyperLogLog with $m$ registers is:

$$\text{SE} = \frac{1.04}{\sqrt{m}} = \frac{1.04}{\sqrt{2^p}}$$

• With $p = 10$ ($m = 1024$ registers, each 6 bits): $\text{SE} \approx 1.04 / 32 \approx 3.25\%$ using 768 bytes.
• With $p = 14$ ($m = 16,384$ registers, each 6 bits): $\text{SE} \approx 1.04 / 128 \approx 0.81\%$ using 12 KB.

HyperLogLog can count hundreds of billions of unique items with under $1\%$ error using just 12 KB of RAM. Redis’s PFADD and PFCOUNT commands implement this exact algorithm.

Elixir Implementation

defmodule HyperLogLog do
  @moduledoc """
  HyperLogLog cardinality estimator using 32-bit FNV-1a hashing.
  """
  import Bitwise

  defstruct [:precision, :m, :registers]

  @spec new(precision :: pos_integer()) :: %__MODULE__{}
  def new(precision) when precision >= 4 and precision <= 16 do
    m = Integer.pow(2, precision)
    %__MODULE__{
      precision: precision,
      m: m,
      registers: %{}
    }
  end

  @spec add(%__MODULE__{}, String.t()) :: %__MODULE__{}
  def add(%__MODULE__{m: m, registers: reg} = hll, value) do
    h = hash_fnv1a_32(value)
    bucket = rem(h, m)
    rank = count_leading_zeros_32(h) + 1

    new_registers = Map.update(reg, bucket, rank, &max(&1, rank))
    %{hll | registers: new_registers}
  end

  @spec count(%__MODULE__{}) :: non_neg_integer()
  def count(%__MODULE__{m: m, registers: reg}) do
    empty_registers = m - map_size(reg)

    if empty_registers > 0 do
      # Linear counting for small range
      round(m * :math.log(m / empty_registers))
    else
      # Harmonic mean estimation
      sum =
        Enum.reduce(0..(m - 1), 0.0, fn i, acc ->
          rank = Map.get(reg, i, 0)
          acc + :math.pow(2, -rank)
        end)

      alpha = alpha_m(m)
      raw_estimate = (alpha * m * m) / sum
      round(raw_estimate)
    end
  end

  # 32-bit FNV-1a hash
  defp hash_fnv1a_32(str) do
    str
    |> :binary.bin_to_list()
    |> Enum.reduce(2166136261, fn byte, acc ->
      acc
      |> bxor(byte)
      |> Kernel.*(16777619)
      |> rem(0x1_0000_0000)
    end)
  end

  # Count leading zeros in 32-bit integer representation
  defp count_leading_zeros_32(0), do: 32

  defp count_leading_zeros_32(n) do
    count_leading_zeros(n, 31, 0)
  end

  defp count_leading_zeros(_n, bit, count) when bit < 0, do: count

  defp count_leading_zeros(n, bit, count) do
    if (n &&& (1 <<< bit)) == 0 do
      count_leading_zeros(n, bit - 1, count + 1)
    else
      count
    end
  end

  defp alpha_m(16), do: 0.673
  defp alpha_m(32), do: 0.697
  defp alpha_m(64), do: 0.709
  defp alpha_m(m), do: 0.7213 / (1.0 + 1.079 / m)
end

---

Comparison of Probabilistic Structures

Structure	Answers Question	Error Guarantee	Space Complexity	Typical Production Use Case
Bloom Filter	Is item $x$ in set $S$?	False positives bounded by $p$; zero false negatives	$O(n \ln(1/p))$ bits $\approx 10$ bits/item	LSM-tree disk read bypass (RocksDB, Cassandra), web crawler URL deduplication
Count-Min Sketch	How many times did $x$ occur?	$\hat{a}_x \le a_x + \varepsilon N$ with prob $1 - \delta$; zero under-estimation	$O(\frac{1}{\varepsilon} \ln \frac{1}{\delta})$ counters (independent of stream length)	Network traffic analysis, top-k heavy hitters, DDoS detection, cache admission policies (TinyLFU)
HyperLogLog	How many distinct items exist?	Relative standard error $\approx 1.04 / \sqrt{m}$	$O(\log \log N)$ per register $\approx 12$ KB total	Daily unique active user (DAU) analytics, distinct search query counts (Redis PFCOUNT)

---

Where to go next

• Bloom Filter - implement the bit-array membership test with Kirsch-Mitzenmacher hashing.
• Count-Min Sketch - implement 2D frequency estimation with minimum-bound reduction.
• HyperLogLog - implement cardinality estimation with leading zero counts and small-range linear correction.
• Hash tables: the O(1) that has fine print - collisions, load factors, and why hash tables need memory.
• Amortized: the expensive step you almost never take - how dynamic arrays and hash table resizing amortize costs.
• Rate limiting: the window that expires before it floods - streaming telemetry windows and rate budgets.
• What O(n) actually promises - time and space complexity boundaries at scale.