Weighted quantile sketch algorithm

#1

I wanted help with understanding the levels logic used in PushTemp in quantile.h. I wanted to understand the rationale behind using levels for creating quantiles. The xgboost paper provides description only for merge, prune in detail. Is there any other paper I can refer to for understanding the logic of levels?

Thanks

#2

@RAMitchell Can you give some pointers?

#3

Late to the discussion. Please refer to the paper “A Fast Algorithm for Approximate Quantiles in High Speed Data Streams”

#4

Thanks a lot for this paper.