algorithm - 相似性搜索的索引

Question

我有大约 1 亿个数字向量(Minhash 指纹)，每个向量包含 0 到 65536 之间的 100 个整数，我正在尝试使用 Jaccard similarity 对该指纹数据库进行快速相似性搜索。 ，即给定一个查询向量(例如 [1,0,30, 9, 42, ...])找到此查询集与 100M 集的数据库的交集/并集的比率。

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

注意事项:我想到了使用 SimHash但在这种情况下实际上需要知道集的交集大小来识别containment而不是纯粹的相似性/相似性，但 Simhash 会丢失该信息。

我试过使用一个简单的 locality sensitive hashing technique如 Jeffrey Ullman's 的第 3 章所述通过将每个向量分成 20 个“带”或长度为 5 的片段，将这些片段转换为字符串(例如 [1, 2, 45, 2, 3] -> “124523”)并将这些字符串用作哈希表中的键来预订，其中每个键都包含“候选邻居”。但问题在于，它为其中一些片段创建了太多候选者，而改变 strip 数量也无济于事。

Answer 1

我可能来晚了一点，但我建议 IVFADC indexing by Jegou et al.: Product Quantization for Nearest Neighbor Search

它适用于 L2 距离/点积相似性度量并且有点复杂，但它在时间和内存方面都特别有效。

它也在 FAISS library for similarity search 中实现，所以您也可以看一下。