# Algorithm to match timestamped events from two sources

I have two different physical devices (one is camera, one is other device) that observe the same scene and mark when a specified event occures. (record timestamp)

So they each produce a serie of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned:

Visualized ideal situation on two time lines "s" and "r" as recorded from the two devices:

but more likely they will not be so nicely aligned and there might be missing events from timeline s or r:

I am looking for algorithm to match events from "s" and "r" like this:

So that the result will be something like: (s1,null); (s2,r1); (s3,null); (s4,r2); (s5,r3); (null,r4); (s6,r5); Or something similar. Maybe with some "confidence" rating.

I have some ideas, but I feel that this might be probably a well known problem, that has some good known solutions, but I don't know the right terminology. I am a little bit out of my element here, this is not my primary area of programming.. Any helps, suggestions etc will be appreciated.

• In order to solve the problem, you will need some criteria that matches like points. Example criteria: "If time stamps are within 100 nanoseconds of each other, then they are considered the same event." – Robert Harvey May 29 '14 at 23:36

Here is my solution in C#, works good enough for my purposes:

``````///compute reasonably aligned pairs
var max_tolerable_offset = 500; //do not match more then 500 miliseconds distant timestamps

Dictionary<long, long> alignedPairs = new Dictionary<long, long>();

foreach(var s in s_timestamps)
{
//for every timestamp in first timeline find the nearest one from r
var nearest_r = r_timestamps.OrderBy(r => Math.Abs(r - s)).First();

//if that is closer than allowed offset
if ((Math.Abs(nearest_r - s)) <= max_tolerable_offset * 10000)
{
//so now I need to find nearest s mark for this r mark
var closest_s = s_timestamps.OrderBy(s=> Math.Abs(s- nearest_r )).First();

//if they are mutually in love, marry them
if (closest_s == s)