索引用于相似性搜索

Question

我有大约一亿个数字向量（Minhash指纹），每个向量包含100个介于0和65536之间的整数，我正在尝试使用Jaccard相似度对这些指纹进行快速相似性搜索，即给定一个查询向量（例如[1,0,30,9,42,…]），找到此查询集合与1亿个集合的交集/并集比率。

要求在笔记本电脑上不包括索引/文件IO时间，在<1秒内返回k个查询向量的“最近邻居”。因此，显然需要某种形式的索引，问题是什么是最有效的方法。

注释： 我曾考虑使用SimHash，但在这种情况下实际上需要知道集合交集的大小来识别包含关系，而不是纯相似度/相似性，但是Simhash会丢失该信息。

我尝试使用简单的局部敏感哈希技术，如Jeffrey Ullman书中第3章所述，将每个向量分成20个“带”或长度为5的片段，将这些片段转换为字符串（例如[1、2、45、2、3] - >“124523”），并使用这些字符串作为哈希表中的键，其中每个键包含“候选邻居”。但问题是它会为某些片段创建太多的候选项，改变带数也无济于事。

- alex

Answer 1

我可能有点晚了，但我建议阅读Jegou等人的IVFADC索引：用于最近邻搜索的产品量化。它适用于L2距离/点积相似度测量，并且有些复杂，但在时间和内存方面都特别高效。 此外，它还被实现在FAISS库中，用于相似性搜索，所以你也可以参考一下这个库。

- fzk

Answer 2

一种处理方法如下：

（1）将向量排列成树形结构（基数树）。

（2）使用模糊条件查询树，换句话说，如果树的每个节点处的值之间的差异在阈值内，则匹配成功。

（3）从（2）生成包含所有匹配向量的子树。

（4）现在，在子树上使用较小的阈值重复过程（2）。

继续执行，直到子树有K项。 如果K项太少，则取先前的树，并对子树中的每个成员计算Jacard距离并排序以消除最差的匹配，直到只剩下K项为止。

- Tyler Durden

Answer 3

六年后回答自己的问题，有一个基准用于近似最近邻搜索，有许多算法可以解决这个问题：https://github.com/erikbern/ann-benchmarks，目前的获胜者是“分层可导航小世界图”：https://github.com/nmslib/hnswlib

- alex

---

http://ann-benchmarks.com/ 是一个更直接的链接。请注意，他们不测试二进制相似性搜索（如minhash）；而且小世界图有它们自己的问题（需要二次时间来构建；不能在困难数据集上工作）。 - Thomas Ahle

谢谢，我猜你所说的“二进制相似性搜索”是指通过Jacquard集合相似系数进行相似性搜索，就像minhash一样（与欧几里得距离、余弦或汉明距离度量不同）。 - alex

以Jaccard为例，但也适用于二进制数据的其他相似度测量方法：https://arxiv.org/pdf/1612.07710 - Thomas Ahle

Answer 4

你可以使用现成的相似性搜索服务，比如AWS-ES或Pinecone.io。

- Ron