1. A method comprising employing a computer system to perform the steps of: receiving a message stream; determining whether to add a new cluster to a set of spam clusters by determining whether a first message of the message stream belongs to at least one cluster of the set of spam clusters according to a feature space distance between the first message and a centroid of the at least one cluster; when the first message does not belong to any cluster of the set of spam clusters, adding the new cluster to the set of spam clusters, wherein the new cluster includes the first message; performing a comparison between a first quantity and a second quantity, wherein the first quantity is an indicator of a distance separating the first message from a centroid of a first cluster of the set of spam clusters, and wherein the second quantity is d(C 1 , C 2 )/2, wherein d(C 1 , C 2 ) is a distance separating the centroid of the first cluster from a centroid of a second cluster of the set of spam clusters; and deciding according to a result of the comparison whether to compute a distance separating the first message from the second centroid.