6_RA

header

6_RA assignament

Request

Do a web research about the various methods proposed to compute the running median (one pass, online algorithms). Store (cite all sources and attributions) the algorithm(s) that you think is(are) a good candidate, explaining briefly how it works and possibly try a quick demo.

Compute it with one pass

the median is the value that is at the center of the distribution and biscet it,for computing it we can use a simple algo: Starting from a ordered distribution (cardinality n) whe could say that:

how to calculate it with an oline algo

we can approssimate the median with the formula: [1] Me= Xi+(Xi+1 -Xi)=(0,5 -Fi)/(Fi+1-Fi) where Fi are the acutual comulative frequency and calculate it online with this

Efficient Algorithm for computing a Running Median

From -LIGO- LASER INTERFEROMETER GRAVITATIONAL WAVE OBSERVATORY[2]

Inputs to the code: • X : the sequence x[k], k = 0, . . . , N − 1. • M : The number of points per block. Output of the code: • Y : sequence y[k], k = 0, . . . , N − M.

Several special cases may arise such as x[j] smaller or larger than any of the sample from the previous block. A lot of the code is devoted to handling such special cases. However, for the sake of clarity, these special cases are not shown in the outline above. Interested readers must consult the documentation of the C code (c.f., Appendix B) to understand how these special cases are handled

Median algo

[1]“url”,“https://dcc-backup.ligo.org/public/0027/T030168/000/T030168-00.pdf" [2]“url”,“https://it.wikipedia.org/wiki/Mediana_(statistica)#Definizione_e_calcolo"