Scalable and robust set similarity join

Understand

Set similarity join is a fundamental and well-studied database operator.

• It is usually studied in the exact setting where the goal is to compute all pairs of sets that exceed a given similarity threshold (measured e.g.
• as Jaccard similarity).
• But set similarity join is often used in settings where 100% recall may not be important --- indeed, where the exact set similarity join is itself only an approximation of the desired result set.