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?
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.