My Favorite Algorithm: Linear Time Median Finding (2018)

Post by rented_mule » Fri, Jul 26, 2024, 1:24 AM UTC

ant6n wrote: post #113

rented_mule wrote: post #102

10-15 years ago, I found myself needing to regularly find the median of many billions of values, each parsed out of a multi-kilobyte log entry. MapReduce was what we were using for processing large amounts of data at the time. With MapReduce over that much data, you don't just want linear time, but ideally single pass, distributed across machines. Subsequent passes over much smaller amounts of data are fine. It was a…

I’m not sure why you use a dictionary with keys 0…999, instead of an array indexed 0…999.

Post by sevensor » Fri, Jul 26, 2024, 2:01 AM UTC

throwaway_2494 wrote: post #95

fanf2 wrote: post #40

Earlier quoted context omitted.

There 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/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-h…

See also the Greenwald Khanna quantile estimator, an online algorithm which can compute any quantile within a given ϵ. https://aakinshin.net/posts/greenwald-khanna-quantile-estima...

Post by sevensor » Fri, Jul 26, 2024, 2:27 AM UTC

ssfrr wrote: post #99

sevensor wrote: post #20

Earlier quoted context omitted.

I’ve definitely had situations where a streaming quantile algorithm would have been useful, do you have any references?

Here's a simple one I've used before. It's a variation on FAME (Fast Algorithm for Median Estimation) [1]. You keep an estimate for the current quantile value, and then for each element in your stream, you either increment (if the element is greater than your estimate) or decrement (if the element is less than your estimate) by fixed "up -step" and "down-step" amounts. If your increment and decrement steps are equal,…

Post by fasa99 » Fri, Jul 26, 2024, 2:57 AM UTC

xinok wrote: post #58

> P.S: In 2017 a new paper came out that actually makes the median-of-medians approach competitive with other selection algorithms. Thanks to the paper’s author, Andrei Alexandrescu for bringing it to my attention! He also gave a talk about his algorithm in 2016. He's an entertaining presenter, I highly recommended! There's Treasure Everywhere - Andrei Alexandrescu https://www.youtube.com/watch?v=fd1_Miy1Clg

Post by laweijfmvo » Fri, Jul 26, 2024, 3:28 AM UTC

fenomas wrote: post #85

someplaceguy wrote: post #75

Earlier quoted context omitted.

> The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Except that there is no such thing as "arbitrarily large storage", as my link in the parent comment explained: https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ So why would you want to talk about arbitrarily large input (where the input is an array that is stored in mem…

Big-O analysis is about scaling behavior - its real-world implications lie in what it tells you about relative sizes, not absolute sizes. E.g., if you need to run a task on 10M inputs, then knowing that your algorithm is O(N) doesn't tell you anything at all about how long your task will take. It also doesn't tell you whether that algorithm will be faster than some other algorithm that's O(N^2). But it does tell you…