What are some of the applications of Order Statistics Algorithms?

Question

I am watching the MIT lectures and Eric Demaine says that they discussed some of the applications of Order Statistics Algorithms. I was wondering if the SO community would help me figure out some of the applications of the selection algorithms.

Answer 1

Finding the median is a common application of such algorithm. E.g. I've used it in image processing for the median filter. Min, max, k-NN also use order statistic algorithms, so that's another application.

Answer 2

Here are some other applications that I can think of in addition to what Jacob said:

Most of the services care about 95-th or 99-th percentile of latency rather than mean 'coz they want to keep most of the users happy.

In machine-learning if you want to convert a continuous valued feature into Boolean features by bucketing it, one common approach is to partition it by percentile so that the cardinality of each Boolean feature is somewhat similar.

There are probably hundreds of applications of order statistics. The algorithms to compute them can change based on what kind of scaling you need and what approximations you can tolerate. If you can give more context on what Eric Demaine says, probably you can get better answers.