5 ms·
You could also use one of the streaming algorithms which allow you to compute approximations for arbitrary quantiles without ever needing to store the whole dat
by mgaunard 2y ago
You could also use one of the streaming algorithms which allow you to compute approximations for arbitrary quantiles without ever needing to store the whole data in memory.
- cosmic_quanta 2y agoThat 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.
- conradludgate 2y agoWell, 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.
- SkiFire13 2y agoThen you don't get a guaranteed O(n) complexity if the approximated algorithm happen to make bad choices
- mgaunard 2y agosay 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.
- skrtskrt 2y agoA 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".
- mgaunard 2y agoany approximation gives a bound on the error.
- sevensor 2y agoI’ve definitely had situations where a streaming quantile algorithm would have been useful, do you have any references?
- fzy95 2y ago"Further analysis of the remedian algorithm" https://www.sciencedirect.com/science/article/pii/S0304397513004519 https://www.sciencedirect.com/science/article/pii/S030439751... This one has a streaming variant.
- sevensor 2y agoThanks!!
- fanf2 2y agoThere are two kinds: - quantile sketches, such as t-digest, which aim to control the quantile error or rank error. Apache DataSketches has several examples, https://datasketches.apache.org/docs/Quantiles/QuantilesOverview.html https://datasketches.apache.org/docs/Quantiles/QuantilesOver... - histograms, such as my hg64, or hdr histograms, or ddsketch. These control the value error, and are generally easier to understand and faster than quantile sketches. https://dotat.at/@/2022-10-12-histogram.html https://dotat.at/@/2022-10-12-histogram.html
- throwaway_2494 2y agoSee also the Greenwald Khanna quantile estimator, an online algorithm which can compute any quantile within a given ϵ. https://aakinshin.net/posts/greenwald-khanna-quantile-estimator/ https://aakinshin.net/posts/greenwald-khanna-quantile-estima...
- sevensor 2y agoI am so glad I asked. This is a wheel I’ve been reinventing in my head for eighteen years now. I’ve even asked in other venues, why are there no online median algorithms? Nobody knew of even one. Turns out, I was asking the wrong people!