On: Algorithms Every Programmer Should Know: Reservoir...

[bradleyjg]

Imagine you are writing software to sit on a router to:

1) collect data for some length of time, and

2) thereafter have available for querying the (maybe approximate) 25th, 50th, 95th, and 99th percentile TCP connection bandwidth thresholds, and

3) signal when a connection grows beyond the 95th percentile.

You only have a fairly limited amount of memory.

[x0x0 → bradleyjg]

While it's great for medians, reservoir sampling for calculating high or low percentiles, particularly with high dynamic range data, will probably have very high error.