要走的路是使用相对相似度度量：

$$\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*}$$

Wherex和y是包含哈希识别特征的集合，并且k是实验选择的允许“扩展”距离范围的因素。

鉴于该数据点，实际上是一个大小的二进制向量，2^32仅在哈希表示的位置上设置了位，我们可以将距离计算为哈希集的交集大小除以哈希集总和的大小。

欧几里得距离可以分解为点积

$$\|a-b\|^2=\|a\|^2-2(a\cdot{b})+\|b\|^2$$ 可以有效地计算稀疏向量。

对于二元向量，是的非零索引集的大小，而是和的索引集的交集的大小。（对于位数组，交集只是按位“与”。）$\|a\|^2$$a$$a\cdot{b}$$a$$b$

只需加入两个排序列表。如果您并行执行它们，则只需要遍历每个列表。

但是，如果您希望这更快，您可能需要使用咆哮位图来计算共享位和不同位的数量。

如果您没有注意到：在二进制数据上，几乎任何距离函数都会减少到计算交叉点大小和设置的位数。