请教一个算法复杂度问题

[zxCoder]

有 N 个 embedding （就是一列浮点数），和另外 M 个 embedding 。

要求出这 N 个 embedding 分别在另外 M 个 embedding 里相似度最高的那个 embedding 。

这个算法复杂度最优能做到什么程度？不考虑实现问题

相似度可以看成 O(1) 就行

[zhangxh1023]

猜测一波
相似度是啥？如果是最接近的值，或者可以排序，那就可以 O((N + M)logM)？

[zxCoder]

@zhangxh1023 相似度是余弦相似度，不过这里看成 O(1)复杂度就行

[msaionyc]

O(NM)

[otakustay]

提前让 2 个数组都有序可以快不少，不然就是 O(NM)了

[Jooooooooo]

有个隐含的问题是, "相似度" 这个计算是否具备某种关联性.

举个例子, 相似度是 f 的话, 那么已知 f(a, b) 和 f(b, c) 的前提下, 是否能获得 f(a, c) 呢?

或者按照楼上所说, 排序好的数据相似度有更好的结构信息吗?

[yuruizhe]

本质是查找相似度最高的 embeding ，而不是计算相似度
所以实际问题是：向量检索的最快方法有哪些？
暴力检索 100%最精确最耗时，近似最近邻 ANN 检索会有速度与准确性的 trade-off ，可以参考 https://yongyuan.name/blog/ann-search.html 入门介绍

[princelai]

我做 1xM 的余弦相似都使用 scipy 的 cKDTree,我特地搜了一下，文档里这句话应该就是答案吧

https://scikit-learn.org/stable/modules/neighbors.html#k-d-tree