Add an API to directly compute median value of a column in RDataFrame

[vepadulano]

Feature description

Request from a forum post https://root-forum.cern.ch/t/calculating-median-with-rdataframe/64941

Alternatives considered

• Takeing all the values of the column and computing the median manually (e.g. with other popular libraries such as numpy)
• Creating a custom action with Book

Additional context

No response

[ferdymercury]

Could (re)use https://root.cern/doc/master/namespaceTMath.html#a41b4842224232ede7726f26624365d2e

[vepadulano]

Could (re)use https://root.cern/doc/master/namespaceTMath.html#a41b4842224232ede7726f26624365d2e

In principle yes, but that would require storing the whole column in a temporary vector, which would be unoptimal.

[vepadulano]

Just to add to my previous comment, I believe properly addressing this issue should consider:

• Giving the possibility to compute the exact median, which in general would be more costly
• Implementing an online algorithm to compute the median that implies not storing all values in the column upfront

Both possibilities should coexist, probably within the same API, and there should be a clearly documented way of accessing one vs the other. The feature should be tested locally with one thread, locally with multithreading, and distributed with multiprocessing.

[ArjunXvarma]

Hi @vepadulano, I'd like to work on this as a first contribution. I'm new to the ROOT framework, but I have worked with similar data science libraries (NumPy, pandas, Matplotlib, scikit-learn) and have a C++ systems background. My plan is to read the RDataFrame docs, study how the existing Mean/StdDev actions are implemented, and then follow that pattern to add a Median action. Does that sound like a reasonable approach? Happy to hear any pointers before I start.

[MehkaanKhan]

Thanks for the detailed requirements @vepadulano! Since exact + online + distributed is a lot for one PR, I'd like to propose splitting it into two, and get your thoughts before I start coding.

Phase 1: exact median.
A new MedianHelper alongside MeanHelper/StdDevHelper in ActionHelpers.hxx. Each slot buffers its values like TakeHelper does today, then Finalize() concatenates and runs std::nth_element to get the middle value(s), so we skip a full sort. For distributed RDF I'd add an RMergeableValue subclass so the per-slot/per-process buffers merge correctly.

Phase 2: online/approximate median.
I'd like your input on the algorithm before writing this one. The P² algorithm is the classic O(1)-memory streaming approach, but two independent P² estimators don't merge cleanly across threads or processes. t-digest merges much more easily and seems like a better fit given the multithreading/distributed requirement, but let me know if you have a preference or if ROOT has a policy against adding this kind of dependency.

Also curious what API shape you'd prefer: one Median(colName, EMedianMode) with an enum (kExact/kOnline), or two separate methods. I lean toward the single method, but happy to go whichever way you think fits better.

Let me know if this split works or if you'd rather see both in one PR.

[ArjunXvarma]

Hi @MehkaanKhan, the split makes a lot of sense. One more option worth weighing alongside t-digest is a KLL sketch - similar mergeability (works for the multithreaded and distributed cases) but with provable error bounds, could be useful for a library such as this.

@vepadulano if the 2 PR split works for you, I'd be happy to prototype phase 2 in parallel. I have a source build of master set up and have been digging into the action helpers, so I can work on phase 2 while phase 1 lands.

[vepadulano]

Hi @MehkaanKhan and @ArjunXvarma ,

Thank you for showing interest in the ROOT project and wanting to help out with this issue!

I have no objections to proposing PRs, in fact they are always more than welcome! In this case since more than one contributor is interested in the same issue, I suggest you find a way to split the work to avoid overlap and inefficient use of time.

I roughly agree with the idea of proposing first an helper class responsible for calculating the exact median. In principle, the first PR could just contain the single-thread functionality and then multi-thread and distributed could came in other PRs. But I also don't disagree with the phase 1 proposal given by @MehkaanKhan .

Yes, Median should be just one API and give the user the possibility to choose how they want it to be computed. Naively, a second argument using an enum would be a good start. I wonder if more arguments would be needed for the online case; depending on the chosen algorithms there may be further parameters to be adjusted. I would need to see a proposal first.