Each node of a metric tree comprises a similarity hash of a member of a dataset of known message threats, calculated using a given similarity hashing algorithm. The nodes are organized into the tree, positioned such that the differences between the similarity hashes are represented as distances between the nodes. Messages are received and tested to determine whether they are malicious. When a message is received, a similarity hash of the message is calculated using the same similarity hashing algorithm that is used to calculate the hashes of the members of the dataset. The tree is searched for a hash of a known message threat that is within a threshold of distance to the hash of the received message. Searching the tree can take the form of traversal from the root node, to determine whether the tree contains a node within the similarity threshold.