I have a list of steadily growing values like 19:57(12.259), 19:58(13.101) stored in mongodb. Now I want to find out if the value grew 50% within 30 minutes within the last 3 hours.

My first naive approach was to take the value from 3 hours ago (a) and then look for the point in time when the value is greater than or equal (a*1.5). Then - in a post check - I test if this increase happened within 30 minutes.

This does work if the post condition is fulfilled but fails if it doesn't and there would be another, better candidate. In this case I would need to go on looking but there has to be a better way.

Basically I think, I am looking for a way to find a certain steepness on a curve.

  • 1
    "Steepness of a curve" is called "slope." That's not quite enough to solve your particular problem, though. – Robert Harvey Sep 12 '17 at 22:19
  • 1
    I can think of a naive O(n²) solution, where n is the number of data points that span a 30 minute window. Would that be sufficient? You start at k, check the points to y (where k and y are your 30 minute window, starting at k=0), to see if any of them exceed i[k] * 1.5. Then, increment k and y, and do it again until k equals the end. – Robert Harvey Sep 12 '17 at 22:25
  • That would be my solution as well but with a resolution of 1 minute this is 180 potential results and this has to be checked for 190 individual time series. I can pull them all out of the database but I was hoping for some smart mathematical algorithm to apply then. – DanielKhan Sep 12 '17 at 23:30
  • 2
    Do you need to find a place where it increases exactly 50% or is more acceptable? And by within, do you mean that increase must be over the time of exactly 30 minutes, or are shorter intervals acceptable? – Sebastian Redl Sep 13 '17 at 8:16
  • 1
    The growth is measured from any point in time within a timeframe and it's never negative. It's max 30 minutes and 50% or more (>= a * 1.5) – DanielKhan Sep 13 '17 at 9:12

I don't really understand why your solution doesn't work, logically it should. However, another option is to go back 3 hours and systematically compare the original point (a) to the point 30 minutes afterwards (b) to see if b >= a * 1.5, starting with the points 17:00 (or whatever 3 hours ago is) and 17:30. Then compare 17:01 and 17:31 and so on.

Unless perhaps your numbers have a chance to decrease (sounds like they don't).

  • 1
    This. Further I'd start by reading the first 30 minutes of data into memory. Then as each newer value is read it's added to the front of the queue, the oldest value is dropped off, and the oldest and newest are compared. This way each value is read once only, swapping RAM for IO. Better still, at startup read the most recent 30 minutes into RAM. As a new value arrives add it to the queue, drop the oldest and compare. The "+50%" notification can be sent synchronously with the data ingestion. – Michael Green Sep 19 '17 at 4:41

So based on the fact that it can't never decrease, we know that if a value didn't rise 50% in an hour, it didn't rise 50% in any 30 minute interval in that hour. Likewise for 2 hours or 3 hours.

I would probably go about it in something like this, at least to start: Divide the intervals into 6 30-minute segments across the 3 hours. Compare the value at the beginning of the 3rd with the beginning of the 1st. Then the 4th with 2nd, ... 6th with the 4th. If any of these hour segments show growth of 50% or more, you can then check every 30 minute interval in that hour. There are 30 of them if you are assuming a 1 minute resolution. Collect all those that contain the requisite growth and remove duplicates.

The problem is a little poorly defined, however. Let's say there's a 25 minute period where growth was 50%. There are 10 different 30 minute periods containing that same 25 minutes but all of them are represent the same period of growth.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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