For estimating a median or percentile in a stream, using constant memory.
It's very simple: if the current value is higher than our estimate, then increase our estimate by one. Else decrease by one. It will converge over long enough time.
This is called the Frugal-1U algorithm.
The Frugal-2U is a slightly more advanced version that modifies the step size along the way, plus other optimizations, to converge faster and not oscillate too much.
For estimating a median or percentile in a stream, using constant memory.
It's very simple: if the current value is higher than our estimate, then increase our estimate by one. Else decrease by one. It will converge over long enough time. This is called the Frugal-1U algorithm.
The Frugal-2U is a slightly more advanced version that modifies the step size along the way, plus other optimizations, to converge faster and not oscillate too much.
https://pastebin.com/wAcCS8WZ