Greenwald Khanna Quantile
Greenwald Khanna Quantile Greenwald Khanna Quantile is a deterministic streaming algorithm for approximate quantile queries. It stores a compact ordered summary of the stream and guarantees that returned values have rank error at most $\epsilon n$. The algorithm is useful when the stream is too large to store but percentile queries must remain accurate. Problem Given a stream: $$ x_1, x_2, \dots, x_n $$ support quantile queries: query(phi): return an...