I am trying to implement t-digest. Everything is more or less straight forward, except one "little" thing - compression (compaction) of the centroids.
I will use the t-digest in my own database hm4 (https://github.com/nmmmnu/HM4) and I really need the centroids to to be stored in fixed-size array. It will be not very fast because you either will need to search the "nearest" centroid or and you need to sort the array from time to time. Let suppose that is OK.
However most compression implementations I checked in examples and AI sites, merge the centroids only if they are nearby (there is a constant called compression) and code is something like this:
if (Math.abs(last.mean - current.mean) < compression) {
// merge last and current centroid
}
This means that there is a case in which compression will not reduce the size of the array.
One AI I checked suggested each centroid to have "date" field and I can drop oldest data. Strange enough it also suggested, if two centroids are merged, the "date" of the new centroid is minimum "date" from both. This mean, if I drop a centroid, its weight can be huge, which is not acceptable at least for me.
Another example I checked, just skip adding the data, if compression does not free space. This may mean if certain point is reached, no new data will enter into the t-digest.
So what is the better way to do it, if resize of the array is not an option:
- drop data - most demo code doing that.
- remove oldest centroid - an AI suggestions, I never saw it on internet.
- merge two "nearest" centroids, even they are spaced on distance more than
compression. - add data to the "nearest" centroid, even they are spaced on distance more than
compression- this is my own idea.
