15
$\begingroup$

I have been reading this book for my class, Randomized Algorithms. In this particular book, there is a whole section dedicated to finding the median of an array using random selection, that leads to a more efficient algorithm. Now, I wanted to know if there are any practical applications of this algorithm, in the domain of computer science, besides a theoretical improvement. Are there any algorithms or data structures that need to find the median of an array?

$\endgroup$
  • 3
    $\begingroup$ You might want to take a look at quicksort: By choosing the median as the pivot, its worst case can be avoided (worst case runtime = O(n log n) instead of O(n^2)) and the recursion depth will be minimized (log2(n)). $\endgroup$ – hoffmale Oct 2 '17 at 1:30
  • 1
    $\begingroup$ @hoffmale: But that doesn't require you to find the median. It requires you to find a value that is reasonably close to the median. For example, finding a pivot that is not within the top 5% or bottom 5% guarantees O (n log n). $\endgroup$ – gnasher729 Oct 2 '17 at 18:07
  • 1
    $\begingroup$ @gnasher729: but that won't minimize the recursion depth. Both properties are important, e.g. in a resource-limited real-time environment. $\endgroup$ – hoffmale Oct 2 '17 at 19:36
  • $\begingroup$ @hoffmale, incidentally, the usual notation for base 2 logarithm (particularly among computer scientists) is simply "lg" as in (lg(n)). $\endgroup$ – Wildcard Oct 3 '17 at 0:05
  • $\begingroup$ @gnasher729 Since the topic is stochastic algorithms, this (= reasonably close) is probably precisely what these algorithms are doing. $\endgroup$ – Konrad Rudolph Oct 3 '17 at 14:51
19
$\begingroup$

if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement

The application of this algorithm is trivial - you use it whenever you want to compute a median of a set of data (array in other words). This data may come from different domains: astronomical observations, social science, biological data, etc.

However, it is worth mentioning when to prefer median to mean (or mode). Basically, in descriptive statistics, when our data is perfectly normal distributed then mean, mode, and median are equal, i.e. they coincide. On the other hand, when our data is skewed, i.e. the frequency distribution for our data is (left/right) skewed, the mean fails to provide the best central location because the skewness is dragging it away from the typical value to left or right, while the median is not as strongly influenced by the skewed data, and thus best retains this position pointing to a typical value. Thus computing a median might be preferable when you deal with skewed data.

Also, machine learning is where statistical methods are heavily used, for example $k$-medians clustering.

$\endgroup$
  • $\begingroup$ Thank you! That is extremely helpful! Any other algorithms or techniques that may need to find a median? $\endgroup$ – Sharan Duggirala Oct 1 '17 at 23:32
  • 5
    $\begingroup$ While this is true enough (+1), more often than not in applied statistics the data would be sorted prior to finding the median, since in many or even most contexts where the median is desired, so are at least some of the other order statistics. $\endgroup$ – John Coleman Oct 2 '17 at 2:05
  • 1
    $\begingroup$ Interesting. I have heard about $k$-means clustering, but not about $k$-medians clustering. $\endgroup$ – svick Oct 2 '17 at 15:43
13
$\begingroup$

Median filtering is common in reduction of certain types of noise in image processing. Especially salt and pepper noise. It works by picking out the median value in each color channel in each local neighbourhood of the image and replacing it with it. How large these neighbourhoods are can vary. Popular filter sizes (neighbourhoods) are for example 3x3 and 5x5 pixels.

$\endgroup$
  • 1
    $\begingroup$ Median applies not just to noise in images but noise in pretty much all sensor readings, of which cameras are just one sort of sensor. School Textbooks show nice sinusoidal and square wave shapes to work with. In the real world clean data like that almost never happens. If it does, it is almost always because somebody else took care of smoothing out the data before you got hold of it. e.g. of more typical sensor reading data of which you need to pick the "correct" value: (1, 3, 5, 65, 68, 70, 75, 80, 82, 85, 540, 555). I sorted the data to make it more obvious. $\endgroup$ – Dunk Oct 2 '17 at 19:57
  • 1
    $\begingroup$ Yep you are right. But it would make a very long and boring answer if we wrote down all little things in signal processing where it can be used. $\endgroup$ – mathreadler Oct 2 '17 at 20:15
  • 1
    $\begingroup$ Medians in image processing can also be used per pixel with sequences of 5 or so photos, which is a way to get rid of temporal noise (aka. tourists blocking the view) $\endgroup$ – Hagen von Eitzen Oct 3 '17 at 11:15
  • $\begingroup$ @HagenvonEitzen You are right! Actually I was thinking of something quite similar just a few days ago. Many tourists around... $\endgroup$ – mathreadler Oct 3 '17 at 15:15
10
$\begingroup$

Computing medians is particularly important in randomized algorithms.

Quite often, we have an approximation algorithm that, with probability at least $\tfrac34$, gives an answer within a factor of $1\pm\epsilon$ of the true answer $A$. Of course, in reality, we want to get an almost-correct answer with much higher probability than $\tfrac34$. So we repeat the algorithm $k$ times and then take the median. The median will be within $A(1\pm\epsilon)$ unless at least half of the $k$ samples were less than $A(1-\epsilon)$ or at least half were bigger than $A(1+\epsilon)$, and this has probability exponentially small in $k$.

Computing medians takes our crappy "It's wrong one time in four" algorithm and turns it into an "It's wrong once in $2^n$ runs" algorithm while only adding a factor of something like $n$ to the running time.

$\endgroup$
5
$\begingroup$

The median of medians has some applications:

  • Finding a pivot for quicksort, which brings its worst-time complexity to $ O(n \log n)$.
  • Finding a pivot for quickselect, bringing it's worst-time complexity to $O(n)$, from $O(n^2)$.
$\endgroup$
  • 1
    $\begingroup$ Actually using median-of-medians to select a pivot for quicksort seems very likely to slow down the algorithm in practice, because it completely kills the cache locality, which is the main contribution to quicksort's quickness. But your comment about the worst-case complexity is of course correct. $\endgroup$ – wchargin Oct 2 '17 at 2:12
  • $\begingroup$ @wchargin What alternatives do you suggest? No practical quicksort implementation that I know of uses a cache-sensitive pivot, because doing so trades in atrocious worst-case runtime. The seminal “Engineering a sort function” paper discusses alternatives, and none of them are cache-aware (and nevertheless outperform naive pivot selection). $\endgroup$ – Konrad Rudolph Oct 3 '17 at 14:56
  • 1
    $\begingroup$ @wchargin … answering my own question: Java 7 switched to a new dual-pivot procedure that I was unaware of. This is intriguing and might render median pivot algorithms obsolete. $\endgroup$ – Konrad Rudolph Oct 3 '17 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.