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
There's a consideration at XGBoost about potentially using the KLL sketch to represent feature value histograms.
One potential blocker is the need for a weighted version of the sketch, this would allow us to use data points that are weighted, and adjust their feature contributions accordingly (See Appendix A of XGBoost paper).
I remember discussing in the past the possibility of using data weights with KLL, is that still an option?
The only option we have thought about would be restricted to positive integer weights and >= 1.
My interpretation of weights in a quantiles context is that an item with a weight of 2 is equivalent to updating the sketch with two identical items with a weight of 1. Is this your understanding?
@thvasilo: Is it possible to assume that all the weights in the data sum up to at least 1? (or some other known constant.) There are no assumptions on individual weights or on weights being integral here, but it does mean you need to know something about the overall scaling of the weights.
There are several possible implementations that incorporate weighting. If you can assume this, then you get the simplest (and perhaps most performant) implementation, but it's certainly possible to handle weights without this assumption as well.
@DanielTing The XGBoost use-case would be for batch training, so we can assume to know all weights in advance and normalize them so they sum to 1.
I'm having a chat with the first author of the linked paper tomorrow, I'll update with any progress. I plan to work on this codebase so I hope we can come up with something we can contribute back.
KLL now supports integer weights: apache/datasketches-cpp#582 · KLL: weighted update, matching… added kll_sketch::update(item, weight), which gives the same result as calling update(item) weight times, for weights from 1 to 2^61 - 1. For large weights its cost grows with the logarithm of the weight. It matches the weighted update in datasketches-java, and it will be in the next release. DS-CPP now has the same capability that DS-Java has had for a while.
Real-valued weights, which the XGBoost use case needed, are not supported. If that is still of interest, please open a new issue that describes the use case. Real-valued weights would require more knowledge about the input stream (e.g., that all weights sum to 1.0 or some constant), or a more complex post-normalization process, which would be slower. Either case would require some significant redesign of the sketch or perhaps a different sketch altogether.
@DanielTing, @thvasilo, thank you for your comments! We would very much appreciate any contributions you may have for the real-valued inputs case.
Closing, since KLL now has the integer weights discussed above and the same capability that DS-Java KLL has.
Activity
leerho commentedon Jun 9, 2020
The only option we have thought about would be restricted to positive integer weights and >= 1.
My interpretation of weights in a quantiles context is that an item with a weight of 2 is equivalent to updating the sketch with two identical items with a weight of 1. Is this your understanding?
thvasilo commentedon Jun 9, 2020
Yes, I think the outcome would be the same in this case. I think for this to be used in XGBoost it would require real-valued weights.
I found the paper that I had in mind when talking to Zohar Karnin a couple of years ago, that includes a weighted extension for KLL (Section 4).
I'll ping @trivialfis in case he wants to chime in.
DanielTing commentedon Jun 10, 2020
@thvasilo: Is it possible to assume that all the weights in the data sum up to at least 1? (or some other known constant.) There are no assumptions on individual weights or on weights being integral here, but it does mean you need to know something about the overall scaling of the weights.
There are several possible implementations that incorporate weighting. If you can assume this, then you get the simplest (and perhaps most performant) implementation, but it's certainly possible to handle weights without this assumption as well.
thvasilo commentedon Jun 10, 2020
@DanielTing The XGBoost use-case would be for batch training, so we can assume to know all weights in advance and normalize them so they sum to 1.
I'm having a chat with the first author of the linked paper tomorrow, I'll update with any progress. I plan to work on this codebase so I hope we can come up with something we can contribute back.
leerho commentedon Nov 19, 2026
KLL now supports integer weights: apache/datasketches-cpp#582 · KLL: weighted update, matching… added kll_sketch::update(item, weight), which gives the same result as calling update(item) weight times, for weights from 1 to 2^61 - 1. For large weights its cost grows with the logarithm of the weight. It matches the weighted update in datasketches-java, and it will be in the next release. DS-CPP now has the same capability that DS-Java has had for a while.
Real-valued weights, which the XGBoost use case needed, are not supported. If that is still of interest, please open a new issue that describes the use case. Real-valued weights would require more knowledge about the input stream (e.g., that all weights sum to 1.0 or some constant), or a more complex post-normalization process, which would be slower. Either case would require some significant redesign of the sketch or perhaps a different sketch altogether.
@DanielTing, @thvasilo, thank you for your comments! We would very much appreciate any contributions you may have for the real-valued inputs case.
Closing, since KLL now has the integer weights discussed above and the same capability that DS-Java KLL has.