0

Caveat: I'm conscious that this question may not be a great fit for stack-exchange platform as maybe 'too broad' but will try & structure it that it helps people in the future

I have 2 event steams that represent GPS & Heart Rate sensors over a period of time. Both sensors are non deterministic is when they raise events as & when the sensor can - i would like an efficient means to 'marry' the 2 sets of data with O(1) efficiency.

i.e. the closest heart rate is within 2000MS (-/+) of the GPS event then they are a match.

So the question is; what data structure/algorithm would you use to achieve such as a use case?

  • 2
    No point worrying about using the "right" method when your requirements are trivial. Just subscribe to both streams and emit a joint event whenever the latest inputs from both streams are close in time. – Kilian Foth May 10 at 8:07
  • @KilianFoth That assumes that the streams are being read in 'real time', right? I don't know that you can assume that. It's an error to conflate the time an event occurred with the time that you process it. – JimmyJames May 10 at 19:12
1

You have to define all the constraints in your data. For example:

  • Sample Rate: how often samples are obtained
  • Variance: how much uncertainty there is in the sample (in time and magnitude)
  • Threshold: consider how much time passes before you declare the data stream dead. Also consider your minimum and maximum values.

Once you've defined that information, understand how sampling works:

  • That value remains constant until the next sample is retrieved

Putting it together

Givens:

  • GPS sample rate: 1 location every 10 seconds, GPS point is +/- 20m of your actual location (which dissapointingly is a pretty good error bound)
  • BPM sample rate: 1 average heart rate every 6 seconds, heart rate is +/- 5 BPM of actual heart rate

You receive data:

0:0:06 118 BPM
0:0:10 34.12345, -77.54321, 100m
0:0:12 119 BPM
0:0:18 117 BPM
0:0:20 34.12354, -77.54312, 99m
...

In your application you can see that by the time we get the first GPS point, the BPM is 118, and when we get the second GPS point the BPM is 117.

You know that because the last sample point was within the normal sample rate so you can simply use that value.

Now, you need to define when the data stream is officially dead. If your last BPM is 40 seconds ago, you probably can't trust that value.

1

I think what you are looking for here is the basic approach to processing the streams and finding the points that are co-located in time. I'm going to assume you want to do this on a stream of values. If you have this in a relational DB there are ways to do it that are relatively simple to write but probably won't perform well.

Here's the basic approach:

Read the first value from each stream to initialize.

  1. Compare the values. If they are close, emit the pair
  2. Advance to the next value of the stream whose last read value was earliest
  3. Repeat

The main potential complication is that you might find more than value from one of the streams within the range of tolerance of the current value of the other stream. If that's not desirable, you need to either ignore the additional values or find another approach to dealing with that such as averaging.

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.