Abstract
The Jaccard index is an important similarity measure for item sets and Boolean data. On large datasets, an exact similarity computation is often infeasible for all item pairs both due to time and space constraints, giving rise to faster approximate methods. The algorithm of choice used to quickly compute the Jaccard index \(\frac\{\vert A \cap B \vert\}\{\vert A\cup B\vert\}\) of two item sets \(A\) and \(B\) is usually a form of min-hashing. Most min-hashing schemes are maintainable in data streams processing only additions, but none are known to work when facing item-wise deletions. In this paper, we investigate scalable approximation algorithms for rational set similarities, a broad class of similarity measures including Jaccard. Motivated by a result of Chierichetti and Kumar [J. ACM 2015] who showed any rational set similarity \(S\) admits a locality sensitive hashing (LSH) scheme if and only if the corresponding distance \(1-S\) is a metric, we can show that there exists a space