Awful quantile estimation on small sample size

[caio]

Following the discussion on PR #11 I've isolated a tiny pathological sample:

t := New(10)
data := []float64{0, 279, 2, 281}
for _, f := range data {
    t.Add(f, 1)
}
fmt.Println(t.Quantile(0.25))

Which yields -67.7500. In hindsight, this outrageously wrong number should have raised a major red flag in my head already, but when comparing to Java this gets even more obviously wrong:

public class Ughhh {
    public static void main(String[] args) {
        TDigest t = new AVLTreeDigest(10);
        Arrays.asList(0, 279, 2, 281).forEach(t::add);
        System.out.println(t.quantile(0.25));
    }
}

Prints out 1.0 😅 (Note: before the min/max patch on tdunning/t-digest@89bb394 it yields 1.5).

[caio]

So here's my current understanding of this issue:

This implementation estimates the value under a quantile following Algorithm 4 described in the paper whereas the reference implementation uses a different method.

Whilst using the reference implementation does behave a lot better for this pathological example, it also suffers from a serious bug (Notice that the test is disabled in the reference implementation).

Interestingly the current version does not suffer from the singletonInACrowd bug. So it would be trading one bug for another. It's hard for me to say which is worse for I don't quite understand the impact of this current issue on similar-but-real shapes.

Apparently there's a new approach being developed which I'll take a look at as soon as possible. I also skimmed through the merging digest implementation and it seems like it's not much work to port it.

[caio]

Alright, branch avl-wip now contains code that is able to close this issue.

Gotchas (explanation in the commit message):

• 8a6b3a5
• baa0190

Another notable commit (because it makes test execution significantly slower): 79b62e9

I'm pretty happy with the results, even considering the above gotchas so my plan is cleaning the branch up (a lot of code has gone away, I didn't pay attention to abstractions nor "niceties") when I can and merging it as a real fix for this. If anyone is watching, now it's the time to shout 😝

[caio]

The fix has been released on v1.1.3: https://github.com/caio/go-tdigest/releases/tag/v1.1.3