  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 important applications in data
cleaning and integration, collaborative filtering, genome sequence assembly,
etc. This problem has attracted significant attention in the past two decades.
However, all previous algorithms either cannot scale well to long strings and
large similarity thresholds, or suffer from imperfect accuracy.
  In this paper we propose a new algorithm for edit similarity joins using a
novel string partition based approach. We show mathematically that with high
probability our algorithm achieves a perfect accuracy, and runs in linear time
plus a data-dependent verification step. Experiments on real world datasets
show that our algorithm significantly outperforms the state-of-the-art
algorithms for edit similarity joins, and achieves perfect accuracy on all the
datasets that we have tested.
