You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Ted Dunning (JIRA)" <ji...@apache.org> on 2013/12/02 07:55:37 UTC
[jira] [Updated] (MAHOUT-1368) Convert OnlineSummarizer to use the
new TDigest
[ https://issues.apache.org/jira/browse/MAHOUT-1368?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Ted Dunning updated MAHOUT-1368:
--------------------------------
Attachment: MAHOUT-1368.patch
Here is a patch with additional skewed test.
> Convert OnlineSummarizer to use the new TDigest
> -----------------------------------------------
>
> Key: MAHOUT-1368
> URL: https://issues.apache.org/jira/browse/MAHOUT-1368
> Project: Mahout
> Issue Type: Bug
> Reporter: Ted Dunning
> Fix For: 0.9
>
> Attachments: MAHOUT-1368.patch
>
>
> The new TDigest provides better accuracy for quartile estimation as well as producing any other quantile you might like. The current quartile estimation of the OnlineSummarizer fails for highly skewed distributions and can't really be extended to provide other quantiles. The TDigest handles all of this.
--
This message was sent by Atlassian JIRA
(v6.1#6144)
Re: [jira] [Updated] (MAHOUT-1368) Convert OnlineSummarizer to use
the new TDigest
Posted by Dawid Weiss <da...@cs.put.poznan.pl>.
> I've not heard of t-digest before
Because it's a new Ted's baby, perhaps? ;) See
https://github.com/tdunning/t-digest
The repository contains a tex source and PDF:
https://github.com/tdunning/t-digest/blob/master/docs/theory/t-digest-paper/histo.pdf
Dawid
On Mon, Dec 2, 2013 at 9:35 AM, Andy Twigg <an...@gmail.com> wrote:
> I've not heard of t-digest before. Are there any theoretical
> guarantees on its performance? Can you point me to a published paper?
>
> On 2 December 2013 06:55, Ted Dunning (JIRA) <ji...@apache.org> wrote:
>>
>> [ https://issues.apache.org/jira/browse/MAHOUT-1368?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
>>
>> Ted Dunning updated MAHOUT-1368:
>> --------------------------------
>>
>> Attachment: MAHOUT-1368.patch
>>
>>
>> Here is a patch with additional skewed test.
>>
>>> Convert OnlineSummarizer to use the new TDigest
>>> -----------------------------------------------
>>>
>>> Key: MAHOUT-1368
>>> URL: https://issues.apache.org/jira/browse/MAHOUT-1368
>>> Project: Mahout
>>> Issue Type: Bug
>>> Reporter: Ted Dunning
>>> Fix For: 0.9
>>>
>>> Attachments: MAHOUT-1368.patch
>>>
>>>
>>> The new TDigest provides better accuracy for quartile estimation as well as producing any other quantile you might like. The current quartile estimation of the OnlineSummarizer fails for highly skewed distributions and can't really be extended to provide other quantiles. The TDigest handles all of this.
>>
>>
>>
>> --
>> This message was sent by Atlassian JIRA
>> (v6.1#6144)
>
Re: [jira] [Updated] (MAHOUT-1368) Convert OnlineSummarizer to use the new TDigest
Posted by Ted Dunning <te...@gmail.com>.
Andy
I don't have a published paper yet. I do have an unpublished paper. See github.com/tdunning/t-digest/docs
The paper does not have rigorous bounds but it does have some good empirical comparisons. Bounds for random ordering should be pretty straightforward. The algorithm provides similar performance, however, for perverse ordering so it would be nice to have a way to include that. Repeated values are also tricky to put bounds on. Empirically, accuracy is several orders of magnitude better than q-digest for extreme quantiles and 1-2 orders better near the median.
T-digest is already committed to mahout and I have a pull request in to stream lib. The algebird guys are looking to reimplement in scala.
Sent from my iPhone
> On Dec 2, 2013, at 0:35, Andy Twigg <an...@gmail.com> wrote:
>
> I've not heard of t-digest before. Are there any theoretical
> guarantees on its performance? Can you point me to a published paper?
>
>> On 2 December 2013 06:55, Ted Dunning (JIRA) <ji...@apache.org> wrote:
>>
>> [ https://issues.apache.org/jira/browse/MAHOUT-1368?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
>>
>> Ted Dunning updated MAHOUT-1368:
>> --------------------------------
>>
>> Attachment: MAHOUT-1368.patch
>>
>>
>> Here is a patch with additional skewed test.
>>
>>> Convert OnlineSummarizer to use the new TDigest
>>> -----------------------------------------------
>>>
>>> Key: MAHOUT-1368
>>> URL: https://issues.apache.org/jira/browse/MAHOUT-1368
>>> Project: Mahout
>>> Issue Type: Bug
>>> Reporter: Ted Dunning
>>> Fix For: 0.9
>>>
>>> Attachments: MAHOUT-1368.patch
>>>
>>>
>>> The new TDigest provides better accuracy for quartile estimation as well as producing any other quantile you might like. The current quartile estimation of the OnlineSummarizer fails for highly skewed distributions and can't really be extended to provide other quantiles. The TDigest handles all of this.
>>
>>
>>
>> --
>> This message was sent by Atlassian JIRA
>> (v6.1#6144)
Re: [jira] [Updated] (MAHOUT-1368) Convert OnlineSummarizer to use
the new TDigest
Posted by Andy Twigg <an...@gmail.com>.
I've not heard of t-digest before. Are there any theoretical
guarantees on its performance? Can you point me to a published paper?
On 2 December 2013 06:55, Ted Dunning (JIRA) <ji...@apache.org> wrote:
>
> [ https://issues.apache.org/jira/browse/MAHOUT-1368?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
>
> Ted Dunning updated MAHOUT-1368:
> --------------------------------
>
> Attachment: MAHOUT-1368.patch
>
>
> Here is a patch with additional skewed test.
>
>> Convert OnlineSummarizer to use the new TDigest
>> -----------------------------------------------
>>
>> Key: MAHOUT-1368
>> URL: https://issues.apache.org/jira/browse/MAHOUT-1368
>> Project: Mahout
>> Issue Type: Bug
>> Reporter: Ted Dunning
>> Fix For: 0.9
>>
>> Attachments: MAHOUT-1368.patch
>>
>>
>> The new TDigest provides better accuracy for quartile estimation as well as producing any other quantile you might like. The current quartile estimation of the OnlineSummarizer fails for highly skewed distributions and can't really be extended to provide other quantiles. The TDigest handles all of this.
>
>
>
> --
> This message was sent by Atlassian JIRA
> (v6.1#6144)