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

Question

我想在高度维度上索引数据（128 维整数向量在 [0,254] 范围内是可能的）：

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

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

我也看到了index implementation for int arrays.

现在我对如何执行查询有疑问。
我可以对整数数组执行 knn 搜索和半径搜索吗？也许我还必须定义自己的距离函数。这可能吗？我想为我的查询使用 Manhattan distance（块距离）。

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

例如，如果我有这两个字符串：

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

这两个字符串之间的结果/距离应该是3。

Answer 1

也许 cube extension 是更好的选择，因为您感兴趣的领域不是单个整数，而是完整向量。

Cube支持GiST索引，Postgres 9.6也会为Cube带来KNN索引，支持euclidean, taxicab (aka Manhattan) and chebishev distances.

有点烦人的是 9.6 仍在开发中，但是将多维数据集扩展的补丁向后移植到 9.5 是没有问题的，我是根据经验说的。

希望 128 个维度仍然足以得到 meaningful results。

怎么做？

先举个例子table:

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

使用示例数据填充 table：

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 个维度的人，请注意：a 100 dimensions limit in cube extension。

棘手的部分是 postgres 允许您创建超过 100 个维度的多维数据集。当您尝试恢复被拒绝的备份时（意识到这一点的最糟糕的时间）。

按照文档中的建议，我修补了多维数据集扩展以支持更多维度。我为它做了一个 docker 图像，你可以查看 Dockerfile 以了解如何自己做，来自 github repos.

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

indexing and query high dimensional data in postgreSQL

sql

postgresql

indexing

multidimensional-array

postgresql-9.3