Recently I had to implement a median filter algorithm, I found Redis very powerful to accomplish this! A very simple solution and scalable.
As described in Wikipedia, Median filter works in this way: given a signal, output sample is the median of last N input samples, where N can be any positive integer number. Higher is N, more aggressive will be your filter.
We need a store for last samples, in a FIFO way, pushing a new one will drop an older one. Redis provides lists, which are perfect for this scope. Also we need to sort these samples in numerical order, to get every time we want the median value. Redis provides a SORT command, which does this job.
I implemented these two primitives:
add_sample(value)- called every time to add a new sample
get_median()- to get the median value
For the former we need to call two Redis commands:
MULTI LPUSH <yourkey> <value> LTRIM 0 <N>-1 EXEC
LPUSH will simply add a new sample to the list,
LTRIM ensures that at least
N elements will be stored, no more.
To get median value we need to call
SORT and then calculate median. SORT returns
all values on that list, sorted by numerical order. I have preferred
to use a script, so Redis avoids returning non useful data to clients:
local list_key = KEYS -- Key of samples list -- Sort values local sorted_values = redis.call("SORT", list_key) local size = #sorted_values local median = 0.0 -- Calculate median if size % 2 == 0 then median = (sorted_values[size/2]+sorted_values[size/2+1]) / 2 else median = sorted_values[(size+1)/2] end -- Use tostring because median value may be floating point return tostring(median)
Calling this script it’s easy:
EVAL <script> 1 <yourkey>
Copyright © 2014-2021 Luca Marturana. License.