Zhao, J.; McDonald, D.; Sfiligoi, I.; Lladser, M. E.; Patel, L.; Weng, Y.; Khatib, L.; Degregori, S.; Gonzalez, A.; Lozupone, C.; Knight, R.

We introduce a new algorithm, DartUniFrac, and a near-optimal implementation with GPU acceleration, up to three orders of magnitude faster than the state of the art and scaling to millions of samples (pairwise) and billions of taxa. DartUniFrac connects UniFrac with weighted Jaccard similarity and exploits sketching algorithms for fast computation. We benchmark DartUniFrac against exact UniFrac implementations, demonstrating that DartUniFrac is statistically indistinguishable from them on real-world microbiome and metagenomic datasets.