PostgreSQL：针对一对多搜索的浮点数组余弦相似性创建索引

Question

余弦相似度是指两个大小相等（由实数组成）向量的点积除以各自范数的乘积。

我有一个大型的float数组表，用于表示向量，例如：CREATE TABLE foo(vec float[])'。给定一个特定的float数组，我需要通过余弦相似度快速（使用索引而非序列扫描）在该表中找到最接近的数组，例如：SELECT * FROM foo ORDER BY cos_sim(vec, ARRAY[1.0, 4.5, 2.2]) DESC LIMIT 10; 但我应该使用什么方法？

pg_trgm的余弦相似度支持是不同的。它比较文本，我不确定它具体做了什么。一个名为smlar的扩展程序（这里）也支持对float数组进行余弦相似度计算，但它在做一些不同的事情。我所描述的通常用于数据分析，用于比较文档特征，因此我认为Postgres应该支持它。

- sudo

---

@rd_nielsen < 也是一个二元运算符，但是Postgres有btree索引支持，可以加速带有过滤和排序的查询。 <@ 是数组的二元运算符 - 同样，GiST和GIN支持可以加速查询。 - Nick

那些俄罗斯人不会创建没有索引支持的扩展程序 :) 他们是全文搜索（使用GiST、GIN索引）、数组索引功能（通过GiST的GIN和RD-tree）、R-tree的GiST版本（替换了原始的R-tree实现）、hstore、jsonb索引支持等的作者。如果“smlar”没有实现索引支持，我会非常惊讶。 - Nick

通常情况下，距离被定义为 1/相似度。因此，相似度越大，对象之间的距离就越小，它们之间越“相似”。 - Nick

哦，“N_i是交集中唯一元素的数量，N_a和N_b是每个向量中唯一元素的数量”，更像是Jaccard相似度（并不完全相同，有些奇怪的变体），绝对不像余弦相似度...你从哪里得到这个定义的？源代码还是文档？能提供一个链接吗？ - Nick

顺便提一下，这篇帖子中有一个余弦相似度的postgresql实现。 - Shadi

Answer 1

我了解目前没有这样的扩展程序，因此我找到了一种有限的解决方法：

如果A和B都被标准化（长度为1），则cos(A,B)=1-0.5*||A-B||^2。||A-B||是欧几里得距离，cos(A,B)是余弦相似性。因此，较大的欧几里得距离意味着较小的余弦相似性（如果你想象一个单位圆的话，这在直觉上是有意义的），而且如果你有非正常化的向量，改变它们的大小而不改变它们的方向并不会影响它们之间的余弦相似性。很好，所以我可以标准化我的向量并比较它们的欧几里得距离......

这里有一个很好的答案，讨论了Cube，它支持n维点和GiST索引，其中包含欧几里得距离，但只支持100个或更少的维度（可以通过一些方法进行高级处理，但我在135或更高的处理时出现了问题，所以我现在很害怕）。也需要Postgres 9.6或更高版本。

所以：

1. 确保我不在意最多有100个维度。升级到Postgres 9.6或更高版本。
2. 用数组填充我的表来表示向量。
3. 标准化向量以创建一个额外的cube点列。在此列上创建GiST索引。
4. 按欧几里得距离升序排序，得到余弦相似性降序：EXPLAIN SELECT * FROM mytable ORDER BY normalized <-> cube(array[1,2,3,4,5,6,7,8,9,0]) LIMIT 10;

如果我需要超过100个维度，我也许可以使用多个索引列来实现这个目的。在那种情况下会更新答案。

更新: 我相信将超过100维向量拆分成多个列是无法解决问题的。我最终不得不扫描整个表。

- sudo

---

有进展吗？欧几里得距离关系很好地将其简化为最近点对问题，但索引问题似乎相当困难。也许局部敏感哈希可以解决？ - ShellRox

@ShellRox 你好！那个扩展程序负责索引，他们有一篇关于哈希机制的论文，但是Postgres对索引每行大小有任意限制。如果我编辑扩展程序使用float4而不是float8（又称double），我可以达到大约180个维度。由于其他原因，这个项目已经被放弃了，所以我没有再研究索引问题。此外，我想Postgres并不适用于延迟敏感的机器学习模型推断 ;) - sudo

谢谢您的回复！我也使用Postgres，并希望它可以在512维向量上进行余弦相似度搜索。不幸的是，我没有找到任何有效的方法（除了全扫描）-这个问题是唯一的希望。因此，我相信我必须编写自己的搜索函数。 - ShellRox

Henry Conklin的回答可能适合您的需求。 - sudo

Answer 2

如果您可以接受不精确的解决方案，您可以使用随机投影：https://en.wikipedia.org/wiki/Random_projection。

随机生成与其他向量相同长度的k个不同向量，并将它们存储在某个地方。您将使用这些向量来空间分bin您的数据。对于表中的每个向量，与每个随机向量进行点积并存储乘积的符号。

每个随机向量具有相同符号的向量放入同一个bin中，通常具有高余弦相似度的向量将最终放入同一个bin中。您可以将符号打包为位并使用普通索引将向量拉入与查询相同的bin中，然后执行顺序搜索以找到具有最高余弦相似度的向量。

- Henry Conklin

---

我听说过降维，但没有见过这种。这很酷，因为即使你不想编写扩展程序，也可以只使用Postgres表/查询来完成它。但对于我的情况来说行不通，因为我的数据已经通过SVD或Glove从更高的维度（自然语言）“压缩”下来了。我发现300d比100d给出了更准确的结果。所以实际上我需要全部的300个维度。 - sudo

随机投影可以用作降维，但在这种情况下，我们将向量保持原样，并使用随机投影来分桶。随机投影被用作空间哈希表中的关键字，而不是低维表示。因此，您的向量将保留完整的300维度，但更容易在索引上拉出一组相似的向量。在二维空间中的类比是使用x轴和y轴作为“随机”向量，并通过它们所在的象限对向量进行分组。 - Henry

这确实与新的科学文献相似，该文献利用随机二叉树森林将向量空间划分为由超平面界定的凸多面体非重叠单元格。我一定会尝试它们两个，谢谢！ - ShellRox

@HenryConklin 哦，好的，我搞混了。那很有道理，我同意这应该可以工作。 - sudo

多年后，我翻看了我的SO资料，并决定这是更正确的答案，尽管我的答案可以在不编写自定义扩展的情况下工作。同时，考虑到你们在这里提供的帮助非常棒，我给自己打上勾感觉有些不好意思。 - sudo