<p>Looking for algorithms means entering the realm of Academia, so it's helpful to know the proper name of the problem. We're looking for a <a href="https://en.wikipedia.org/wiki/Streaming_algorithm" rel="nofollow noreferrer">Streaming Algorithm</a>, probably Quantile Streaming although you may want other statistics too. Search for that phrase and you'll get more informed answers.</p>

<p>One easy answer is <a href="https://sites.cs.ucsb.edu/~suri/psdir/ency.pdf" rel="nofollow noreferrer">this paper</a>, a collaboration between Amazon and Academia describing the state of the art as of 2007. It provides a high-level view of the Greenwald-Khanna (GK) and Q-Digest algorithms. You can actually find those algorithms in libraries. <a href="https://github.com/sengelha/streaming-percentiles" rel="nofollow noreferrer">This library</a> has an easy to use looking C++ and JS implementation. The <a href="https://software.intel.com/en-us/mkl-ssnotes-computing-quantiles-for-streaming-data-with-vsl-ss-method-squants-zw" rel="nofollow noreferrer">Intel Math Kernel Library</a> implements Zhang 2007.</p>

<p>While the sengelha library looks easy to use and good enough for most needs, the world has moved on since 2007. A <a href="https://arxiv.org/abs/1907.00236" rel="nofollow noreferrer">paper from this year</a> (Amazon, Yahoo, and Academia) describes the "lazy kll" algorithm which is implemented in the <a href="https://datasketches.github.io/" rel="nofollow noreferrer">Data Sketches</a> library (C++, Java, Python) <a href="https://github.com/apache/incubator-datasketches-cpp/blob/master/kll/include/kll_sketch.hpp" rel="nofollow noreferrer">here</a>.</p>

<p>This information should be enough to let you generate quantile data from your software or even distributed software, and I hope others post even better answers.</p>
How can I generate performance metrics without storing much data? (Quantile Streaming)
<p>It's such a common problem but the answers are hard to find. I want to measure the performance of [ web server 95th percentile response time | API calls | algorithm performance | disk I/O | whatever ]. But, you know, that's a lot of data and I don't want to store it because this is used in <em>production</em>. Also, I don't want to spend a lot of CPU time calculating how slow my software is.</p>

<p>If you search for answers, you'll see many references to ancient algorithms that store a ton of data in bins or keep a large reservoir of random sample data. Common results include P-square and binmedian , and notice it's hard to find any decent implementations because although they're commonly suggested they're also garbage and nobody with a clue uses them.</p>

<p>You'll also find clever-sounding answers you can't implement because half the explanation is missing. Maybe if you were a stats major you'd understand <a href="https://stackoverflow.com/a/2144754">this</a>.</p>

<p>So what can I use to get cheap performance statistics? Algorithm and source code, please.</p>