Find best matching route from many routes

user_503694 0
Viewed 35

I have a dataset of historical routes (lists of lat/lon points) from AIS data. I now have a test route (8 lat/lon points) and I want to find the 10 closest routes in the historical database. How can I do this efficiently?

I could loop through all the routes in the historical dataset, and for each candidate route calculate the best match for the test to that candidate. Best match would be calculated by pairing the first point of the test route to the candidate route and sum distances for the next 7 point, then pairing the first point of the test route to the second point of the candidate and sum, and continue. This is horribly inefficient, and I have 100,000 historical routes to go through.

So, I am thinking about some sort of spatial indexing or binning approach, so I do not have to consider most of the data. Many of the historical route are long though, and go through large areas, so can't really make independent sections.

Is there a known algorithm that solves this?

numpy algorithm python
1 Answers

Indeed. Consider some safe estimate on how far the starting point of test route can be from the corresponding point of a historical route. Make a grid, and put all route points into grid cells. Then, when searching for the first corresponding point, you have to check only the grid cells which are reasonably close to the start.

Additionally, when the sum of distances for the first few points is already larger than the best sum you found so far, you can skip the candidate altogether, and proceed immediately with the next one.

These notions are not an algorithm, just some heuristics to narrow the search.

user_14887990
Related