fuzzbuzz hash is a Locality-sensitive hashing algorithm that has the following properties:

The length of the longest common prefix of two bit strings is smaller that the length of the longest common prefix of their fuzzbuzz hash.

The smaller the Hamming distance between two bit strings, the bigger the longest common prefix of their fuzzbuzz hash.

The algorithm rely on a Merkle-tree that use a bitwise `OR`

as a hash
function and then serialize the tree using a top-down depth-first
traversal algorithm.

For instance, let's pick `1001 0001`

bit string. We can construct the
following Merkle tree:

. __ 1 __ / \ / \ 1 1 / \ / \ 1 1 0 1 / \ / \ / \ / \ [1][0][0][1] [0][0][0][1]

Then we can serialize it the tree without the leafs, using top-down depth-first traversal.

Here is the same tree, with the index of each bit between parens:

. __ 1(0)__ / \ / \ 1 (1) 1 (4) / \ / \ 1 (2) 1 (3) 0 (5) 1 (6) / \ / \ / \ / \ [1][0][0][1] [0][0][0][1]

That result is the following bitstring: `111 1101`

At last, we suffix that bitstring with the original bitstring:

11 1110 1001 0001

More experiments in fuzzbuzz repository.

References: