Research if we need DamerauLevenshteinAlgorithm to find similar routes

[abhishek1508]

No description provided.

[1ec5]

Currently, calculating an edit distance over the route summary (such as using the Damerau–Levenshtein algorithm) is the only way we have to efficiently determine similarity between two routes. The iOS navigation SDK calculates similarity to persist the user’s chosen route after a reroute. The edit distance approach is not only more efficient but also more reliable than comparing the geometries, as illustrated in mapbox/mapbox-navigation-ios#818.

[Guardiola31337]

Follow up from #3074 (comment)

Refs. #764 and #808

[kmadsen]

Could we potentially take advantage of direction response values? What would the results be like if we compared the remaining step in a route?

Route A - Steps A0, A1, A2
Route B - Steps B0, B1, B2

Routes A and B are different, if they have different steps.

[kmadsen]

Could we potentially take advantage of direction response values? What would the results be like if we compared the remaining step in a route?

Responding to myself. Considering the code is already done for this, would be good to port it over and use it as is #808

If we add tests around the service usage of the algorithm, which appears to be right here. Then we could verify current usage, and attempt new approaches

[kmadsen]

I haven't been able to find a test case where we need to use this algorithm. All the test cases pass using a string compare on the geometry strings #3262

[kmadsen]

Here's a draft that describes why this is not effective for comparing similar routes #3306

[kmadsen]

A method that appears to be effective, is comparing route step names. As described in this #3116 (comment)

DamerauLevenshteinAlgorithm could be effective if we converted step names to a hash, and then compare how many step differences there are. It is a cool algorithm! But not seeing a practical use for it yet.

Legacy will re-order alternative routes by which one is most similar. But again, why not use string compares? Comparing the number of character differences is not more effective:

Different streets are different streets. The number of character differences does not appear to add information

DamerauLevenshteinAlgorithm.execute("17th Street", "19th Street") --> returns 1
DamerauLevenshteinAlgorithm.execute("Pennsylvania Avenue", "17th Street") --> returns 19
DamerauLevenshteinAlgorithm.execute("17th Street"", "17th Street") --> returns 0 because they're equal

[1ec5]

Comparing the number of character differences is not more effective

Agreed, it was only meant to be a crude (read: too precise) comparison. If we had a word-by-word comparison algorithm at the ready, we would’ve used it on iOS instead. Comparing the number of similar step names should be fine. We didn’t go with that way back in mapbox/mapbox-navigation-ios#818 because of a potential performance concern (comparing an arbitrary number of strings versus doing an edit distance calculation over a single string).

[1ec5]

Different streets are different streets. The number of character differences does not appear to add information

I’m pretty sure we were trying to account for cases like “North 1st Street” versus “1st Street”. At least in the U.S. with TIGER-imported data, cardinal directions can pop in and out arbitrarily even though it’s the same street in reality.