<p>UPDATE: it appears that a new and very good algorithm has appeared, called KLL. See <a href="https://arxiv.org/abs/1603.05346" rel="nofollow noreferrer">paper</a>. It has an implementation <a href="https://github.com/edoliberty/streaming-quantiles/blob/master/kll.py" rel="nofollow noreferrer">in Python</a> and <a href="https://github.com/dgryski/go-kll" rel="nofollow noreferrer">in Go</a>.</p>

<p><a href="https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf" rel="nofollow noreferrer">t-digest</a> has implementations in several languages and satisfies all of your requirements. See <a href="https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf" rel="nofollow noreferrer">the paper</a> that makes comparisons to some other algorithms, e.g. to Q-Digest. You can look for more comparisons in the <a href="https://graphics.stanford.edu/courses/cs468-05-winter/Papers/Information_Aggregation/Suri_sensys04.pdf" rel="nofollow noreferrer">Q-Digest paper</a>.</p>

<p>Generally, both of these algorithms are far superior to sampling-based algorithms for estimating quantiles, in terms of giving much better accuracy given the same amount of storage. You can look for a discussion of many more approximate algorithms in the excellent book <a href="https://rads.stackoverflow.com/amzn/click/com/193301914X" rel="nofollow noreferrer" rel="nofollow noreferrer">Data Streams: Algorithms and Applications</a> (it does not discuss t-digest because it was created after the book was published).</p>

<p>There might be other, better algorithms that I'm not familiar with.</p>

<p>There is currently no Beam wrapper for the t-digest library, but it should not be difficult to develop one using a custom <code>CombineFn</code>. See, for example, <a href="https://github.com/apache/beam/pull/3991" rel="nofollow noreferrer">a current pending PR</a> adding support for a different approximate algorithm using a <code>CombineFn</code>.</p>
efficient algorithm for computing quantiles in terabytes dataset
<p>I am trying to compute quantiles (can be approximate with some accuracy guarantees or error bounds) for a huge dataset (terabytes of data) . How can i efficiently compute quantiles . The requirements are </p>

<pre><code>1) Can be computed efficiently (one-pass) or in a distributed way (merging)
2) High accuracy (or at least can be controlled)
3) Can be re-computed or reproduced in multiple language (java and python)
4) Incrementally updated (not a requirement but good to have)
</code></pre>

<p>The few approaches I am looking at are :</p>

<blockquote>
  <p>1) The naive solution : reservoir sampling (not sure how to do it in<br>
  distributed map reduce way specially how to merge different reservoir 
  samples for same data or two different distributions, are there any<br>
  good implementations ? )</p>
  
  <p>2) t-digest </p>
  
  <p>3) Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay.
  Approximate medians and other quantiles in one pass and with<br>
  limited memory. (Reason being i think some map reduce frameworks like 
  dataflow and BigQuery already implement variation of this AFAIK)</p>
</blockquote>

<p>Can someone who has prior experience with working with these algorithm and techniques provide me some pointers about what are the caveats, pros and cons for each . When to use which method, is one approach arguably better than other if requirement is efficient computation and accuracy better. </p>

<p>I have not in particular used digest based approach and would like to understand better why and when would i prefer something like t-digest over something simple like reservoir sampling to compute the approximate quantiles.</p>