You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Question: How do we ensure TDigest::merge never causes numCentroids over centroidsCapacity and thus index out of bound? #703
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).
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).
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.
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.
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.
Activity
AlexanderSaydakov commentedon Dec 18, 2025
This must be a property of the algorithm.
PavelVesely commentedon Dec 18, 2025
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 commentedon Dec 18, 2025
I think so. Curious if there is some math proof of it. Perhaps cc @tdunning if you're still interested in.
tdunning commentedon Dec 18, 2025
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 commentedon Dec 18, 2025
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 commentedon Dec 23, 2025
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 commentedon Dec 24, 2025
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 commentedon Dec 24, 2025
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.
tisonkun commentedon Sep 15, 2026
Closed as answered. Thanks for all of your inputs.