BBD-tree is only for low dimensions because it suffers from the curse of dimensionality.

Note that BBD-tree is orthogonal to e-means, they can combined very straightforwardly just like it is combined with k-means. The 10x speedup should remain compared to BBD-tree k-means.

So it's not that e-means is better than BBD-tree, it's that you can combine them to make e-means even better, but only at low dimensions and on CPU.