ANN: MaxMinFilters.jl - fast streaming maximum / minimum within moving window

[sairus7]

I think, when writing some new functions, it is easier to start with 1-dimensional case for simplicity, then debug it, and then it can be rewritten to multi-dimensional case, if applicable. And if there are some notable performance differences OR extra code complexity, we can leave both implementations.

It’s nice to have one implementation for 2 and more dimensions. But combining 1 and many has some extra burden, e.g. in DataStructures we have 1-dimensional CircularDeque, and there is no need to rewrite it for multidimensional deque with pushes along selected dims. If we really need that, it can be just added in separate source file.

[Jakub_Wronowski]

Hi, recently there were thread started by @Kruxigt and I realised, that I need this functionality

@juliohm

Indeed, it would be nice to see a generalization of all these efforts into a single even more powerful package.

As I will need those moving max/min for a quantitative algorithms I am working now, I can spend some time on such consolidation or improving something in existing ones, cause I want to avoid creating one more package with this functionality.

@tkf

Just FYI, you may be interested in transducers instead of stateful functions, e.g., if you want to squeeze out performance

This is what I am going to do, using transducers will allow operations on infinite streams.

@tim.holy

The algorithm in MaxMinFilters is the same one implemented in ImageFiltering; it just turned out the one in ImageFiltering had been optimized for small window sizes. A small tweak fixed the performance for large windows, so that now its performance is similar to MaxMinFilters.

@tim.holy, unfortunately my benchmarks are not reflecting that. Am I doing something wrong?

EDIT: now I see that it uses fast algorithm for extrema, but not minimum or maximum

julia> @btime ImageFiltering.mapwindow($maximum, $x, $1001);
  1.010 s (11021 allocations: 17.82 MiB)

julia> @btime movmax($x, $1001);
  9.996 ms (3 allocations: 7.64 MiB)

julia> length(x)
1000000

[sairus7]

What functionality are you talking about?
There are different sets of possible functionality extensions:

1. Steteless functions (to process small data chunks at once) => stateful functions for (realtime or larger than memory) data streams, that can be stopped and resumed later, so function state can be saved and loaded. This is also related to delays and boundary conditions handling.

2. Special function types:

   2.1. Moving window functions => moving window with decimation, if window step > 1 (or “jumping” window)
   2.2. Special filters, like sorting filter for fast moving median and moving percentiles, etc.
   2.3. Regularly sampled data => irregularly sampled data, constant window length => variable window length.
   2.4. Event detectors: local maxima peak detectors, zero-crossing and threshold detectors, step detectors and so on. Also related to data formats for irregularly sampled events.

3. Functions for 1-dimensional signals => multi-diomensional signals, like video streams.

4. Composing chains of processing steps, like: “filter1 > decimate > sliding function > detect events > calc features > …” and so on. It is related to using transducers to feed data, or making functions and data buffers compatible for possible use with transducers. You may be interested in this thread:
   Using Transducers.jl instead of stateful functions for stream processing
   Speaking of transducers, I just don’t fully understand, how to use them for complex processing chains, if you need branching and joining data streams, select to store some intermediate data, log intermediate data for debug purpose, and so on.

All that extensions are partly compatible with each other, but not all.

Also, I think we should start with as simple use cases as possible.

[Jakub_Wronowski]

Nice summary, I can see you were working a lot on this algorithm.

@sairus7

Steteless functions (to process small data chunks at once) => stateful functions for (realtime or larger than memory) data streams, that can be stopped and resumed later, so function state can be saved and loaded. This is also related to delays and boundary conditions handling.

This is the most interesting for me - processing of very large or infinite streams from databases or other “larger than memory” sources. I don’t think stopping and resuming is crucial but probably you have more insight in this concept than me, so maybe just I cannot imagine a use case. There are coroutines, tasks and threading (see ThreadPools.jl), so they can handle interrupts in the data delivery quite nice.

@sairus7

Special function types:

Those functionalities sounds complicated, I am not sure the O(N) algorithm will handle them.

@sairus7

Functions for 1-dimensional signals => multi-diomensional signals, like video streams.

I guess we neeed an array of Deques to handle that. Probably it would be useful somewhere but I have only 1D cases to handle.

@sairus7

Speaking of transducers, I just don’t fully understand, how to use them for complex processing chains, if you need branching and joining data streams, select to store some intermediate data, log intermediate data for debug purpose, and so on.

I don’t think they can handle that. Branching streams is not easy. If we have an iterator to database query stream it would be problematic to iterate it in 2 places with different cadence. The solution would be to open 2 independent connections and process them separately, eventually we can join those 2 processed streams later.

@sairus7

Also, I think we should start with as simple use cases as possible.

So for me simplest use case is to make this fast extrema algorithm work for any iterable things, not only AbstractArrays. I’ll try to prototype it soon, the discussion you linked is helpful. I did it long time ago in C# so this is feasible.

[LostInMusic]

When I looked for an efficient moving/rolling/running median in Julia this was one of the first threads I found, but none of the mentioned packages could do a running median that was fast enough for my application.
So I took matters into my own hands and created one:

https://github.com/Firionus/FastRunningMedian.jl

For window sizes above roughly 10 it is faster than sairus7’s https://github.com/sairus7/SortFilters.jl which can do arbitrary probability levels though. See the README.md for Benchmarks.