Percentile Aggregation: Help me understand "Accuracy is proportional to q(1-q)."

The terminology is confusing, but it is correct here. Accuracy relative to q(1 - q) means that the error is bounded by a constant times q(1 - q). That is, there is a positive constant C so that |td(q) - f(q)| <= Cq(1 - q) where q -> td(q) is the t-digest estimate, and q -> f(q) is the actual value.

The intuition for why the extreme percentiles are the most accurate is due to the fact that at the extremes the t-digest algorithm uses small clusters and towards the median, larger clusters are used (the size of the clusters is proportional in size to (q(1 - q))^(1/2)).