Measuring Data Similarity Through Compression Efficiency

32 concepts23 papers1 proposal

How do we determine if two pieces of data are similar? Traditional machine learning relies on extensive feature engineering or training massive neural networks to map inputs into a high-dimensional vector space. However, a more fundamental, information-theoretic approach bypasses representation learning entirely by looking at a core property of data: compressibility.

The core intuition relies on algorithmic information theory, specifically Kolmogorov complexity—the length of the shortest computer program that can generate a given string. While true Kolmogorov complexity is mathematically uncomputable, standard lossless compression algorithms (such as gzip, LZ77, or Huffman coding) act as excellent practical proxies. As established by Ran El-Yaniv et al. in Agnostic Classification of Markovian Sequences, universal compressors can effectively estimate cross-entropy and statistical similarity between sequences without requiring any prior knowledge of the underlying data generation rules or domain-specific models.

The Mechanics of Joint Compression

Why does compression reveal similarity? Imagine you have two text documents, $A$ and $B$. If you compress $A$ alone, the compressor builds a dictionary of statistical regularities and repeating patterns found within $A$. If $B$ is completely unrelated to $A$, compressing the concatenated string $AB$ yields no additional savings; the compressor must build an entirely new set of dictionary entries to handle the novel patterns in $B$.

However, if $B$ shares significant structural, stylistic, or thematic patterns with $A$, the compressor can reuse the dictionary it already constructed for $A$ to compress $B$ highly efficiently. The joint file size of $AB$ will be significantly smaller than the sum of their individual compressed sizes.

This cross-document compression gain is formally quantified using the Normalized Compression Distance (NCD), a domain-independent metric highlighted by Robert P. Goldman et al. in Measuring Plan Diversity: Pathologies in Existing Approaches and A New Plan Distance Metric and Zohreh Aghababaeyan et al. in Black-Box Testing of Deep Neural Networks through Test Case Diversity. NCD computes the distance between two objects $x$ and $y$ as:

$$NCD(x, y) = \frac{C(xy) - \min(C(x), C(y))}{\max(C(x), C(y))}$$

where $C(x)$ is the compressed size of $x$, and $C(xy)$ is the compressed size of their concatenation.

  • If $x$ and $y$ are highly similar, the compressor reuses its history perfectly, making $C(xy)$ barely larger than $\max(C(x), C(y))$, driving the NCD toward 0.
  • If they share no patterns, $C(xy)$ approaches $C(x) + C(y)$, driving the NCD toward 1.

Extracting Semantics from Statistical Regularity

One might wonder how a purely syntactic tool like a file compressor can capture high-level semantic meaning. The answer lies in the deep connection between statistical regularity and semantic context.

As Zhiying Jiang et al. demonstrate in "Low-Resource" Text Classification: A Parameter-Free Classification Method with Compressors, documents sharing a topic naturally exhibit similar vocabulary distributions and structural patterns. By pairing gzip-based NCD with a simple $k$-nearest-neighbor (kNN) classifier, the authors achieved text classification performance that rivals or outperforms deep learning models like BERT on low-resource and out-of-distribution datasets. Similarly, Michael Ibrahim in Parameter-Free Spanish Hope Speech Detection utilized lossless compression to successfully categorize nuanced social media text without explicit semantic training or parameter optimization.

Beyond broad topic classification, compression metrics excel at capturing subtle stylistic signatures. Because an individual writer maintains consistent, idiosyncratic redundancies in vocabulary and syntax, bidirectional compression analysis can isolate authorship style from content. Cor J. Veenman in Authorship Verification with Compression Features and Manuela Hürlimann et al. in GLAD: Groningen Lightweight Authorship Detection leverage these non-parametric compression features to verify document authorship. This capability allows researchers to link split online identities across different platforms (Einat Amitay et al. in Serial Sharers: Detecting Split Identities of Web Authors) or flag repetitive, automated messaging strategies used by spammers (Kyumin Lee et al. in Seven Months with the Devils: A Long-Term Study of Content Polluters on Twitter).

