# Matching closest position of a sequence from another

I have 2 sequences:

• One is a videoclip with the image taken by a drone's camera
• The other is a file with a list of chronological data from the sensors

Example:

``````time 0: speed_x=1, latitude=0.001, longitude=0.2, altitude=40
time 112: speed_x=3, latitude=0.0021, longitude=0.221, altitude=30
time 232: speed_x=3, latitude=0.0021, longitude=0.221, altitude=35
time 425: speed_x=3.1, latitude=0.0024, longitude=0.222, altitude=40
…
``````

*time comes in milliseconds

I have created an application that plays the video (that's the easy part) but I want to display information about the flight at a given position of the video.

The problem is that, in order to display the sensor data at a given position of the video (at a given time), I would have to traverse the list of sensor data in order to find the sensor data that is closer to that position

For example:

If the video is showing the frame at 150 milliseconds, and in the list of sensor data I have these items in the list of the sensor data:

``````time 0:
time 90: …
time 120: …
time 200: …
time 230: …
``````

Then, I should choose to show the sensor data at the item with `time=120`, because it's the one that is closer to 150 ms.

I can do a lookup algorithm to do the lookup, but I will be really inefficient to traverse the whole list of data from the sensors calculating distances and choosing the one with the minimum distance.

So, I thought about creating some kind of dictionary/hash table that, given a position in the video, it would retrieve the appropriate sensor data.

However, I have never created suck lookup data structure. I don't even know it it's feasible! I have used dictionaries and hash tables that given a discrete key, a result is obtained. But in my case, I have a virtually infinite set of values that will result in the same item.

Can you, please, tell me how to solve this problem?

Thanks!

• This looks like it is at the complexity-level of at least a Master's Plan B [U.S.] project, if not more intricate. Oct 8, 2018 at 20:56

## 2 Answers

If you would create a hash table, you'd need to have an entry for every possible video time code.

But you can certainly use a sorted map. You need to search for the time code and if there's no exact match, take the element before.

In C++ you could for example use an `std::map`, use `lower_bound()` to get an iterator to the first element not smaller than the time code. If it doesn't correspond exactly, just decrement the iterator.

In Java, you would for example use a `TreeMap` and use `floorEnry()` to get the first element smaller or equal than the timecode you're looking for.

The lookup algorithm you are looking for is called binary search, which is quite efficient.

Note when playing the video you will typically have to check the time index of the next frame repeatedly, in increasing order. So once you have done an initial lookup, finding an index `i` in your sensor data list for a time index `t`, the next lookup for `t+t0` (where `t0` is the time interval between two frames) can be efficiently done by subsequently checking data records `i`, `i+1`, `i+2`, ... , and take the nearest one (stopping when the time distance from `t+t0` starts to increase). Assumed the time intervals between records in your sensor data list is not much smaller than `t0`, this search will end after one or two steps (if the interval is guaranteed to be bigger than `t0`, one can stop the search at `i+1`).

If you expect random positioning in your video (and so the need for random lookup in your data records) to happen seldom, and playing forward as the standard use case, it may turn out you don't even need the binary search. Don't optimize something if you don't need to.