During the last years, malware writers have been using several techniques to evade detection. One of the most common techniques employed by the anti-virus industry is signature scanning. This method requires the end-host to compare files against a database that should contain signatures for each malware sample. In order to allow their creations to bypass these protection systems, programmers use software encryption tools and code obfuscation techniques to hide the actual behaviour of their malicious programs. One of these techniques is packing, a method that encrypts the real code of the executable and places it as data in a new executable that contains an unpacking routine. In previous work, we designed and implemented an anomaly detector based on PE structural characteristics and heuristic values, and we were able to decide whether an executable was packed or not. We stated that this detection system could serve as a filtering step for a generic and time consuming unpacking phase. In this paper, we improve that system applying a data reduction algorithm to our representation of normality (i.e., not packed executables), finding similarities among executables and grouping them to form consistent clusters that reduce the amount of comparisons needed. We show that this improvement reduces drastically the processing time, while maintaining detection and false positive rates stable.