Fast Hamming distance in R using matrix multiplication


This post is strictly about binary matrices. For matrices of any data type, have a look at this post.

The hamming distance is perhaps the most frequently used distance measure for binary vectors. It is defined on two vectors of equal length as the number of corresponding elements that differ between the two vectors. A special case of the Hamming distance, is the Hamming distance between two binary vectors, which is often used e.g. in telecommunication to count the number of bit flips in a signal, and in bioinformatics as a similarity measure for hierarchical clustering. While this binary Hamming distance calculation between only two vectors is simple and computationally cheap, calculating all pairwise distances between the rows of a matrix quickly becomes prohibitive, as the computation time scales quadratically with the number of rows in a matrix. The following R function represents a basic implementation of calculating the Hamming distance between all rows of a matrix, using a nested for-loop:


hamming_loop <- function(X) {
	d <- matrix(0, nrow = nrow(X), ncol = nrow(X))
	for ( i in 1:(nrow(X) - 1) ) {
		for ( j in (i + 1):nrow(X) ) {
			d[i,j] <- d[j,i] <- sum(X[i,] != X[j,])
		}
	}
	d
}

 

However, in R, the Hamming distance between the rows of a binary matrix can be computed much faster, by exploiting the fact that the dot product of two binary vectors x and (1 – y) counts the corresponding elements where x has a 1 and y has a 0:


hamming <- function(X) {
	D <- (1 - X) %*% t(X)
	D + t(D)
}

To demonstrate how much faster the matrix multiplication function is than the nested for-loop function, I ran some simulations. In addition to the above two functions, I included the function hamming.distance from the R-package e1071:

Hamming distance computation time in seconds, as a function of number of rows, while keeping the number of columns at 100.
Hamming distance computation time in seconds, as a function of number of rows, while keeping the number of columns at 100.

The relatively naive nested for-loop approach is faster than the hamming.distance function from the e1071 package. This is surprising, since the e1071 hamming.distance function is also implemented as a nested loop. Strikingly, the matrix multiplication-based function is by far the fastest function for computing the Hamming distance, the reason being that it does not use any expensive looping at R-level, only efficient lower level linear algebra routines. Note that the above approach is restricted to binary matrices. However, quite conveniently, matrix multiplication can also be used for computing the Hamming distance for matrices with more than two possible values, and other types of elements (character, numeric, …), as explained in this post.

18 thoughts on “Fast Hamming distance in R using matrix multiplication

      1. Unfortunately that problem is caused by the machine you’re running the algorithm on, not by the matrix multiplication. Regardless of the algorithm, the result matrix will remain 200000 x 200000. If you’re having memory issues you could try (1) having a look at sparse matrices (if your data is sparse), or (2) the bigalgebra package in R, or (3) processing your matrix in batches and write the results to a file.

        Like

  1. “the dot product of two binary vectors x and (1 – y) counts the corresponding elements that are different between x and y” Is it correct? Say two vectors x = (1, 1, 0) and y = (0, 0, 1), all 3 elements are different, but the dot product between either x * (1 – y) or (1 – x) * y is 3.

    Like

    1. Hmm, I might be missing your point: didn’t you just give an example that supports that statement? The dot product is 3, and the number of corresponding elements that are different is also 3.

      Like

  2. Ah, now I see what you mean, and also see that the phrasing might not be entirely clear (well spotted; updated now). The dot products do in fact count the number of corresponding elements that are different between x and y. For each element in the distance matrix, you could see it as adding two dot products, one that is explicitly computed, and one that is implicitly computed. More specifically, the following is an equivalent way of computing distance matrix: (1 – X) %*% t(X) + X %*% t(1 – X). Note however that X %*% t(1 – X) == t((1 – X) %*% t(X)). Hence, for efficiency reasons, I choose to compute it only once, and then add the transpose, i.e. D + t(D). So, one dot product that computes all distances.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s