我有大约 100M 个数字向量（Minhash指纹），每个向量包含 0 到 65536 之间的 100 个整数，我正在尝试使用Jaccard 相似度对这个指纹数据库进行快速相似度搜索，即给定一个查询向量（例如 [ 1,0,30, 9, 42, ...]) 求该查询集与 100M 集数据库的交集/并集的比率。
要求是在笔记本电脑上在 <1 秒（不包括索引/文件 IO 时间）内返回查询向量的 k 个“最近邻”。所以显然需要某种索引，问题是最有效的方法是什么。
笔记：我想过使用SimHash，但在这种情况下实际上需要知道集合的交集的大小来识别包含而不是纯粹的相似性/相似性，但 Simhash 会丢失该信息。
我尝试使用Jeffrey Ullman 书中第3 章中描述的简单的局部敏感散列技术，将每个向量分成 20 个“带”或长度为 5 的片段，将这些片段转换为字符串（例如 [1, 2, 45, 2, 3] - >“124523”）并将这些字符串用作哈希表中的键，其中每个键包含“候选邻居”。但问题是它为其中一些片段创建了太多候选者，而改变乐队的数量也无济于事。
我可能有点晚了，但我建议Jegou 等人的 IVFADC 索引：最近邻搜索的产品量化
它适用于 L2 距离/点积相似性度量，有点复杂，但在时间和内存方面都特别有效。
它也在FAISS 库中实现了相似性搜索，所以你也可以看看。
解决此问题的一种方法如下：
(1) 将向量排列成一棵树（基数树）。
（2）用模糊标准查询树，换句话说，匹配是树的每个节点的值的差异是否在阈值之内
（3）从（2）生成包含所有匹配向量的子树
(4) 现在，在阈值较小的子树上重复过程(2)
继续直到子树有 K 个项目。如果 K 的项目太少，则取前一棵树并计算子树每个成员的 Jacard 距离并排序以消除最差匹配，直到只剩下 K 个项目。
6年后回答我自己的问题，有很多算法来解决这个问题的近似最近邻搜索的基准：https ://github.com/erikbern/ann-benchmarks ，目前的获胜者是“Hierarchical Navigable Small World graphs” ：https ://github.com/nmslib/hnswlib
您可以使用现成的相似性搜索服务，例如 AWS-ES 或 Pinecone.io。