  Normalized Compression Distance (NCD) is a popular tool that uses compression
algorithms to cluster and classify data in a wide range of applications.
Existing discussions of NCD's theoretical merit rely on certain theoretical
properties of compression algorithms. However, we demonstrate that many popular
compression algorithms don't seem to satisfy these theoretical properties. We
explore the relationship between some of these properties and file size,
demonstrating that this theoretical problem is actually a practical problem for
classifying malware with large file sizes, and we then introduce some variants
of NCD that mitigate this problem.
