(The question caught my attention way down into the weekend (many offices starting the working week this minute): observations about the approach for starters.)

As [commented by Pieter Witvoet](https://codereview.stackexchange.com/questions/212823/levenshtein-distance-between-each-pair-of-elements-from-two-large-data-sets/237420#comment411891_212823), determining (all) *similar* strings does *not* require full evaluation of the Levenshtein distance

- difference in length sets a lower bound on Levenshtein distance
- Levenshtein distance follows the [triangle inequality](https://en.m.wikipedia.org/wiki/Triangle_inequality) 
This is related to what ["the Wei/Chuan/Xuemin/Chengqi paper"](https://stackoverflow.com/questions/54511595/optimize-matching-elements-from-two-large-data-sets-using-levenshtein-distance#comment96935784_54516063) seems to exploit (from glossing that over)
- character histograms account for something