In 2003 Charles Elkan reported a considerable gain in speed for K-Means clustering using the triangle inequality. In this talk we present some further work specifically targetting the case where the entities being clustered are represented by very sparse vectors in a very large dimensional space. This situation naturallly arises when clustering a large set of documents represented by bag-of-words vectors. In this talk we are concerned only with speed and we specifically concentrate on small numbers of clusters such as are used in iterative clustering schemes such as X-Means.