Quantile splitting


I’m trying to understand what XGBoost does in the “approx” method.
Normally you would go look at all gradients and the different datapoints and split on those.
When splitting with quantiles you calculate the gradients as in algorithm 2
now in algorithm 1 the instances I would be the different splits instead of the Instances right?
normally after you found the maxScore, you will split up the dataset with the instances that have a value higher and lower into the right and left node.

How would you go about splitting the dataset to the right and left node if you use quantiles however? I don’t see how I can split up the G_{kv} dataset without recalculating it. And from what I am reading from papers the G_{kv} does not have to be recalculated (Ong etal. “Adaptive Histogram-Based Gradient Boosted Trees For Federated Learning”)

Thanks for the help!