A market data feed delivers 5 million trades a second and you must report the 100 symbols with the largest traded volume, with bounded memory. Give an algorithm, state the memory it needs, and state exactly what guarantee it gives about the reported set.

A market data feed delivers 5 million trades a second and you must report the 100 symbols with the largest traded volume, with bounded memory. Give an algorithm, state the memory it needs, and state exactly what guarantee it gives about the reported set.

Approach: Exact top-k in one pass needs memory linear in the number of distinct keys. Relax to a counter-eviction scheme and work out the error it admits.

Run the space saving algorithm with m counters and report the top 100, which uses O(m) memory and guarantees that every symbol holding more than N/m of the total volume N appears in the reported set, so only symbols that are not heavy hitters can be missed. Keep m key-count pairs in a hash map with a pointer to the smallest. On an arrival, add the volume to the counter if the key is tracked, otherwise perform a counter eviction: replace the key of the smallest counter with the new one and add the new volume to the count it already held. Each counter overstates its key by at most the value it inherited, which is at most the current minimum, and that minimum is at most N/m, so every reported count lies between the true count and the true count plus N/m. Setting m = 10^4 for a top 100 report puts the error bound at 0.01% of total volume. Exact top-k in one pass provably needs memory linear in the number of distinct symbols, which is what the relaxation buys off.

Follow-up: How do you make the same report over a sliding window of the last hour rather than since the open?

Key concepts: space saving, heavy hitters, counter eviction, error bound.