150维空间中的快速最近邻搜索

Question

我想使用任何可能的 RDBMS 创建一个数据库。它将有一个包含大约 150 列的表。目标是执行一些其他对象的最近邻搜索。所以它是150维空间中的NNS。

我已经尝试使用一些明显的方法，例如 L1 或 L2 距离，但当然对于包含多行的表需要花费大量时间。我还尝试查看 KD-tree（注意我没有测试它）和 PG-Strom，但它们对于多维数据并不是一个好的解决方案。

我可以使用数学方法（如 KD-tree）或技术方法（如 PG-Strom）以某种方式提高所描述的搜索速度吗？

我将尝试使用任何可以提高 NNS 速度的 RDBMS。但是 MySQL 和 PostgreSQL 是最适合我的 DBMS。

Answer 1

PostgreSQL 9.6 使用 cube

首先安装cube扩展

CREATE EXTENSION cube;

现在我们将创建一些 n 维空间，在 50 维中包含 100,000 个点。此外，我们将添加一个 GIST 索引。

CREATE TEMP TABLE space_nd
AS
  SELECT i, cube(array_agg(random()::float)) AS c
  FROM generate_series(1,1e5) AS i
  CROSS JOIN LATERAL generate_series(1,50)
    AS x
  GROUP BY i;

CREATE INDEX ON space_nd USING gist ( c );
ANALYZE space_nd;

现在我们将生成一个点并使用<->算子使用欧氏距离找到最近的点。

WITH points AS (
  SELECT cube(array_agg(random()::float)) AS c
  FROM generate_series(1,50)
    AS x
)
SELECT i,
  pg_typeof(space_nd.c),
  pg_typeof(points.c),
  cube_distance(space_nd.c, points.c)
FROM space_nd
CROSS JOIN points
ORDER BY space_nd.c <-> points.c
LIMIT 5;

PostgreSQL 9.6+ 支持其他距离运算符cube。所有这些都可以使用我们创建的 GIST 索引。即，

a <-> b float8  Euclidean distance between a and b.
a <#> b float8  Taxicab (L-1 metric) distance between a and b.
a <=> b float8  Chebyshev (L-inf metric) distance between a and b.

也就是说有一个警告，

为了让人们更难打破东西，立方体的维数限制为 100。如果您需要更大的东西，这在cubedata.h 中设置。

您要求 150 个维度。这可能会带来轻微的并发症。