Postgres：用于一对多搜索的浮点数组的余弦相似性索引
Postgres: index on cosine similarity of float arrays for one-to-many search
Cosine similarity 两个大小相等的向量（实数）之间的定义为点积除以范数的乘积。
为了表示向量，我有一个大型 table 的 float 数组，例如CREATE TABLE foo(vec float[])'。给定一个 float 数组，我需要快速（使用索引，而不是 seqscan）通过余弦相似度找到该 table 中最接近的数组，例如SELECT * FROM foo ORDER BY cos_sim(vec, ARRAY[1.0, 4.5, 2.2]) DESC LIMIT 10; 但是我用什么？
pg_trgm的余弦相似度支持不同。它比较文本，我不确定它到底做了什么。名为 smlar (here) 的扩展也具有对浮点数组的余弦相似性支持，但又做了一些不同的事情。我描述的是数据分析中常用的文档特征比较，所以我想 Postgres 会支持它。
我了解到没有扩展程序可以执行此操作，因此我找到了一个有限的解决方法：
如果 A 和 B 都归一化（长度为 1），cos(A, B) = 1 - 0.5 * ||A - B||^2。 ||A - B||是欧氏距离，cos(A, B)是余弦相似度。所以更大的欧几里得距离 <=> 更小的余弦相似度（如果你想象一个单位圆，直观上是有意义的），如果你有非法向量，改变它们的大小而不改变它们的方向不会影响它们的余弦相似度。太好了，这样我就可以归一化我的向量并比较它们的欧几里得距离...
There's a nice answer here about Cube，支持Euclidean距离上的n维点和GiST索引，但只支持100维以下（可以hack得更高，但我有大约 135 或更高的问题，所以现在我很害怕）。还需要 Postgres 9.6 或更高版本。
所以：
- 确保我不关心最多 100 个维度。升级到 Postgres 9.6 或更高版本。
- 用数组填充我的 table 来表示向量。
- 标准化向量以创建额外的
cube 点列。在此列上创建 GiST 索引。
- 按欧氏距离升序得到余弦相似度降序：
EXPLAIN SELECT * FROM mytable ORDER BY normalized <-> cube(array[1,2,3,4,5,6,7,8,9,0]) LIMIT 10;
如果我需要超过 100 个维度，我可以使用多个索引列来实现。在那种情况下会更新答案。
更新： 很确定我无法将 >100 维向量拆分为多列。我最终不得不扫描整个 table.
如果您接受不精确的解决方案，您可以使用随机投影：https://en.wikipedia.org/wiki/Random_projection.
随机生成 k 个与其他向量长度相同的不同向量，并将它们存储在某个地方。您将使用这些在空间上对数据进行分类。对于 table 中的每个向量，对每个随机向量进行点积并存储乘积的符号。
每个随机向量具有相同符号的向量进入同一个 bin，通常具有高余弦相似性的向量最终将进入同一个 bin。您可以将符号作为位打包成一个整数，并使用普通索引将向量拉入与查询相同的 bin 中，然后进行顺序搜索以找到余弦相似度最高的向量。
Cosine similarity 两个大小相等的向量（实数）之间的定义为点积除以范数的乘积。
为了表示向量，我有一个大型 table 的 float 数组，例如CREATE TABLE foo(vec float[])'。给定一个 float 数组，我需要快速（使用索引，而不是 seqscan）通过余弦相似度找到该 table 中最接近的数组，例如SELECT * FROM foo ORDER BY cos_sim(vec, ARRAY[1.0, 4.5, 2.2]) DESC LIMIT 10; 但是我用什么？
pg_trgm的余弦相似度支持不同。它比较文本，我不确定它到底做了什么。名为 smlar (here) 的扩展也具有对浮点数组的余弦相似性支持，但又做了一些不同的事情。我描述的是数据分析中常用的文档特征比较，所以我想 Postgres 会支持它。
我了解到没有扩展程序可以执行此操作，因此我找到了一个有限的解决方法：
如果 A 和 B 都归一化（长度为 1），cos(A, B) = 1 - 0.5 * ||A - B||^2。 ||A - B||是欧氏距离，cos(A, B)是余弦相似度。所以更大的欧几里得距离 <=> 更小的余弦相似度（如果你想象一个单位圆，直观上是有意义的），如果你有非法向量，改变它们的大小而不改变它们的方向不会影响它们的余弦相似度。太好了，这样我就可以归一化我的向量并比较它们的欧几里得距离...
There's a nice answer here about Cube，支持Euclidean距离上的n维点和GiST索引，但只支持100维以下（可以hack得更高，但我有大约 135 或更高的问题，所以现在我很害怕）。还需要 Postgres 9.6 或更高版本。
所以：
- 确保我不关心最多 100 个维度。升级到 Postgres 9.6 或更高版本。
- 用数组填充我的 table 来表示向量。
- 标准化向量以创建额外的
cube点列。在此列上创建 GiST 索引。 - 按欧氏距离升序得到余弦相似度降序：
EXPLAIN SELECT * FROM mytable ORDER BY normalized <-> cube(array[1,2,3,4,5,6,7,8,9,0]) LIMIT 10;
如果我需要超过 100 个维度，我可以使用多个索引列来实现。在那种情况下会更新答案。
更新： 很确定我无法将 >100 维向量拆分为多列。我最终不得不扫描整个 table.
如果您接受不精确的解决方案，您可以使用随机投影：https://en.wikipedia.org/wiki/Random_projection.
随机生成 k 个与其他向量长度相同的不同向量，并将它们存储在某个地方。您将使用这些在空间上对数据进行分类。对于 table 中的每个向量，对每个随机向量进行点积并存储乘积的符号。
每个随机向量具有相同符号的向量进入同一个 bin，通常具有高余弦相似性的向量最终将进入同一个 bin。您可以将符号作为位打包成一个整数，并使用普通索引将向量拉入与查询相同的 bin 中，然后进行顺序搜索以找到余弦相似度最高的向量。