One embodiment relates to an apparatus for in-the-cloud identification of spam and/or malware. The apparatus includes computer-readable code configured to be executed by the processor so as to receive queries, the queries including hash values embedded therein. The apparatus further includes computer-readable code configured to be executed by the processor so as to detect a group of hash codes which are similar and to identify the group as corresponding to an undesirable network outbreak. Another embodiment relates to an apparatus for in-the-cloud detection of spam and/or malware. The apparatus includes computer-readable code configured to be executed by the processor so as to receive an electronic message, calculate a locality-sensitive hash based on the message, embed the locality-sensitive hash into a query, and send the query to a central analysis system via a network interface. Other embodiments, aspects and features are also disclosed.