获得给定向量和数据库中向量之间的最小欧几里德距离

Question

我将PostgreSQL表中的128D向量存储为double precision []:

create table tab (
   id integer,
   name character varying (200),
   vector double precision []
 )

对于给定的向量,我需要从数据库返回一条记录,该向量与表条目中的向量之间的最小欧氏距离.

我有一个函数,根据已知公式SQRT计算两个向量的欧几里德距离((v11-v21)^ 2 +(v1 [2] -v2 [2])^ 2 + .... +(v1 [128 ] -v2 [128]])^ 2):

CREATE OR REPLACE FUNCTION public.euclidian (
  arr1 double precision [],
  arr2 double precision [])
  RETURNS double precision AS
$ BODY $
  select sqrt (SUM (tab.v)) as euclidian from (SELECT
     UNNEST (vec_sub (arr1, arr2)) as v) as tab;
$ BODY $
LANGUAGE sql IMMUTABLE STRICT

辅助功能:

CREATE OR REPLACE FUNCTION public.vec_sub (
  arr1 double precision [],
  arr2 double precision [])
RETURNS double precision [] AS
$ BODY $
  SELECT array_agg (result)
    FROM (SELECT (tuple.val1 - tuple.val2) * (tuple.val1 - tuple.val2)
        AS result
        FROM (SELECT UNNEST ($ 1) AS val1
               , UNNEST ($ 2) AS val2
               , generate_subscripts ($ 1, 1) AS ix) tuple
    ORDER BY ix) inn;
$ BODY $
LANGUAGE sql IMMUTABLE STRICT

查询:

select tab.id as tabid, tab.name as tabname,
        euclidian ('{0.1,0.2,...,0.128}', tab.vector) as eucl from tab
order by eulc ASC
limit 1

一切正常,因为我在标签中有数千条记录.但是数据库将会增长,我需要避免对运行查询的选项卡进行全面扫描,添加一种索引搜索.通过索引过滤掉至少80%的记录会很棒,剩下的20%可以通过全扫描来处理.

解决方案搜索的当前方向之一:PostGIS扩展允许按距离搜索和排序(ST_3DDistance),按距离过滤(ST_3DWithin)等.使用指标可以很好地和快速地工作.是否可以抽象出N维空间？

一些观察:

• 所有的坐标值介于[-0.5 ... 0.5(我不知道到底,我认为[-1.0 ... 1.0]的理论极限)

• 向量未归一化,距(0,0,... 0)的距离在[1.2 ... 1.6]范围内.

这是来自StackExchange Russian的翻译帖子.

Answer 1

您可以查看计算几何，这是一个致力于高效算法的领域。通常在存储的数据量和算法的效率之间存在权衡。因此，通过添加数据我们可以降低速度。特别是，我们正在研究最近邻搜索，下面的算法使用一种空间划分形式。

让我们考虑 3D 情况，因为距原点的距离位于一个狭窄的范围内，看起来它们聚集在一个模糊球体周围。根据每个坐标的符号将空间划分为 8 个立方体，并标记为 +++、++- 等。我们可以计算出从测试向量到每个立方体中的向量的最小距离。

假设我们的测试向量是（0.4,0.5,0.6）。从它到 +++ 立方体的最小距离为零。到 -++ 立方体的最小距离为 0.4，因为 -++ 立方体中最近的向量为 (-0.0001,0.5,0.6)。同样，到 ++ 的最小距离是 0.5，++-：0.6，--+：sqrt(.4^2+.5^2) 等。

然后算法变为：首先搜索测试向量所在的立方体，并找到到该立方体中所有向量的最小距离。如果该距离小于到其他立方体的最小距离，那么我们就完成了。如果不搜索下一个最接近的立方体，直到任何其他立方体中没有向量可以更接近。

如果我们要实现这是一个数据库，我们将为每个向量计算一个密钥。在 3D 中，这是一个 3 位整数，每位中包含 0 或 1，具体取决于坐标 + (0)、- (-) 的符号。因此首先选择 WHERE key = 000，然后选择 where key = 100，依此类推。

您可以将其视为一种哈希函数，专门设计用于轻松查找接近点。我认为这些称为局部敏感哈希

数据的高维度使事情变得更加棘手。对于 128 个维度，仅使用坐标符号即可给出 2^128 = 3.4E+38 种可能性。这是太多的哈希桶，需要某种形式的降维。

您也许可以选择 k 个点并根据您最接近的点来划分空间。