Abstract Given trees T and T * on the same taxon set, the transfer index ϕ ( b, T *) is the number of taxa that need to be ignored so that the bipartition induced by branch b in T is equal to some bipartition in T *. Recently, Lemoine et al . [14] used the transfer index to design a novel bootstrap analysis technique that improves on Felsenstein’s bootstrap on large, noisy data sets. In this work, we propose an algorithm that computes the transfer index for all branches b ∈ T in O ( n log 3 n ) time, which improves upon the current O ( n 2 )-time algorithm by Lin, Rajan and Moret [15]. Our implementation is able to process pairs of trees with hundreds of thousands of taxa in minutes and considerably speeds up the method of Lemoine et al . on large data sets. We believe our algorithm can be useful for comparing large phylogenies, especially when some taxa are misplaced (e.g. due to horizontal gene transfer, recombination, or reconstruction errors).