Publications of Torsten Hoefler

Maciej Besta, Raghavendra Kanakagiri, Harun Mustafa, Mikhail Karasikov, Gunnar Rätsch, Torsten Hoefler, Edgar Solomonik:

Communication-Efficient Jaccard Similarity for High-Performance Distributed Genome Comparisons

(May 2020, In Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium )

Abstract

Jaccard Similarity index is an important measure of the overlap of two sets, widely used in machine learning, computational genomics, information retrieval, and many other areas. However, little efforts have been made to develop a scalable and high-performance scheme for computing the Jaccard Similarity for today's large data sets. 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. The resulting scheme is the first to enable accurate Jaccard distance derivations for massive datasets, using large-scale distributed-memory systems. We package our routines in a tool, called GenomeAtScale, that combines the proposed algorithm with tools for processing input sequences. Our evaluation on real data illustrates that one can use GenomeAtScale to effectively employ tens of thousands of processors to reach new frontiers in large-scale genomic and metagenomic analysis. While GenomeAtScale can be used to foster DNA research, the more general underlying SimilarityAtScale algorithm may be used for high-performance distributed similarity computations in other data analytics application domains.

Documents

download article:

download slides:

BibTeX

@inproceedings{,
  author={Maciej Besta and Raghavendra Kanakagiri and Harun Mustafa and Mikhail Karasikov and Gunnar Rätsch and Torsten Hoefler and Edgar Solomonik},
  title={{Communication-Efficient Jaccard Similarity for High-Performance Distributed Genome Comparisons}},
  year={2020},
  month={May},
  note={In Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 18.191.192.113:16203	© Torsten Hoefler