Question: How do we ensure `TDigest::merge` never causes numCentroids over centroidsCapacity and thus index out of bound?

[tisonkun]

datasketches-java/src/main/java/org/apache/datasketches/tdigest/TDigestDouble.java

Lines 571 to 602 in 37edd8c

	numCentroids_ = 0;
	Sort.stableSort(values, weights, num);
	if (reverseMerge_) { // this might be avoidable if stableSort could be implemented with a boolean parameter to invert the logic
	Sort.reverse(values, num);
	Sort.reverse(weights, num);
	}
	centroidMeans_[0] = values[0];
	centroidWeights_[0] = weights[0];
	numCentroids_++;
	int current = 1;
	double weightSoFar = 0;
	while (current != num) {
	final double proposedWeight = centroidWeights_[numCentroids_ - 1] + weights[current];
	boolean addThis = false;
	if ((current != 1) && (current != (num - 1))) {
	final double q0 = weightSoFar / centroidsWeight_;
	final double q2 = (weightSoFar + proposedWeight) / centroidsWeight_;
	final double normalizer = ScaleFunction.normalizer(k_ * 2, centroidsWeight_);
	addThis = proposedWeight <= (centroidsWeight_ * Math.min(ScaleFunction.max(q0, normalizer), ScaleFunction.max(q2, normalizer)));
	}
	if (addThis) { // merge into existing centroid
	centroidWeights_[numCentroids_ - 1] += weights[current];
	centroidMeans_[numCentroids_ - 1] += ((values[current] - centroidMeans_[numCentroids_ - 1])
	* weights[current]) / centroidWeights_[numCentroids_ - 1];
	} else { // copy to a new centroid
	weightSoFar += centroidWeights_[numCentroids_ - 1];
	centroidMeans_[numCentroids_] = values[current];
	centroidWeights_[numCentroids_] = weights[current];
	numCentroids_++;
	}
	current++;
	}

I don't find any constraint that numCentroids will never exceed centroidsCapacity here.

[AlexanderSaydakov]

This must be a property of the algorithm.

[PavelVesely]

Hello, noticed this issue by chance. In my experiments with the original implementation, t-digest is actually pretty bad in keeping the number of centroids close to the prescribed size. (Specifically, I have to manually adjust the number of centroids. Btw, the experimental results are in my recent paper.)

So I believe it's the property of the exact implementation of the algorithm (perhaps some adjustments of the algorithm could fix it but could also make the accuracy worse).

[tisonkun]

This must be a property of the algorithm.

I think so. Curious if there is some math proof of it. Perhaps cc @tdunning if you're still interested in.

[tdunning]

Yes. There is just such a proof. The existence of a proof is a key requirement of the scale function.

https://arxiv.org/abs/1903.09921

[tdunning]

The size proof is the interesting counterpoint between the relative error version of the KL sketch and the t-digest. The KL sketch has hard limits on accuracy with unbounded (log N) size. The t-digest has hard limits on size (but only hazy and empirical bounds on accuracy).

[leerho]

This is why we have the KLL, REQ, and T-digest sketches in the library. One size doesn't fit all.

The "unbounded (log N) size" sounds a bit harsh, although theoretically correct. I have characterized the growth path of our KLL sketches with streams up to over 10^12 items:

The following graph illustrates the typical size of KLL Floats and KLL Doubles Sketches vs number of items. Once the sketch, of a given K, reaches its "full compaction shape" its size grows very, very slowly. As you can see here, a KllDoubles sketch of 10^10 items would be about 6KB in size. The KllFloats sketch is about half that. This means for practical stream sizes, the KLL sketches stay pretty small.

The growth path for KLL can be estimated from equations and plots that predict the size of the sketch fairly accurately. The following plot shows the growth path normalized per byte of item size. This can be used even for items of variable size as long as you can estimate the average item size.

A KLL sketch of a larger"K", would shift this graph to the right. A smaller "K" would shift it to the left.

[tdunning]

Lee,

The real issue with anything other than constant size is the requirement for dynamic allocation after startup. This is an all or nothing issue. There are environments where dynamic allocation during operation is a very bad thing (the stuff I have been doing with embedded systems is an example). Even if the language has garbage collection, minimizing and simplifying the requirements for dynamic allocation pays benefits, often in terms of memory fragmentation.

I agree that the different between O(1) and O(log N) space may be small in the practicalities of many situations, but there are definitely other considerations. There are cases where O(1) algorithms are much, much slower than O(log N) algorithms and there are environments where allocation is forbidden. This is just another example of your original point that your mileage will vary.

[leerho]

Ted,

Thank you for your comments! I am well aware that these sketches are not suitable for all situations. And precisely because of that, we try to provide comparative and characterization data of our sketches so that users can make informed decisions about which sketches to use and what to expect when they use them. Unless the user can find, read and understand the theoretical research papers that is behind these sketches, this kind of comparative and characterization data is hard to find and certainly not found in one place.

Our work is not perfect, but with help like your comments above, we can continue to improve the quality of our code and descriptive content.