0
$\begingroup$

The algorithm should analyze measured time series data in realtime and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over the specified time period.

Input data

t        | 10:00 | 10:01 | 10:02 | 10:03 | ... | 19:00 |
Temp [°C]| 40    | 41.3  | 39    | 43    |     | 45    |

Algorithm parameters

  1. Duration D: Past time to check for min/max
  2. Max range R: (max-min) < R

e.g: Check if the temperature was steady within 2 °C for the last hour. D=1hour, R=2°C

The algorithm should check periodically during data acquisition if the condition (all values of the last hour have been inside a range of 2°C) is true.

Other requirements

  • The sampling time can be from 10Hz to 50kHz.
  • The time will always be increasing.
  • Since this algorithm should run in an realtime environment there should be no memory allocations during run time

Possible solutions

At the moment I have two possible solutions but do not like both of them:

  1. Store all values within the duration in a bounded fifo-buffer and perform a min/max check from start to end periodically. I expect this to be the worst solution

  2. Store the tuples in two B-Trees:

    There are two indexes

    1. TimeIndex t->(t,v): Index from time to tuple,
    2. ValueIndex v->list(t,v): Index from the value to a list of tuples with this value.

    The algorithm will first get all tuples that are outside the time range and remove them in the value index.

    Then the value index is updated with the newly measured tuples.

    The range can then be determined by looking up the minimum and maximum key in the value index.

I think the second approach is faster but will allocate memory during runtime. Since it should run in a realtime environment I like to avoid allocations.

Is there another possibility with O(log n) and no allocations?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You need to provide some more details. Is the time series data always the same, that is, do we get to preprocess it after which we'll answer a bunch of queries with different durations? Or do we need to support adding new data points, and if so, how does that avoid allocation to begin with (is there a maximum size?). Do we also need to remove data points? Hint: think in terms of data structures, not algorithms. $\endgroup$
    – orlp
    Commented Jul 1, 2019 at 10:15
  • $\begingroup$ @orlp: Thanks for trying to understand my problem. I updated the text and tried to be clearer with my wording. I would appreciate if you could check again. $\endgroup$
    – schoetbi
    Commented Jul 1, 2019 at 13:12
  • 1
    $\begingroup$ Is the sampling time always constant? That is, if you know the duration you need to check could you also just equivalently check the last duration*freq samples? Similarly, are $D$ and $R$ constants? $\endgroup$
    – orlp
    Commented Jul 1, 2019 at 13:25
  • $\begingroup$ @orlp: The sampling frequency does not change. And D and R are constant. $\endgroup$
    – schoetbi
    Commented Jul 2, 2019 at 9:37

1 Answer 1

Reset to default
2
$\begingroup$

The following paper provides a O(1) algorithm:

D. Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element, Nordic Journal of Computing, 13 (4), 2006 (https://arxiv.org/abs/cs/0610046).

An implementation of this algorithm is provided in the GNU Scientific Library (see https://www.gnu.org/software/gsl/doc/html/movstat.html).

Improve this answer
$\endgroup$
3
  • $\begingroup$ The algorithm is beautiful. I even found a LGPL licenced code: github.com/lemire/runningmaxmin $\endgroup$
    – schoetbi
    Commented Jul 2, 2019 at 9:43
  • $\begingroup$ While this algorithm certainly is beautiful it is only amortized $O(1)$. In the worst case it can lead to $O(w)$ operations for a single update where $w$ is the window width. Something to keep in mind for a real-time algorithm @schoetbi. I do believe that you can reduce it to $O(\log w)$ by doing a binary search on the $U$ and $L$ queues to find how many you need to pop. $\endgroup$
    – orlp
    Commented Jul 2, 2019 at 10:45
  • $\begingroup$ @orlp: Thanks for this hint. We have mostly noisy signals. So a sequence of monotonic values will be very unlikely. But I will implement binary search in the wedge. $\endgroup$
    – schoetbi
    Commented Jul 2, 2019 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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