====== Hamming Distance ======
**Hamming distance** is a fundamental distance metric used in computer science and information theory to measure the dissimilarity between two strings of equal length, particularly binary vectors. The metric quantifies the number of positions at which the corresponding symbols differ, providing a simple yet powerful way to compare discrete sequences (([[https://en.wikipedia.org/wiki/Hamming_distance|Hamming Distance - Wikipedia]])).

===== Definition and Mathematical Foundation =====
Hamming distance between two strings of equal length is formally defined as the count of positions where the symbols at corresponding indices are different. For binary vectors, this translates to counting the number of bit positions where one vector has a 0 and the other has a 1. Mathematically, for two binary vectors **x** and **y** of length n:

d(x,y) = Σ(x_i ⊕ y_i) for i=1 to n

where ⊕ represents the XOR (exclusive OR) operation. The result is always a non-negative integer ranging from 0 (identical vectors) to n (completely opposite vectors) (([[https://arxiv.org/abs/1906.11172|Survey on Vector Similarity Metrics in Machine Learning]])).

The metric satisfies the mathematical properties of a proper distance metric: non-negativity, identity of indiscernibles, symmetry, and the triangle inequality, making it suitable for clustering, classification, and similarity search applications.

===== Applications in Vector Databases =====
Modern vector database systems like pgvector leverage Hamming distance for specialized use cases involving binary vector representations. Binary vectors are particularly useful in machine learning scenarios where dimensionality reduction or memory efficiency is critical (([[https://www.databricks.com/blog/what-is-pgvector|Databricks - What is pgvector (2026]])).

Common applications include:

* **Information retrieval**: Comparing fingerprints or hash-based document representations
* **Error detection and correction**: Identifying and correcting transmission errors in digital communications
* **DNA sequence analysis**: Comparing genetic sequences where each position represents a nucleotide
* **Nearest neighbor search**: Finding similar items in high-dimensional binary spaces
* **Semantic hashing**: Computing similarity between binary-encoded semantic representations

===== Computational Efficiency =====
The computational efficiency of Hamming distance makes it particularly attractive for large-scale similarity search operations. Computing Hamming distance between two binary vectors requires only bitwise XOR operations followed by a population count (popcount), which modern processors implement as single CPU instructions. This results in extremely fast comparison operations, often faster than floating-point distance metrics like Euclidean or cosine distance (([[https://arxiv.org/abs/2001.04451|Approximate Nearest Neighbor Search on High Dimensional Data - A Comprehensive Survey]])).

For a pair of 1024-bit vectors, the computation involves only one XOR operation per word and a single popcount, making it scalable to billions of vectors in similarity search operations.

===== Relationship to Other Distance Metrics =====
Hamming distance differs fundamentally from continuous distance metrics commonly used in vector similarity:

* **Euclidean distance** measures geometric distance in continuous space, suitable for dense floating-point vectors
* **Cosine distance** measures angular similarity, invariant to magnitude differences
* **Manhattan distance** sums absolute differences across dimensions
* **Jaccard distance** measures set similarity between binary sets

Hamming distance is uniquely suited for binary representations and discrete comparisons, making it complementary to these other metrics rather than interchangeable with them.

===== Limitations and Considerations =====
While computationally efficient, Hamming distance has notable limitations. The metric treats all positions equally regardless of their semantic importance, and it does not account for the magnitude of difference in high-dimensional spaces. For continuous vectors, converting to binary representations through thresholding or hashing may lose significant information. Additionally, Hamming distance is only defined for equal-length strings, requiring padding or alignment for variable-length sequences.

In machine learning contexts, the choice between Hamming distance and other metrics depends on the underlying data representation and the semantic meaning of similarity in the specific application domain.

===== See Also =====
  * [[inner_product_distance|Inner Product Distance Metric]]
  * [[jaccard_distance|Jaccard Distance]]
  * [[l2_euclidean_distance|L2 (Euclidean Distance)]]
  * [[cosine_similarity|Cosine Similarity]]

===== References =====