<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Manikanta on Medium]]></title>
        <description><![CDATA[Stories by Manikanta on Medium]]></description>
        <link>https://medium.com/@mani.?source=rss-11b7229565ee------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*tguiu4pedt_2708PJFgcig.jpeg</url>
            <title>Stories by Manikanta on Medium</title>
            <link>https://medium.com/@mani.?source=rss-11b7229565ee------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 01:33:48 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mani./feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[T-Digest: An interesting datastructure to estimate quantiles accurately.]]></title>
            <link>https://medium.com/@mani./t-digest-an-interesting-datastructure-to-estimate-quantiles-accurately-b99a50eaf4f7?source=rss-11b7229565ee------2</link>
            <guid isPermaLink="false">https://medium.com/p/b99a50eaf4f7</guid>
            <category><![CDATA[t-digest]]></category>
            <category><![CDATA[anomaly]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[quantile]]></category>
            <dc:creator><![CDATA[Manikanta]]></dc:creator>
            <pubDate>Sat, 31 Mar 2018 05:17:22 GMT</pubDate>
            <atom:updated>2018-03-31T05:17:22.495Z</atom:updated>
            <content:encoded><![CDATA[<p>A new data structure for accurate accumulation of rank-based statistics such as quantiles &amp; percentiles. We can use this data structure for detecting anomalies in the point data. It is implemented in Java and can be found in <a href="https://github.com/tdunning/t-digest">Github</a>. The basic outline of the algorithm has been given below, but for more detailed explanation refer to this paper[5]. Please check references section for interesting lectures. Before digging into what T-Digest does, let me first define what a quantile and trimmed-mean is.</p><p><strong>Quantiles &amp; Percentiles:</strong></p><p>These are standard statistical techniques Quantiles, Percentiles &amp; Deciles which are used to divide a set of numbers into equal subsets. To be precise, Median is a 2-Quantile i.e., it divides the data into two equal parts. Quartiles divides into 4 equal parts and Percentile divides into 100 equal parts.[<a href="https://www-users.york.ac.uk/~mb55/intro/quantile.htm">1</a>]</p><p><strong>Trimmed mean:</strong></p><p>Trimmed mean is the average of the dataset that we get after trimming X%. For example, 50% Trimmed mean is cutting down 25% of both lower and higher scores. Median is the 100% Trimmed mean. Where actual mean(average) is 0% Trimmed mean. Trimmed mean is obviously less susceptible than the effects of higher score than the arithmetic mean.[<a href="http://davidmlane.com/hyperstat/A11971.html">3</a>]</p><p><strong>Internals of T-Digest:</strong></p><ul><li>Let’s assume we have samples samples X = {x1 . . . xn} are presented in ascending order.</li><li>A t-digest is formed from the sequence of points by grouping all of the samples into sub- sequences of samples, X = {s1|s2| . . . |sm} where si = {xleft(i) . . . xright(i)}.</li><li>Importantly, we force sub-sequences near the ends to be small while allowing sub-sequences in middle to be larger in order to get fairly constant relative accuracy, refer to Fig: 2.</li><li>To limit the sub-sequence size in this way, we define a mapping from quantile q to a notional index k with compression parameter δ. This mapping is known as the scaling function as shown in Fig:1. The mapping k is monotonic with minimum value k(0) = 0 and maximum value k(1) = δ.</li><li>The introduction of the concept of a scaling function provides a useful way to see the core distinction between conventional percentile approximation algorithms that use equal-sized bins and the t-digest with its non-equal bin sizes. The only really necessary characteristics of a scaling function is that be monotonic and satisfy the constraints that k(0) = 0 and k(1) = δ.</li><li>Once we have formed a t-digest by binning the original sequence into sub-sequences that satisfy the size limit, we can estimate quantiles using interpolation between the end-points of each bin. So, each bin will have a centroid associated with it which contains mean &amp; sum, value K. Till this part, we have seen a set of centroids C= {1,….m} constructed from the initial dataset.</li><li><strong>Progressive merging algorithm</strong>: The operation of merging a buffer’s worth of samples into an existing set of centroids is shown in Fig: 5 given below.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*nkrC1aN-QcGfRuon." /></figure><ul><li>Also, the number of points assigned to each centroid is limited so that the new data point is never added to a centroid if the combination would exceed the t-digest size constraint.</li><li><strong>Finding the Quantile at a point:</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-5eF-Dbo5OZ0bWeT." /></figure><ul><li><strong>Computing T-Digests in parallel</strong>: For example, in a map-reduce framework such as Hadoop, a combiner function can compute the t-digest for the output of each mapper and a single reducer can be used to compute the t-digest for the entire data set.</li><li><strong>Associative &amp; Cumulative Properties of T-Digest: </strong>Let’s say we have datasets that are being processed in N different systems. In that case, we can process data into the t-Digest sequentially, so we have N t-Digests in N computers happening the map stage(map-reduce scenario). At the reduce stage, we can define an addition operation on two t-Digests as follows. Create a new t-Digest and treat the internal centroids of the two left-hand side digests as incoming data. The resulting t-Digest is a only slightly larger, but more accurate, t-Digest.</li><li><strong>Conclusion</strong>: T-Digest provides accurate on-line estimates of a variety of rank-based statistics including quantiles and trimmed mean. It has already been adopted by the Apache Mahout and stream-lib projects and is likely to be adopted by other projects as well.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*rxgWY-yFVugb4SUU." /><figcaption>Fig:1</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hLF6vVHVuFsSOgDc." /><figcaption>Fig: 2</figcaption></figure><p><strong>Sample Case Study:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*d-sUdD1zrL52nLCf." /><figcaption>Fig: 3</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*bBccilr3xbAkAblE." /><figcaption>Fig: 4</figcaption></figure><p><strong>Problem statement:</strong></p><p>Let’s say we have a dataset of billion values ranging from [100–10000000]. We want to find the outliers(anomalies) information in the above dataset. So, given below an efficient solution using T-Digest.</p><p>Create a new TDigest() instance.</p><ol><li>After ingesting data, the data structure has learned the “interesting” points of the CDF, called centroids. Refer to Fig: 3, Fig: 4.</li><li>In the next step as shown in the algorithm, we set a compression factor value of 100(used in most cases) and create an ArrayDigest.</li><li><strong>LOC</strong>: val totalDigest = TDigest.createArrayDigest(100)</li><li>Then we add all the values into tdigest object.totalData.foreach(value =&gt; totalDigest.add(value))</li><li>Then we do .quantile to obtain the threshold value at the tails. This threshold means that we expect ~0.1% of data is anomalies.<br> <strong>LOC:</strong> val threshold = totalDigest.quantile(0.999d).toInt</li></ol><p>For more detailed explanation refer to this blog: [<a href="http://koff.io/posts/using-t-digest/">6</a>]</p><p><strong>Currently using:</strong></p><ul><li>An aggregator in Elastic Search</li><li>In Stream-lib</li><li>Apache Mahout</li></ul><p><strong>References:</strong></p><p>[1] — : <a href="https://www-users.york.ac.uk/~mb55/intro/quantile.htm">Medians/Quantiles/Outliers well explained</a></p><p>[2] — : <a href="https://berlinbuzzwords.de/sites/berlinbuzzwords.de/files/media/documents/ted_dunning-practical_t-digest_applications.pdf">Ted[T-Digest owner] presentation</a></p><p>[3] — : <a href="http://davidmlane.com/hyperstat/A11971.html">Trimmed Mean explained</a></p><p>[4] — : <a href="https://math.stackexchange.com/questions/52400/what-is-cdf-cumulative-distribution-function">CDF(Cumulative Distribution Function)</a></p><p>[5] — : <a href="https://raw.githubusercontent.com/tdunning/t-digest/master/docs/t-digest-paper/histo.pdf">Paper on T-Digest</a></p><p>[6] — : <a href="http://koff.io/posts/using-t-digest/">Blog on T-Digest, Anomaly</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b99a50eaf4f7" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>