# On Normalized Compression Distance and Large Malware

arXiv: https://arxiv.org/abs/1509.00689 · HTML: https://mlsanity.com/paper/1509.00689/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2015.

## Built on by (most cited first, 5 of 5)

- [Black-Box Testing of Deep Neural Networks Through Test Case Diversity](https://mlsanity.com/paper/2112.12591/) (2021)
- [Recasting Self-Attention with Holographic Reduced Representations](https://mlsanity.com/paper/2305.19534/) (2023)
- [Zipf-Gramming: Scaling Byte N-Grams Up to Production Sized Malware Corpora](https://mlsanity.com/paper/2511.13808/) (2025)
- [Context Steering: A New Paradigm for Compression-based Embeddings by Synthesizing Relevant Information Features](https://mlsanity.com/paper/2508.14780/) (2025)
- [An Introduction to Compression-Based Machine Learning](https://mlsanity.com/paper/2609.21309/) (2026)

## Abstract (arXiv)

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.