<p>@thkala started off with some literature citations. Let me extend that.</p>
<h2>Implementations</h2>
<ul>
<li><a href="https://github.com/tdunning/t-digest" rel="nofollow noreferrer">T-digest</a> from the 2019 Dunning paper has reference implementation in Java, and ports on that page to Python, Go, Javascript, C++, Scala, C, Clojure, C#, Kotlin, and <a href="https://github.com/facebook/folly/blob/main/folly/stats/TDigest.cpp" rel="nofollow noreferrer">C++ port by facebook</a>, and a further <a href="https://crates.io/crates/tdigest/0.2.2" rel="nofollow noreferrer">rust port of that C++ port</a></li>
<li><a href="https://spark.apache.org/" rel="nofollow noreferrer">Spark</a> implements &quot;GK01&quot; from the 2001 Greenwald/Khanna paper for approximate quantiles</li>
<li><a href="https://beam.apache.org/releases/javadoc/2.1.0/org/apache/beam/sdk/transforms/ApproximateQuantiles.html" rel="nofollow noreferrer">Beam: org.apache.beam.sdk.transforms.ApproximateQuantiles</a> has approximate quantiles</li>
<li>Java: <a href="https://guava.dev/releases/23.0/api/docs/com/google/common/math/Quantiles.html" rel="nofollow noreferrer">Guava:com.google.common.math.Quantiles</a> implements exact quantiles, thus taking more memory</li>
<li>Rust: <a href="https://docs.rs/quantiles/0.7.1/quantiles/" rel="nofollow noreferrer">quantiles crate</a> has implementations for the 2001 GK algorithm &quot;GK01&quot;, and the 2005 CKMS algorithm. (caution: I found the CKMS implementation slow - <a href="https://github.com/postmates/quantiles/issues/32" rel="nofollow noreferrer">issue</a>)</li>
<li>C++: <a href="https://www.boost.org/doc/libs/1_46_1/libs/math/doc/sf_and_dist/html/math_toolkit/dist/stat_tut/weg/normal_example/normal_misc.html" rel="nofollow noreferrer">boost quantiles</a> has some code, but I didn't understand it.</li>
<li>I did some profiling of the options in Rust [<a href="https://github.com/postmates/quantiles/issues/32" rel="nofollow noreferrer">link</a>] for up to 100M items, and found GK01 the best, T-digest the second, and &quot;keep 1% top values in priority queue&quot; the third.</li>
</ul>
<h2>Literature</h2>
<ul>
<li><p>2001: <a href="http://infolab.stanford.edu/%7Edatar/courses/cs361a/papers/quantiles.pdf" rel="nofollow noreferrer">Space-efficient online computation of quantile summaries</a> (by Greenwald, Khanna). Implemented in Rust: <a href="https://docs.rs/quantiles/0.7.1/quantiles/greenwald_khanna/index.html" rel="nofollow noreferrer">quantiles::greenwald_khanna</a>.</p>
</li>
<li><p>2004: <a href="https://arxiv.org/abs/cs/0408039" rel="nofollow noreferrer">Medians and beyond: new aggregation techniques for sensor networks</a> (by Shrivastava, Buragohain, Agrawal, Suri). Introduces &quot;q-digests&quot;, used for fixed-universe data.</p>
</li>
<li><p>2005: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.853&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Effective computation of biased quantiles over data streams</a> (by Cormode, Korn, Muthukrishnan, Srivastava)... Implemented in Rust: <a href="https://docs.rs/quantiles/0.7.1/quantiles/ckms/index.html" rel="nofollow noreferrer">quantiles::ckms</a> which notes that the IEEE presentation is correct but the self-published one has flaws. With carefully crafted data, space can grow linearly with input size. &quot;Biased&quot; means it focuses on P90/P95/P99 rather than all the percentiles).</p>
</li>
<li><p>2006: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.793&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Space-and time-efficient deterministic algorithms for biased quantiles over data streams</a> (by Cormode, Korn, Muthukrishnan, Srivastava)... improved space bound over 2005 paper</p>
</li>
<li><p>2007: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.8534&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">A fast algorithm for approximate quantiles in high speed data streams</a> (by Zhang, Wang). Claims 60-300x speedup over GK. The 2020 literature review below says this has state-of-the-art space upper bound.</p>
</li>
<li><p>2019 <a href="https://arxiv.org/abs/1902.04023" rel="nofollow noreferrer">Computing extremely accurate quantiles using t-digests</a> (by Dunning, Ertl). Introduces t-digests, O(log n) space, O(1) updates, O(1) final calculation. It's neat feature is you can build partial digests (e.g. one per day) and merge them into months, then merge months into years. This is what the big query engines use.</p>
</li>
<li><p>2020 <a href="https://arxiv.org/pdf/2004.08255.pdf" rel="nofollow noreferrer">A survey of approximate quantile computation on large-scale data (technical report)</a> (by Chen, Zhang).</p>
</li>
<li><p>2021 <a href="https://www.sciencedirect.com/science/article/pii/S2665963820300403" rel="nofollow noreferrer">The t-digest: Efficient estimates of distributions</a> - an approachable wrap-up paper about t-digests.</p>
</li>
</ul>
<h2>Cheap hack for P99 of &lt;10M values: just store top 1% in a priority queue!</h2>
<p>This'll sound stupid, but if I want to calculate the P99 of 10M float64s, I just created a priority queue with 100k float32s (takes 400kB). This takes only 4x as much space as &quot;GK01&quot; and is much faster. For 5M or fewer items, it takes less space than GK01!!</p>
<pre><code>struct TopValues {
    values: std::collections::BinaryHeap&lt;std::cmp::Reverse&lt;ordered_float::NotNan&lt;f32&gt;&gt;&gt;,
}

impl TopValues {
fn new(count: usize) -&gt; Self {
    let capacity = std::cmp::max(count / 100, 1);
    let values = std::collections::BinaryHeap::with_capacity(capacity);
    TopValues { values }
}

fn render(&amp;mut self) -&gt; String {
    let p99 = self.values.peek().unwrap().0;
    let max = self.values.drain().min().unwrap().0;
    format!(&quot;TopValues, p99={:.4}, max={:.4}&quot;, p99, max)
}
fn insert(&amp;mut self, value: f64) {
    let value = value as f32;
    let value = std::cmp::Reverse(unsafe { ordered_float::NotNan::new_unchecked(value) });

    if self.values.len() &lt; self.values.capacity() {
        self.values.push(value);
    } else if self.values.peek().unwrap().0 &lt; value.0 {
        self.values.pop();
        self.values.push(value);
    } else {
    }
}
}
</code></pre>
Percentiles of Live Data Capture
<p>I am looking for an algorithm that determines percentiles for live data capture.</p>

<p>For example, consider the development of a server application.</p>

<p>The server might have response times as follows:
17 ms
33 ms
52 ms
60 ms
55 ms
etc.</p>

<p>It is useful to report the 90th percentile response time, 80th percentile response time, etc.</p>

<p>The naive algorithm is to insert each response time into a list. When statistics are requested, sort the list and get the values at the proper positions.</p>

<p>Memory usages scales linearly with the number of requests.</p>

<p>Is there an algorithm that yields "approximate" percentile statistics given limited memory usage? For example, let's say I want to solve this problem in a way that I process millions of requests but only want to use say one kilobyte of memory for percentile tracking (discarding the tracking for old requests is not an option since the percentiles are supposed to be for all requests).</p>

<p>Also require that there is no a priori knowledge of the distribution. For example, I do not want to specify any ranges of buckets ahead of time.</p>