Count Min Sketch

Counting how often each distinct key shows up in a high-volume stream - symbol touches, news identifiers, tick sequence IDs - with a plain key-to-count map means memory that grows with every new distinct key that ever appears, for as long as the program runs. A Count-Min Sketch answers "roughly how many times has this key been seen" from a fixed- size grid of counters, however many distinct keys pass through it, trading exact counts for a bounded, one-sided error. Add(item) increments one counter per row (depth rows total), each row using a different hash of item to pick which column to touch. EstimateCount(item) reads all depth counters back for that same item and returns the SMALLEST of them. That minimum is the whole trick: a hash collision with some other key can only ever push a counter up (never down), so any row where item's own counter got inflated by an unrelated key sharing its slot is exactly the row the minimum discards. The result is an estimate that is mathematically guaranteed to be greater than or equal to the true count, never less - the demo verifies this one-sided property directly against tracked ground-truth counts rather than just asserting it. This is a companion structure to BloomFilter.mqh elsewhere in this catalogue, sharing the same FNV-1a/djb2 double-hashing style (the Kirsch-Mitzenmacher trick, g_i = h1 + i*h2) for a consistent hashing approach across every probabilistic structure here. Where a Bloom filter answers "have I seen this at all" with one bit, a Count-Min Sketch answers "how many times" with a small counter, at the cost of a 2D grid instead of a 1D bit array. Notes and limitations - The estimate is one-sided: it can be too high (from hash collisions between distinct keys sharing a slot) but is never too low for a key that was genuinely Add()-ed. A key that was never Add()-ed can still read back a small nonzero estimate purely from collision noise - this structure answers "how many", not "was this ever seen at all" (use BloomFilter.mqh for that question instead). - There is no way to recover which specific keys are responsible for a high estimate, and no per-key removal - Clear() resets everything at once, there is no way to "un-add" a single key. - The two hash functions (FNV-1a, djb2) are chosen for speed and dispersion, matching BloomFilter.mqh, not for security - not suitable where a deliberately crafted key set could target the hashing to force worst-case collisions. - Init()/InitForAccuracy() clears any existing counts - calling either again on a live sketch discards everything counted so far.

Script · MT5 · v1.0 · Free

Tags: Grid · Volume · News Trading · Dashboards & Scanners · Gold (XAUUSD) · MT5 Script · MQL5 Source Code

MQL4 & MQL5 scripts · PolyMaria