Before revision:  To address this issue, we design and implement SimilarityAtScale, the first communicationefficient distributed algorithm for computing the Jaccard Similarity. The key idea is to express the problem algebraically, as a sequence of matrix operations, and implement these operations with communication-avoiding distributed routines to minimize the amount of transferred data and ensure both high scalability and low latency. We then apply our algorithm to the problem of obtaining distances between whole-genome sequencing samples , a key part of modern metagenomics analysis and an evergrowing need due to the increasing availability of high-throughput DNA sequencing data.
After revision:  To address this issue, we design and implement SimilarityAtScale, the first communicationefficient distributed algorithm for computing the Jaccard similarity among pairs of large datasets. Our algorithm provides an efficient encoding of this problem into a multiplication of sparse matrices. Both the encoding and sparse matrix product are performed in a way that minimizes data movement in terms of communication and synchronization costs. We apply our algorithm to the problem of obtaining distances between whole-genome sequencing samples , a key part of modern metagenomics analysis and an evergrowing need due to the increasing availability of high-throughput DNA sequencing data.