Design a Streaming Percentile Estimator

You are receiving an unbounded stream of numeric observations and need to answer percentile queries without retaining every value. Design an estimator for a given quantile q (where 0 <= q <= 1) and explain precisely what an error statement of plus or minus epsilon (where 0 < epsilon < 1) guarantees.

Your design should address two primary targets:

1. A deterministic single-stream summary whose returned value's rank is within epsilon * N of the target rank after N observations.
2. A centroid-based estimator, such as a t-digest, that prioritizes accuracy near the tails of the distribution.

Compare the two approaches in terms of update cost, memory usage, behavior on duplicate values and skewed distributions, practical merge behavior, and the strength of the guarantees each can honestly claim. Assume that a classic deterministic summary cannot be merged by simple concatenation or recompression while retaining its original error bound. Do not present empirical t-digest accuracy as a universal worst-case guarantee.

Constraints & Assumptions:

• Values arrive one at a time and may be repeated or highly skewed.
• Queries occur only after at least one observation.
• Exact minimum and maximum should be available for q=0 and q=1.
• Rank error alone gives no numeric-value error bound without distribution assumptions.
• If distributed merging is proposed, state exactly which guarantee survives and under which invariant; otherwise, identify the limitation.