Count-Min Sketch

The Count-Min Sketch achieves O(ε⁻¹ log(1/δ)) space complexity, where ε controls the error bound and δ controls the confidence probability. Unlike exact counting methods that require space proportional to the number of distinct items, this structure uses a fixed-size two-dimensional array of counters (width × depth) that remains constant regardless of stream volume.

• A sketch tracking 10⁹ distinct events might occupy only kilobytes of memory
• Width determines precision: wider arrays reduce collision probability
• Depth determines confidence: more hash functions tighten probabilistic guarantees
• Memory footprint is configured at initialization and never grows

The Count-Min Sketch provides a conservative over-estimation guarantee: the estimated frequency is always greater than or equal to the true frequency. This one-sided error property is critical for fraud velocity checks, where false negatives (under-counting) could allow attacks to pass undetected.

• Estimate ≥ True Count: never underestimates frequency
• Error bound: Pr[estimate > true + εN] ≤ δ, where N is total stream count
• Over-counting is bounded and tunable via width and depth parameters
• Ideal for threshold-based alerting: if estimate < threshold, true count is definitely below threshold

Count-Min Sketch excels at identifying heavy hitters—items whose frequency exceeds a specified fraction of the total stream. In fraud detection, this translates to detecting cards, IPs, or accounts exhibiting anomalous velocity within sliding time windows.

• Maintains a heap of top-k candidates alongside the sketch
• Query complexity is O(1) per item: constant-time lookups
• Enables real-time detection of: card testing attacks, credential stuffing bursts, rapid account creation
• Complements exact counting by filtering the stream to only track high-frequency candidates precisely

Multiple Count-Min Sketches with identical dimensions and hash functions can be merged via element-wise addition of their counter arrays. This linear composability enables distributed velocity tracking across partitioned stream processors without coordination overhead.

• Each shard maintains a local sketch for its partition of transaction traffic
• Global velocity is computed by summing sketches at query time
• No need for shared state or distributed locks during ingestion
• Enables hierarchical aggregation: edge sketches → regional sketches → global sketch
• Critical for fraud systems spanning multiple data centers or processing regions

The sketch employs d pairwise-independent hash functions, each mapping input items uniformly to one of w buckets in its corresponding row. The median-of-minima estimation strategy—taking the minimum across all rows—provides the probabilistic guarantee that collisions from one hash function are mitigated by others.

• Each row uses a distinct hash seed to ensure independence
• Common implementations use MurmurHash3 or xxHash for speed
• The minimum operation across rows provides the one-sided error property
• Hash collisions cause over-counting, but the depth parameter controls collision probability
• Cryptographic hash functions are unnecessary: uniform distribution is the only requirement

The Count-Min Sketch supports only increment operations—counters monotonically increase. There is no native delete or decrement operation, making it suitable for append-only stream processing where only frequency accumulation matters. For sliding window velocity checks, implementations typically maintain multiple time-bucketed sketches and rotate them.

• Insert-only: counters are monotonically non-decreasing
• Deletion support requires a Counting Bloom Filter variant or separate decay mechanism
• Sliding windows implemented via: tumbling sketch arrays, exponential decay counters, or time-stamped heavy-hitter caches
• Typical fraud pattern: maintain 5-minute, 1-hour, and 24-hour sketches for multi-resolution velocity checks

A continuous computation technique that calculates metrics over a dynamically updating, overlapping time interval. Unlike Count-Min Sketch's approximate counting, sliding windows provide exact counts but at higher memory cost:

• Tumbling windows: Fixed, non-overlapping intervals
• Hopping windows: Fixed-size, overlapping intervals
• Sliding windows: Continuous, event-triggered intervals Count-Min Sketch is often preferred when memory is constrained and approximate heavy-hitter detection suffices.

A fraud detection technique that monitors the frequency of specific attributes—such as card numbers, IP addresses, or device fingerprints—over short time windows to identify anomalous bursts of activity. Count-Min Sketch is the ideal underlying data structure for velocity checks because:

• It handles high-cardinality keys (millions of distinct cards)
• It operates in constant memory regardless of stream volume
• It provides sub-second estimates for real-time authorization flows
• It gracefully handles the heavy-tailed distribution of transaction keys

The problem of identifying items that appear with frequency above a threshold in a data stream. Count-Min Sketch solves the approximate heavy hitter problem efficiently:

• Point query: Estimate frequency of a specific item
• Heavy hitters: Find all items exceeding φN frequency
• Top-k: Identify the k most frequent items In fraud detection, heavy hitters might reveal compromised cards being tested rapidly or IP addresses launching credential stuffing attacks. The sketch's one-sided error guarantees frequency is never underestimated.