索引和查询postgreSQL中的高维数据

Question

我想在高度尺寸中索引数据(可以在[0,254]范围内的整数的128维向量):

| id |      vector       |
|  1 | { 1, 0, ..., 254} |
|  2 | { 2, 128, ...,1}  |
|  . | { 1, 0, ..., 252} |
|  n | { 1, 2, ..., 251} |

我看到PostGIS实现了R-Trees.那么我可以在PostGIS中使用这些树来索引和查询Postgres中的多维向量吗？

我还看到int数组有一个索引实现.

现在我对如何执行查询有疑问.
我可以对整数数组执行knn-search和radius搜索吗？也许我还必须定义自己的距离函数.这可能吗？我想使用曼哈顿距离(块距离)来查询.

我也可以将我的矢量表示为带有模式的二进制字符串v1;v2;...;vn.这有助于执行搜索吗？

例如,如果我有这两个字符串:

1;2;1;1
1;3;2;2

这两个字符串之间的结果/距离应为3.

Answer 1

也许更好的选择是立方体扩展,因为您感兴趣的区域不是单个整数,而是全向量.

Cube支持GiST索引,Postgres 9.6还将KNN索引到多维数据集,支持欧几里得,出租车(又名曼哈顿)和chebishev距离.

令人讨厌的是9.6仍在开发中,但是将立方体扩展的补丁向后移植到9.5并没有问题,我从经验中说出来.

希望128个维度仍足以获得有意义的结果.

这该怎么做？

首先有一个示例表:

create extension cube;
create table vectors (id serial, vector cube);

使用示例数据填充表:

insert into vectors select id, cube(ARRAY[round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000)]) from generate_series(1, 2000000) id;

然后尝试选择:

explain analyze SELECT * from vectors
order by cube(ARRAY[966,82,765,343,600,718,338,505]) <#> vector asc limit 10;
                                                           QUERY PLAN                                                           
--------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=123352.07..123352.09 rows=10 width=76) (actual time=1705.499..1705.501 rows=10 loops=1)
   ->  Sort  (cost=123352.07..129852.07 rows=2600000 width=76) (actual time=1705.496..1705.497 rows=10 loops=1)
         Sort Key: (('(966, 82, 765, 343, 600, 718, 338, 505)'::cube <#> vector))
         Sort Method: top-N heapsort  Memory: 26kB
         ->  Seq Scan on vectors  (cost=0.00..67167.00 rows=2600000 width=76) (actual time=0.038..998.864 rows=2600000 loops=1)
 Planning time: 0.172 ms
 Execution time: 1705.541 ms
(7 rows)

我们应该创建一个索引:

create index vectors_vector_idx on vectors (vector);

它有帮助:

explain analyze SELECT * from vectors
order by cube(ARRAY[966,82,765,343,600,718,338,505]) <#> vector asc limit 10;

--------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.41..1.93 rows=10 width=76) (actual time=41.339..143.915 rows=10 loops=1)
   ->  Index Scan using vectors_vector_idx on vectors  (cost=0.41..393704.41 rows=2600000 width=76) (actual time=41.336..143.902 rows=10 loops=1)
         Order By: (vector <#> '(966, 82, 765, 343, 600, 718, 338, 505)'::cube)
 Planning time: 0.146 ms
 Execution time: 145.474 ms
(5 rows)

在8个维度,它确实有帮助.

Answer 2

(所选答案的附录)

对于想要超过100个维度的人,请注意:多维数据集扩展中有100个维度限制.

棘手的部分是postgres允许你创建超过100维的立方体就好了.当你尝试恢复被拒绝的备份时(最糟糕的时候才能意识到这一点).

根据文档中的建议,我修补了多维数据集扩展以支持更多维度.我为它制作了一个docker镜像,你可以从github repos查看Dockerfile以了解如何自己动手.