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?
$\begingroup$
$\endgroup$
5
-
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$– hoffmaleCommented Oct 2, 2017 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$– gnasher729Commented Oct 2, 2017 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$– hoffmaleCommented Oct 2, 2017 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$– WildcardCommented Oct 3, 2017 at 0:05
-
$\begingroup$ @gnasher729 Since the topic is stochastic algorithms, this (= reasonably close) is probably precisely what these algorithms are doing. $\endgroup$– Konrad RudolphCommented Oct 3, 2017 at 14:51
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
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.
answered Oct 1, 2017 at 22:16
-
$\begingroup$ Thank you! That is extremely helpful! Any other algorithms or techniques that may need to find a median? $\endgroup$– SDGCommented Oct 1, 2017 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$ Commented Oct 2, 2017 at 2:05
-
1$\begingroup$ Interesting. I have heard about $k$-means clustering, but not about $k$-medians clustering. $\endgroup$– svickCommented Oct 2, 2017 at 15:43
$\begingroup$
$\endgroup$
4
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.
-
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$– DunkCommented Oct 2, 2017 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$ Commented Oct 2, 2017 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$ Commented Oct 3, 2017 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$ Commented Oct 3, 2017 at 15:15
$\begingroup$
$\endgroup$
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.
answered Oct 2, 2017 at 8:13
$\begingroup$
$\endgroup$
3
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)$.
-
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$– wcharginCommented Oct 2, 2017 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$ Commented Oct 3, 2017 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$ Commented Oct 3, 2017 at 15:03