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

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

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

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.

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.

@vepadulano

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.

@vepadulano

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.

@MehkaanKhan

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.

@MehkaanKhan

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.

For the online case, I'd suggest t-digest.
My reasons - the algorithm must be mergeable. In the design of action helper class in the ActionHelpers file are such that per-slot states merge in Finalise and per process states merge in RMergeableValue, this rules out the p-squared option.

T-digest keeps a set of centroids, each having a (mean, weight) representing a cluster of nearby values. The growth of each centroid is dictated by a scale function, centroids are small at the tails and larger in the middle (50th percentile), the delta parameter controls how many centroids can exist in the t-digest. Larger the delta parameter, more centroids, more accuracy (trading memory for accuracy).

Reasons for choosing t-digest over KLL sketch - T-digest is deterministic unlike KLL sketch that uses a random number generator (RNG). T-digest also has a predictable memory footprint (delta parameter), this allows users to more precisely balance memory usage and accuracy.

Regarding the extra argument for the user - delta can be used to tweak the memory vs accuracy trade off. By default the Median() call can be defaulted to the exact algorithm, I agree with your idea of using an enum to select the median algorithm (exact or online). The delta value can be defaulted as well. Something like this -

df.Median("col");                                 // exact
df.Median("col", MedianMode::approx);           // online, default delta
df.Median("col", MedianMode::approx, delta);    // online, user defined delta

Let me know your thoughts on this and anything else I need to know before I start writing the code for this PR.

After a bit of thinking, I realised that t-digest is deterministic for fixed inputs, but for a variable input order, the values are grouped differently into centroids due to the slot partitioning design which might slightly change the result for each order.

Is this acceptable or is reproducibility a hard requirement?

@ArjunXvarma

Dear @ArjunXvarma ,

Thanks for your research and thoughts. As the original request is "just" to have a way to compute the Median value of a colum using RDataFrame, in first approximation we could introduce the feature only in its exact mode. This would incur in a potentially large memory cost, but avoids producing confusing results. Perhaps if another set of users who need the online algo for the Median arises we could reassess and think about introducing that feature addition later on. For now I would only go with the exact Median.

Understood. Here is my proposal on implementing the algorithm -

The MedianHelper class can be implemented similarly to the MeanHelper class. The only required changes are -

A vector<vector<double>> fBuffers member holding per-slot values and shared_ptr<double> fResult holding the final result.
Exec (plus the IsDataContainer overload for collection columns) appending into the calling slot's buffer.
Finalize merging the per-slot buffers and running nth_element, averaging the two middle values for even counts.
GetActionName() returning "Median".
GetResultPtr() returns fResult as a shared pointer.

I have a working median action helper class that can be used from the C++/Python interface. Happy to proceed if the design works.

@ArjunXvarma

Thanks to @ArjunXvarma RDataFrame now has a Median operation for local execution, through #23079 🎉

We are still missing Median support in distributed mode, but for now the issue can be closed as it satisfies the original user request at https://root-forum.cern.ch/t/calculating-median-with-rdataframe/64941

Navigation Menu

Repository navigation

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

Feature description

Alternatives considered

Additional context

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Feature description

Alternatives considered

Additional context

Activity

ferdymercury commented on Jul 13, 2026

vepadulano commented on Jul 14, 2026

vepadulano commented on Jul 14, 2026

ArjunXvarma commented on Jul 15, 2026

MehkaanKhan commented on Jul 16, 2026

ArjunXvarma commented on Jul 16, 2026

vepadulano commented on Jul 21, 2026

ArjunXvarma commented on Aug 5, 2026

ArjunXvarma commented on Aug 5, 2026

vepadulano commented on Aug 6, 2026

ArjunXvarma commented on Aug 7, 2026

vepadulano commented on Sep 11, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions