In some embodiments, a streaming message classification method dynamically allocates a stream of messages to a variable number of clusters (e.g. message categories), each containing messages which share a set of similar features. Incoming messages are compared to a collection of known spam clusters. New spam types are identified, and new clusters are created automatically and dynamically in order to accommodate the new spam types. Message clustering is performed in a hyperspace of message feature vectors using a modified k-means algorithm. Triangle inequality distance comparisons may be used to accelerate hyperspace distance calculations.