My Favorite Algorithm: Linear Time Median Finding

Re:My Favorite Algorithm: Linear Time Median Finding by cosmic_quanta on Thursday July 25, 2024 @07:28AM (#41067292)

That is cool if you can tolerate approximations. But the uncomfortable questions soon arise: Can I tolerate an approximate calculation? What assumptions about my data do I to determine an error bound? How to verify the validity of my assumptions on an ongoing basis?

Personally I would gravitate towards the quickselect algorithm described in the OP until I was forced to consider a streaming median approximation method.

[ Parent | on HN ]

Re:My Favorite Algorithm: Linear Time Median Finding by conradludgate on Thursday July 25, 2024 @07:45AM (#41067439)

Well, I believe you could use the streaming algorithms to pick the likely median, so help choose the pivot for the real quickselect. quickselect can be done inplace too which is O(1) memory if you can afford to rearrange the data.

[ Parent | on HN ]

Re:My Favorite Algorithm: Linear Time Median Finding by SkiFire13 on Thursday July 25, 2024 @10:27AM (#41069069)

Then you don't get a guaranteed O(n) complexity if the approximated algorithm happen to make bad choices

[ Parent | on HN ]

Re:My Favorite Algorithm: Linear Time Median Finding by mgaunard on Thursday July 25, 2024 @03:06PM (#41072215)

say you want the median value since the beginning of the day for a time series that has 1000 entries per second, that's potentially hundreds of gigabytes in RAM, or just a few variables if you use a p-square estimator.

[ Parent | on HN ]

Re:My Favorite Algorithm: Linear Time Median Finding by skrtskrt on Thursday July 25, 2024 @11:25AM (#41069778)

A use case for something like this, and not just for medians, is where you have a querying/investigation UI like Grafana or Datadog or whatever.

You write the query and the UI knows you're querying metric xyz_inflight_requests, it runs a preflight check to get the cardinality of that metric, and gives you a prompt: "xyz_inflight_requests is a high-cardinality metric, this query may take some time - consider using estimated_median instead of median".

[ Parent | on HN ]

Re:My Favorite Algorithm: Linear Time Median Finding by mgaunard on Thursday July 25, 2024 @03:03PM (#41072184)

any approximation gives a bound on the error.

[ Parent | on HN ]