big difference in ArrayDigest vs AVLTreeDigest quantile result

[xysun]

big difference in ArrayDigest vs AVLTreeDigest quantile result

[tdunning]

Very good observation. What you are seeing is a serious bug that is related to the handling of duplicate values in the AVLTreeDigest.

The ArrayDigest is now deprecated, but the good news is that the new MergingDigest behaves correctly. Here is the new test, similar to what you have, but a bit more extreme:

  public void testSingletonInACrowd() {
        final double compression = 100;
        TDigest dist = factory(compression).create();
        for (int i = 0; i < 10000; i++) {
            dist.add(10);
        }
        dist.add(20);
        dist.compress();
        assertEquals(10.0, dist.quantile(0), 0);
        assertEquals(10.0, dist.quantile(0.5), 0);
        assertEquals(10.0, dist.quantile(0.8), 0);
        assertEquals(10.0, dist.quantile(0.9), 0);
        assertEquals(10.0, dist.quantile(0.99), 0);
        assertEquals(10.0, dist.quantile(0.999), 0);
        assertEquals(20.0, dist.quantile(1), 0);
    }

I think I know a way to make the AVLDigest do the right thing. As I see it, this is a blocking bug for the 3.0 release. The work-around is to use the MergingDigest.

[xysun]

Thanks! This is very helpful.

[tdunning]

I am going to push this to after the 3.2 release so that 3.2 can go out.

[tdunning]

The new interpolation methods look like they may fix this issue.

[tdunning]

This is half fixed, but I won't finish checking that the fix is complete until after this 3.3 release.