Frugal streaming. 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

Frugal streaming. 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 https://pastebin.com/wAcCS8WZ