[homin]

Most previous sketches used what they called "rank accuracy". So if your inputs were [2^1, 2^2, ...., 2^1000]. The actual p95 is 2^950, and a 0.01 rank-accurate sketch would be allowed to give you any value between 2^940 to 2^960 (which can be up to a factor of 1024 away).

A 0.01 relative-accurate sketch has to give you a value within a factor of 100.

The above example is contrived, but with real web request data, there is often a very long tail, and rank accurate sketches quickly start giving values far from the actual percentiles.

So to more directly answer you question, it's that the maximum error possible is bounded.