Memory-efficient metric calculation for ultra high dimensional data
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.