Adjusting the centroid threshold values to obtain better accuracy at interesting values

[tdunning]

Adjusting the centroid threshold values to obtain better accuracy at interesting values

[tdunning]

Sorry for the delay in responding.

Yes. You can do exactly what you say.

In the current implementations, you should observe some constraints on your mapping function. The basic idea is that you need to make sure that the total space for the digest is bounded. The condition that allows this is that the bounding has to have the right properties. The gotcha is that the minimum count for a centroid is 1 so for some functions the number of centroids with a single sample grows unboundedly. This is true, for instance, for the original q (1-q) constraint. On the other hand, if you use sqrt(q (1-q)) as your constraint, the size is bounded.

In the current forms of the algorithm itself, the way that this works is that there is something called an index function that maps q to an index k. A centroid is legal if it goes from q_0 to q_1 and if N(k(q_1) - k(q_0)) < 1 except that we always allow centroids with a single element. If you look at the copy of the paper in the master branch, you will see a bit of what I mean. It isn't finished, but it gets pretty far down that line.

The normal index curve looks like this:

For your example, you could use an index curve where the steep part is in the middle instead of near the edges. Kind of like this: