Title: EmbedJoin: Efficient Edit Similarity Joins via Embeddings,
Abstract: We study the problem of edit similarity joins, where given a set of strings
and a threshold value $K$, we want to output all pairs of strings whose edit
distances are at most $K$. Edit similarity join is a fundamental problem in
data cleaning/integration, bioinformatics, collaborative filtering and natural
language processing, and has been identified as a primitive operator for
database systems. This problem has been studied extensively in the literature.
However, we have observed that all the existing algorithms fall short on long
strings and large distance thresholds.
In this paper we propose an algorithm named EmbedJoin which scales very well
with string length and distance threshold. Our algorithm is built on the recent
advance of metric embeddings for edit distance, and is very different from all
of the previous approaches. We demonstrate via an extensive set of experiments
that EmbedJoin significantly outperforms the previous best algorithms on long
strings and large distance thresholds.