Are there cases where Manhattan distance or Hamming distance are useful for vector search, and how do these metrics differ in computational cost or index support compared to Euclidean/Cosine?

Manhattan and Hamming distances are useful in specific vector search scenarios where their unique properties align with the data or problem structure. Manhattan distance (L1) measures the sum of absolute differences between vector coordinates, making it effective for data where differences along individual dimensions matter more than straight-line distances. For example, in recommendation systems analyzing user behavior across discrete categories (e.g., time spent per app), Manhattan distance can better capture incremental differences. Hamming distance, which counts mismatched positions between vectors, is ideal for binary or categorical data, such as comparing hashed image fingerprints or DNA sequences. For instance, detecting similar images using perceptual hashes (binary representations) benefits from Hamming distance, as it quantifies exact positional disagreements.

Computationally, Manhattan and Hamming distances differ from Euclidean (L2) and Cosine in both operations and efficiency. Manhattan requires summing absolute differences, which is slightly faster than Euclidean’s square-and-sqrt steps. For high-dimensional vectors, this can save cycles in tight loops, though both are O(n) in practice. Hamming distance is even cheaper for binary data—it’s a bitwise XOR followed by a population count—often optimized via hardware instructions. However, Hamming only applies to fixed-length, discrete data, unlike Euclidean or Cosine, which handle continuous values. Cosine similarity, which normalizes vectors and computes their dot product, adds overhead from normalization (O(n) operations for vector magnitudes). While libraries optimize these steps, Manhattan and Hamming can still outperform in their niche cases, especially when avoiding floating-point operations.

Index support for these metrics varies. Euclidean and Cosine are widely supported in vector databases (e.g., FAISS, Annoy) and have optimized indexing structures like KD-trees or IVF. Manhattan is less common but supported in some libraries (e.g., Scikit-learn’s BallTree) or via custom implementations. Hamming distance is often limited to specialized indexes for binary data, such as bitmap-based structures or inverted multi-indexes. For example, FAISS includes optimizations for binary codes using Hamming. Developers might need to adapt data (e.g., binarizing features) or use approximate methods to leverage Hamming efficiently. In contrast, Euclidean/Cosine benefit from mature, out-of-the-box solutions for continuous embeddings, making them easier to implement for general-purpose vector search. Choosing the right metric depends on data type, dimensionality, and available tooling.