Count-min sketch and top-k

The problem: top links in the last hour

Snip's home page shows "trending links": the most-clicked links in the last hour. Its abuse team wants "which referrers are sending the most clicks right now" to spot bot farms. Within an hour, millions of different codes and referrers appear, most clicked once or twice. An exact count per item needs a counter for every item, and a sorted list of all of them, on every server, every hour.

What's actually wanted is narrower: the few items with very high counts, the heavy hitters, and roughly how many each has.

Count-min sketch

A count-min sketch is a small grid of counters: d rows of w counters each, with a different hash function per row.

• Add an item: in each row, hash it to one counter and increment it.
• Estimate an item: in each row, look at its counter, and take the minimum.

Every counter for an item includes all of that item's own increments, plus increments from any other items that collided with it. So the estimate can be too high but never too low, and taking the minimum across rows picks the row with the fewest collisions.

The error is controlled by the dimensions. With width w, the over-count is at most about (e / w) × the total number of events, with a probability that improves with each extra row. Redis's version takes the error and probability directly and sizes the grid: the error sets the width, and the probability sets the number of rows.

export class CountMinSketch {
  private rows: Uint32Array[];

  constructor(readonly width = 2048, readonly depth = 4) {
    this.rows = Array.from({ length: depth }, () => new Uint32Array(width));
  }

  add(item: string, n = 1) {
    for (let d = 0; d < this.depth; d++) this.rows[d][hash32(item, d + 1) % this.width] += n;
  }

  /** Never below the true count; above it by collisions. Take the smallest row's counter. */
  estimate(item: string) {
    let min = Infinity;
    for (let d = 0; d < this.depth; d++) min = Math.min(min, this.rows[d][hash32(item, d + 1) % this.width]);
    return min;
  }
}

Top-k on top of it

The sketch estimates any item, but can't list them: it doesn't remember which items it saw. For "top 10", keep a small list of candidates alongside it. After each event, estimate the item; if it's already a candidate, update it; if the list has room, add it; otherwise, if its estimate beats the smallest candidate, replace that one.

export class TopK {
  private sketch = new CountMinSketch();
  private candidates = new Map<string, number>(); // the current top k, with estimates

  constructor(readonly k = 10) {}

  add(item: string) {
    this.sketch.add(item);
    const est = this.sketch.estimate(item);
    if (this.candidates.has(item) || this.candidates.size < this.k) {
      this.candidates.set(item, est);
      return;
    }
    let minItem = "";
    let minVal = Infinity;
    for (const [c, v] of this.candidates) if (v < minVal) [minItem, minVal] = [c, v];
    if (est > minVal) {
      this.candidates.delete(minItem);
      this.candidates.set(item, est);
    }
  }

  top() {
    return [...this.candidates].sort((a, b) => b[1] - a[1]);
  }
}

Tested

200,000 simulated clicks over 50,000 codes with a power-law popularity, like real links (28,817 different codes actually appeared):

Over-counts are small next to heavy hitters' real counts, which is exactly where accuracy matters: being off by 26 on a link with 17,000 clicks doesn't change the ranking, while the long tail of one-click codes, where the relative error is large, never makes the top 10.

Windows and merging

Count-min sketches merge by adding counters (with the same dimensions and hashes), so each server keeps its own and a central job sums them. For "the last hour", keep one sketch per minute and sum the last 60, or decay old counts. Redis's Top-K takes the decaying approach: it's based on the HeavyKeeper algorithm, which decays counts exponentially so items that stopped being popular fade out.

Recap

Interview questions