Streaming Top K Heavy Hitters
An exact frequency table needs one counter per distinct item ever seen, which is unbounded memory over anything that counts tags, symbols or comment strings across a long-running session. The Space-Saving algorithm (Metwally, Agrawal and Abbadi, 2005) caps memory at exactly K counters no matter how many distinct items the stream contains. The mechanism is the whole algorithm: when a new item arrives and the table already has K entries, the entry with the SMALLEST count is evicted, and the new item takes over that slot starting from (evicted count + 1) rather than 1. The evicted count is recorded as that slot's error bound. This is what makes the guarantee work - every tracked item's true frequency is provably between (count - error) and count, and an item whose (count - error) is still positive above zero is a genuine heavy hitter, not noise that survived a lucky sequence of evictions. Most home-grown "top N" trackers either keep an unbounded hash map (the memory problem this algorithm exists to avoid) or a naive fixed-size table that resets a new arrival's counter to 1 on eviction, which throws away exactly the information needed to bound the error and makes the reported counts meaningless for anything but casual eyeballing. The header is self-contained. No dependencies, no DLLs. Notes and limitations - Offer() and eviction are O(capacity) per call (linear scan for the minimum-count slot), the right trade for the tens-of-keys tables this header targets; a heap-backed version would be faster at considerably more code for a workload this small. - Only string keys and integer (long) counts are supported. - The error bound guarantees the TRUE count lies in [count - error, count] - it does not guarantee an item currently outside the table has a smaller true count than everything still tracked, only that anything reporting a positive (count - error) is definitely frequent. - No money is at risk in the demo. It streams a synthetic array of symbol-name strings only and never sends an order.
Script · MT4 · v1.0 · Free
About Streaming Top K Heavy Hitters
Streaming Top K Heavy Hitters is a script for MetaTrader 4. It shows several symbols in one panel. It has 1 setting, such as Capacity. MQL source code included.
Files in the download: StreamingTopK.mqh, StreamingTopK.txt, StreamingTopKDemo.mq4.
Settings
| Setting | Default | What it does |
|---|---|---|
| Capacity | 3 | Space-Saving table capacity (tracked distinct keys) |
How to install
- Download the ZIP from your PolyMaria library and unzip it.
- In MetaTrader 4 open File → Open Data Folder, then go to MQL4 → Scripts.
- Copy the .mq4 file(s) there. Put any .mqh files in MQL4 → Include.
- Open the .mq4 file in MetaEditor and press Compile (F7) if MetaTrader does not show it.
- Drag the script onto a chart to run it once.
Tags: Trading Sessions · Dashboards & Scanners · MT4 Script · MQL4 Source Code