# Memory-efficient metric calculation for ultra high dimensional data

I am preparing for clustering the data which can be only represent as a extremely sparse binary vectors. Each of the objects is represented by a large set the binary features ($$10^3$$ ~ $$10^6$$), each identified by a 32-bit hash code. We can assume that in order to represent the data object without loss of information we need to see it as a vector of $$2^{32}$$ bits - in which only the bits at positions identified by hash are set to one.

The problem is, having two data objects, each represented by a sorted set of hashes, how can I calculate the distance between them without storing two $$2^{32}$$ bits long vectors in memory?

• Which distance are you planning on using? Feb 14, 2017 at 12:13
• I'd like to go with Euclidean, but i'm very eager to change my mind if other distance would be more memory efficient. Feb 14, 2017 at 16:14

The way to go was to use relative similarity metric:

\begin{equation*} d(x,y)=\left(1-\frac{\left\vert{x \cap y}\right\vert }{\left\vert{x \cup y}\right\vert }\right)^k \end{equation*}

Where x and y are sets containing hashes identifying features and k is experimentally selected factor that allows "spreading" the range of distances.

Given that data point, being really a binary vector of size 2^32 have bits set only on the positions denoted by the hashes, we can calculate the distance as size of intersection of hash sets divided by size of sum of hash sets.

Euclidean distance can be decomposed into dot products $$\|a-b\|^2=\|a\|^2-2(a\cdot{b})+\|b\|^2$$ which can be efficiently computed for sparse vectors.

For binary vectors, $\|a\|^2$ is the size of $a$'s non-zero index set, while $a\cdot{b}$ is the size of the intersection of the index-sets of $a$ and $b$. (For bit arrays intersection is just a bitwise "and".)

Simply join the two sorted lists. You only need one pass over each list if you do them in parallel.

But if you want this to be fast, you may want to use roaring bitmaps, to count the number of shared and different bits.

In case you have not noticed: on binary data, pretty much any distance function reduces to counting intersection sizes and number of bits set.