El otro día vostorga mencionó que estaba probando pbzip2 para acelerar el vaciado de un backup a una cinta. Yo hoy lo ultilizé y me parece muy rapido y por supuesto depende de cuantos nucleos tengas y la velocidad de ellos.
Les dejo el site para que lo bajen, yo solo aptitude install pbzip2 y lo instalé pero por si alguien no tiene una distro con .deb