Streaming Approximate Quantiles with Rank-Error Guarantees
Problem statement
You have a stream of $n$ elements arriving one at a time, and you need to answer quantile queries on the fly. For any queried rank fraction $\phi \in (0,1)$, you want to return an element whose rank is within $\pm \varepsilon n$ of the true $\phi$-quantile, where $\varepsilon > 0$ is a precision parameter you choose up front.
Design a one-pass, deterministic streaming algorithm that:
- Answers any $\phi$-quantile query with rank error at most $\varepsilon n$.
- Uses $O\bigl(\frac{1}{\varepsilon} \log(\varepsilon n)\bigr)$ space.
- Processes each incoming element in $O\bigl(\log(1/\varepsilon)\bigr)$ amortized time.
Specifically:
- Describe the data structure you maintain and how it is updated when a new element arrives.
- Prove that the rank error of any query is at most $\varepsilon n$.
- Explain how summaries from two independent streams can be merged while preserving the $\varepsilon$-approximate guarantee -- i.e., why is this structure "mergeable"?
Graded function: an approximate sketch has many acceptable answers, so the grader checks the exact quantity GK approximates. Implement stream_quantiles(stream, phis): for each $\phi$ in phis, return the element of rank $r = \lceil \phi n \rceil$ (1-indexed) in the sorted order of the full stream, with answers in query order. stream is non-empty and each $\phi \in (0, 1)$.
Examples
stream_quantiles([1, 1, 1, 1], [0.25, 0.75]) -> [1, 1]
stream_quantiles([5, 1, 4, 2, 3], [0.2, 0.5, 0.9]) -> [1, 3, 5]
In the second example the sorted stream is $[1, 2, 3, 4, 5]$ and the ranks are $\lceil 1 \rceil = 1$, $\lceil 2.5 \rceil = 3$ and $\lceil 4.5 \rceil = 5$.
Show hint
Instead of storing every value, what if each kept value carried a lower and an upper bound on its rank?
Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.