1. A method for clustering a set S of n data points to find k final centers, comprising: partitioning said set S into P disjoint pieces S 1,..., S P ; for each said piece S 1, determining a set D 1, of k intermediate centers; assigning each data point in each piece S 1 to the nearest one of said k intermediate centers; weighting each of said k intermediate centers in each set D 1 by the number of points in the corresponding piece S 1 assigned to that center; and clustering said weighted intermediate centers together to find said k final centers, said clustering performed using a specific error metric and a clustering method A.