哈希方法通常包含两个部分：
-
【编码】将元素通过「data-dependent」或「data-independent」的方式映射为二进制，并通过比较二进制码的汉明距离 (hamming distance) 来搜索相似元素；
-
【搜索】由于二进制码往往比较长（例如 64, 128, 256 bits），采用直接映射的方式，通常找不到任何元素，因此通常考虑找汉明距离小于 $r$ 的元素，即二进制编码最多只有 $r$ 个位置不同。
下文主要介绍 [TPAMI13 - Mohammad Norouzi] 中提出的「在汉明空间中，使用 Multi-index Hashing 精确快速搜索」的方法。
Multi-Index Hashing
首先介绍一下我们所关心的问题：
-
有 $n$ 个元素，每个元素对应 $q$ 位的二进制码；
-
给定一个查询元素，如何快速在 $n$ 个元素中，找到与查询元素汉明距离小于等于 $r$ 的元素。
如果直接搜索，则需要检查的不同的哈希桶 (hash buckets) 个数为：
这显然是不可接受的。因此为了加速上述过程，我们将每个包含 $q$ 位的哈希码 $\mathbf{h}$ 连续切分为了 $m$ 个不相交的子串，$\mathbf{h}^{(1)},…,\mathbf{h}^{(m)}$，每个子串包含 $q/m$ 位。
若两个哈希码 $\mathbf{h}$ 和 $\mathbf{g}$ 最多相差 $r$ 位，则在 $m$ 个子串中，至少存在一个子串，两个哈希码相差的位数不超过 $\lfloor r / m\rfloor$，即对应下述结果：
上述结果即说明，为了找到与 $\mathbf{h}$ 相差位数小于等于 $r$ 的元素，只需分别在 $m$ 个子串中寻找汉明距离小于等于 $r’$ 的元素，然后再一一检查小于 $r’$ 的元素是否满足小于 $r$ 的要求，整体时间开销得到下降。
当然，上述结果还可以进一步提升，即：
具体证明思路是：假设第一个结论不成立，则 $\mathbf{h}$ 和 $\mathbf{g}$ 在前 $a+1$ 个子串中至少一共有 $(a+1)(r’+1)$ 位不同，即在剩下的 $m-(a+1)$ 个子串中，只需找有 $r-(a+1)(r’+1)$ 位不同的元素。此时运用「Proposition 1」，即可得到：
因此若第一个结论不成立，第二个结论必定成立。由此可知，为找到与 $\mathbf{h}$ 相差位数小于等于 $r$ 的元素，只需先在前 $a+1$ 个子串中寻找距离小于等于 $r’$ 的元素，再在第 $a+1$ 到第 $m$ 个子串中寻找距离小于等于 $r’-1$ 的元素即可，整体时间开销进一步得到下降。具体算法如下：
对于「Proposition 2」，有一个特殊情况，即当 $r<m$ 时，$r’=0$ 且 $a=r$，因此只需在前 $r+1$ 个子串中判断 $r’=0$ 的情况。
性能分析
令 $s=q/m$ 为每个子串的长度，根据「Proposition 1」可知，上述算法需要检索哈希表的总次数为：
其中不等号由组合数公式得到（需满足 $r\leq q/2$）。除了查表外，时间开销还包括将查到的元素进行比对，由于元素在哈希表内的分布难以确定，因此假定 $n$ 个元素均匀分布在大小为 $2^s$ 的哈希表中，即总时间开销为：
另外，文中指出当 $s=\log_2 n$ 时，查搜效果较好，因此将 $s=\log_2 n$ 代入 $\operatorname{cost}(s)$，得到：
当 $r/q\leq .11$ 时，$H(.11)<.5$，运行时间复杂度为 $O(q\sqrt{n}/\log_2 n)$；当 $r/q\leq .06$ 时，时间复杂度变为 $O\left(q \sqrt[3]{n} / \log _2 n\right)$，即与 $n$ 的关系为 sub-linear。
K 近邻搜索
很多时候我们并不想找汉明距离小于等于 $r$ 的元素，而是想找汉明距离最近的 $k$ 个元素，但对于不同的查询元素，对于固定的 $k$，需要的 $r$ 相差很大，如下图所示：
对于相同的 $\text{k-NN}$ 问题，不同查询元素所需要的汉明距离 $r$ 也不相同。
因此对于 $\text{k-NN}$ 问题，我们可以将 $r$ 从 $0$ 向上遍历，直至找到 $k$ 个元素为止，具体算法如下：
