遗憾的是，他们没有为他们提供更好的参考，不是吗O(log(N))。

您要求论文，显而易见的起点是 SCaNN 库所基于的：https ://arxiv.org/abs/1908.10396

他们在那里说的（第 4 节）是：

在我们量化一个包含 n 个点的数据库之后，我们可以在 O(kd+n) 时间内计算一个查询向量 q 与所有量化点的点积。这比原始未量化数据库所需的 O(nd) 时间要好得多

下一个有用的阅读地点是https://github.com/google-research/google-research/blob/master/scann/docs/algorithms.md

他们使用树对大型数据集进行分区。因此存在明显的O(log(N))搜索复杂性。对于 2112.04426 论文中的 2 万亿令牌数据集，该 github 页面上的平方根建议意味着大约 150 万个分区。

他们还为近似邻居搜索的产品量化提供了参考：https ://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_with_quantization.pdf

表 II 比较了在 SDC 和 ADC 之间找到 k 个最小距离的时间。（我假设那里的 ADC 与 ScaNN 中使用的 AH（非对称散列）相同。）不幸的是，表 II 的格式不正确，两个单元格相互碰撞（？）。

然而，我找到了同一作者的基本相同的论文，https://hal.inria.fr/inria-00410767/document/，其中有一个表 2 显示复杂性为n + k log n.

这与另一篇论文中的表 II 中的任何内容都不相似，也不是 O(kd+n)。有点不满意。

但是，总的来说，我假设 O(log(N)) 声明是基于分区的树搜索。然后，一旦您在每个分区内进行搜索，它实际上O(kd + √N)是 ，小到可以扔掉吗？