Robustness to Typographic and Structural Noise

Traditional string-matching metrics like edit distance break down when text undergoes non-standard modifications, such as abbreviations, concatenations, or typos. Compression-based metrics bypass this vulnerability by evaluating character frequency distributions rather than rigid alignments.

In AUTOMS: Automated Ontology Mapping through Synthesis of Methods, Konstantinos Kotis et al. used Huffman coding to compare character clusters, providing a robust lexical matching strategy against typographic variations. This capacity to uncover underlying data semantics from condensed technical identifiers is further leveraged by George Vouros et al. in Uncovering WSDL Specifications' Data Semantics. Furthermore, because information-theoretic patterns scale consistently, Marcus Dobrinkat et al. show in Evaluating Machine Translations Using mNCD that compression distances maintain high stability across varying text granularities, from individual sentences to entire documents.

Domain-Agnostic and Non-Numeric Clustering

Because compression algorithms operate directly on raw bitstrings, they enable parameter-free clustering in non-numeric or unstructured domains where coordinate-based vector spaces do not naturally exist.

Unstructured Data (Text, Plans, Categorical Databases)
       │
       ▼
[ Concatenation (xy) ] ──► [ Lossless Compressor (C) ]
       │                                │
       ▼                                ▼
Individual Sizes: C(x), C(y) ──► Joint Size: C(xy)
       │                                │
       └───────────────┬────────────────┘
                       ▼
           [ NCD Formula Calculation ]
                       │
                       ▼
         Normalized Distance Matrix (0 to 1)
                       │
                       ▼
       Parameter-Free Clustering / Classification

Jilles Vreeken et al. in Identifying the components demonstrated that treating similarity as a specialized model's ability to efficiently compress data subsets allows for the natural clustering of categorical databases without predefined distance metrics. Similarly, Tina Geweniger et al. in Median Variant of Fuzzy c-Means integrated Kolmogorov-complexity-based distance measures into soft clustering algorithms, allowing them to operate seamlessly on raw biological sequences or text. In hardware and storage optimization, Jisung Park et al. in DeepSketch: A New Machine Learning-Based Reference Search Technique for Post-Deduplication Delta Compression utilized empirical delta-compression ratios directly as a distance metric to group binary data blocks, optimizing signatures specifically for storage reduction.

Scaling to Deep Learning and Vision

The core philosophy of compression-based similarity is not restricted to classic byte-level compressors like gzip; it scales to deep neural representations.

For out-of-distribution (OOD) image detection, Dongha Lee et al. introduced Compression Complexity Pooling (CCP) in Convolutional Neural Networks with Compression Complexity Pooling for Out-of-Distribution Image Detection. By evaluating the joint compression efficiency of spatial feature maps within a neural network, the authors determine whether a test sample shares underlying structural patterns with the reference training distribution.

Taking this a step further, Zhiying Jiang et al. in Few-Shot Non-Parametric Learning with Deep Latent Variable Model substituted standard compressors with deep generative models (such as Variational Autoencoders). By using the generative model to compute the relative number of bits required to represent two images together, they applied NCD to complex visual data, outperforming traditional supervised methods in extreme low-data regimes.

Whether applied via a 14-line gzip script or a deep latent variable model, compression-based similarity works because it uncovers the shared information content inherent in data. By measuring how much one sequence can help describe another, it provides a mathematically grounded, parameter-free window into similarity.

Key Foundational Work

A mutual information kernel for sequences (2004) — contributed 2 concept elements to this direction.
Agnostic Classification of Markovian Sequences (1997) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 22 papers
  2. Version 1 · 2026-10-04 · 33 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_normalized_compression_distance_de22d33b,
  title = {normalized compression distance},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/normalized-compression-distance/rdr_de22d33b0df148dc887ea7281baf8bb6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_normalized_compression_distance_de22d33b_v2,
  title = {normalized compression distance},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/normalized-compression-distance/rdr_de22d33b0df148dc887ea7281baf8bb6/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake