# Finding a subarray of time series data in which all values are less than X for specified time Y?

The idea is to find an anomalous value (i.e. it's less than X) in time series data (sorted by time), and check if this behavior continues during specified time (Y=2 hours).

If all values in sub-array (which represents 2 hours period) are X, the subarray is returned as a result, and we do not continue further.

Else search continues until such sub-array is found or we have no more data.

Is there an algorithm or family of algorithms that are suited for this task?

Example:

X = 10

Y = 2 hours

Data:

(time=00:00, value=4)

(time=01:00, value=4)

(time=02:00, value=11)

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

Result:

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

...during these 2 hours all values were consistently than X=4.

On the other hand, 00:00 - 02:00 range has X=11 at the end, so it isn't included in result.

Update:

There are approx. 1440 data points in the array (1 point per minute x 24 hours).

This shouldn't be a streaming algorithm, all needed data points are already available.

Data points are immutable, values (or time) don't change.

It's important that we use as little memory during the search as possible.

Search is run once a day, so the data is different and does not depend on previous searches.

• How frequently are you doing this kind of search? How large is Y? How many data points are there? What kind of, and how much, preprocessing is acceptable? Does the data structure need to be updatable? We can't give a solid answer without a solid understanding of what you're trying to acheive. – Veedrac Apr 19 '17 at 0:48
• @Veedrac I've added more info about my particular use case. – fomalhaut Apr 19 '17 at 14:05
• One search a day? Even an atrociously inefficient n² algorithm should take a few ms at most with so few data points. It's not clear why you're asking for help here. – Veedrac Apr 19 '17 at 14:49
• @Veedrac Sorry, I should've clarified there can be on average 3000 such arrays. So 1440 * 3000 = 4320000 data points. But obviously we need to run the algo on each array independently. – fomalhaut Apr 19 '17 at 14:59
• D.W.'s approach should more than suffice in that case. – Veedrac Apr 19 '17 at 15:02

## 1 Answer

You don't need a clever or sophisticated algorithm. It suffices to linearly scan through the time series, in chronological order, and keep track of the length of window of values less than $X$.

At time $t$, remember the length of the longest window ending at time $t$ such that all values in the window are less than $X$. At time $t+1$, when you see the next value, update this length (it either increases by 1, if the new value is less than $X$, or resets to 0, if the new value is at least $X$). Keep track of the longest such window that you saw during the entire scan. If it is longer than $Y$, output it.

This requires very little memory (only an integer to keep track of the length of the window of consecutive values $< X$, and an integer to keep track of the current position in the array). The algorithm should be extremely fast.