MinJoin: Efficient Edit Similarity Joins via Local Hash Minima

We study the problem of computing similarity joins under edit distance on a set of strings. Edit similarity joins is a fundamental problem in databases, data mining and bioinformatics. It finds import