Hamming Distance

For two binary strings a and b of equal length n, the Hamming distance d is calculated as the population count (popcount) of the XOR result:

d(a, b) = popcount(a XOR b)

• Example: a = 10110, b = 10011
• XOR Result: 00101
• Popcount: 2
• The strings differ at the third and fifth bit positions.

This operation is a single CPU instruction on modern processors, making it extremely fast for large-scale comparisons.

Hamming distance satisfies all axioms of a proper metric space, which is critical for its use in similarity search algorithms:

• Non-negativity: d(a,b) ≥ 0, and d(a,b) = 0 if and only if a = b.
• Symmetry: d(a,b) = d(b,a) for all strings.
• Triangle Inequality: d(a,c) ≤ d(a,b) + d(b,c).

These properties guarantee that distance-based indexing structures and range queries behave predictably without pathological edge cases.

Hamming distance directly defines a code's resilience to bit errors in forward error correction (FEC):

• A code with minimum distance d_min can detect up to d_min - 1 errors.
• It can correct up to ⌊(d_min - 1)/2⌋ errors.
• Example: The classic Hamming(7,4) code has d_min = 3, enabling single-bit error correction and double-bit error detection.

This principle underpins ECC memory, satellite communications, and RAID storage arrays.

In large-scale retrieval systems, documents are encoded as compact binary hash codes (e.g., 64-bit or 128-bit). Hamming distance enables efficient approximate nearest neighbor search:

• Constant-time comparison: XOR + popcount is O(1) per pair.
• Radius search: Find all hashes within r bits of a query.
• Multi-index hashing: Splits codes into substrings for sub-linear lookup.

This is the core mechanism behind perceptual hashing systems like PhotoDNA and pHash for detecting near-duplicate images.

Hamming distance is a special case of L1 distance (Manhattan distance) restricted to binary vectors. Key relationships include:

• Cosine Similarity: For binary vectors, cosine similarity is inversely related to Hamming distance when vectors have equal norm.
• Jaccard Distance: Measures set overlap; Hamming distance measures positional difference. SimHash uses Hamming distance on binary fingerprints to approximate cosine similarity.
• Edit Distance: Hamming distance is equivalent to Levenshtein distance restricted to substitution-only operations on equal-length strings.

Despite its efficiency, Hamming distance has specific constraints:

• Equal-length requirement: Strings must be identical in length; it cannot handle insertions or deletions.
• No magnitude sensitivity: All bit positions are weighted equally, unlike weighted or learned metrics.
• Curse of dimensionality: In very high-dimensional spaces (e.g., 1024-bit codes), the relative contrast between nearest and farthest neighbors diminishes.

For variable-length or real-valued data, consider edit distance or cosine similarity respectively.

A dimensionality reduction technique that creates a compact fingerprint where similar documents produce hashes with a small Hamming distance. It works by computing a weighted hash of features, then collapsing the result into a binary string. Documents with few differing bits are near-duplicates.

• Used by Google for web crawl deduplication
• Hamming distance between two SimHash values estimates cosine similarity
• A 64-bit SimHash with a distance of 3 or less typically indicates a near-duplicate

An algorithmic technique that hashes similar input items into the same buckets with high probability. LSH functions are designed so that the probability of collision is high for items with small Hamming distance and low for dissimilar items.

• Enables sub-linear approximate nearest neighbor search
• Bit-sampling LSH uses random bit positions as hash functions
• Fundamental to scaling similarity search to billions of items

A technique that computes a similarity digest of a file, allowing comparison of two files to determine their degree of commonality. Unlike cryptographic hashes where a single bit flip produces a completely different output, fuzzy hashes produce outputs where similarity correlates with shared content.

• ssdeep is the most common implementation using context-triggered piecewise hashing
• Hamming distance can compare the base64-encoded digest chunks
• Used extensively in malware analysis and digital forensics

A class of methods that use deep neural networks to learn compact binary hash codes directly from data. The network is trained so that semantically similar inputs map to codes with minimal Hamming distance, while dissimilar inputs are far apart.

• Loss functions often directly optimize for Hamming distance preservation
• Enables fast image retrieval using bitwise XOR operations
• Typical code lengths range from 16 to 128 bits for efficient storage

The original application domain for Hamming distance. Richard Hamming introduced the concept in 1950 to create codes that could detect and correct bit errors in data transmission. The minimum Hamming distance between valid codewords determines the code's error-correction capability.

• A code with minimum distance d can detect up to d-1 bit errors
• Can correct up to floor((d-1)/2) errors
• Hamming(7,4) code has distance 3 and corrects single-bit errors

A measure of similarity between two non-zero vectors that calculates the cosine of the angle between them. While Hamming distance operates on binary strings, cosine similarity operates on real-valued vectors. For binary vectors, there is a direct mathematical relationship between the two metrics.

• Cosine similarity ranges from -1 (opposite) to 1 (identical)
• For normalized binary vectors, Hamming distance is proportional to angular distance
• Widely used for comparing embedding vectors from neural networks