Similarity between line strings

Question

I have a number of tracks recorded by a GPS, which more formally can be described as a number of line strings.

Now, some of the recorded tracks might be recordings of the same route, but because of inaccurasies in the GPS system, the fact that the recordings were made on separate occasions and that they might have been recorded travelling at different speeds, they won't match up perfectly, but still look close enough when viewed on a map by a human to determine that it's actually the same route that has been recorded.

I want to find an algorithm that calculates the similarity between two line strings. I have come up with some home grown methods to do this, but would like to know if this is a problem that's already has good algorithms to solve it.

How would you calculate the similarity, given that similar means represents the same path on a map?

Edit: For those unsure of what I'm talking about, please look at this link for a definition of what a line string is: http://msdn.microsoft.com/en-us/library/bb895372.aspx - I'm not asking about character strings.

Answer 1

Compute the Fréchet distance on each pair of tracks. The distance can be used to gauge the similarity of your tracks.

Math alert: Fréchet was a pioneer in the field of metric space which is relevant to your problem.

Answer 2

I would add a buffer around the first line based on the estimated probable error, and then determine if the second line fits entirely within the buffer.