A scalable algorithm for high-quality clustering of Web snippets

We consider the problem of partitioning, in a highly accurate and highly e±cient way, a set of n documents lying in a met- ric space into k non-overlapping clusters. We augment the well-known furthest-point-¯rst algorithm for k-center clus- tering in metric spaces with a ¯ltering scheme based on the triangular inequality. We apply this algorithm to Web snip- pet clustering, comparing it against strong baselines consist- ing of recent, fast variants of the classical k-means iterative algorithm. Our main conclusion is that our method attains solutions of better or comparable accuracy, and does this within a fraction of the time required by the baselines. Our algorithm is thus valuable when, as in Web snippet clus- tering, either the real-time nature of the task or the large amount of data make the poorly scalable, traditional clus- tering methods unsuitable.