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

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]范围内。

That is the translated post from StackExchange Russian。

Answer 1

使用限制在PostgreSQL的128维数据，您将别无选择，只能对每个查询应用完整扫描。

即使是高度优化的索引结构，用于索引像X-Tree或IQ-Tree这样的高维数据也会遇到很多方面的问题，并且通常没有比纯扫描更大的优势。

这里的主要问题是curse of dimensionality，它将使指数结构在20维以上退化。

因此，较新的工作考虑了近似最近邻搜索的问题，因为在具有这么多维度的许多应用中，找到一个好的答案就足够了，而不是最好的答案。 Locality Sensitive Hashing就是这些方法之一。

注意：即使索引结构能够过滤掉80％的记录，您也必须通过磁盘的随机访问操作访问剩余的20％的记录（使应用程序I / O绑定），这将是均匀的比在一次扫描中读取所有数据并计算距离慢。

Answer 2

您可以查看Computational Geometry，这是一个致力于高效算法的领域。在存储的数据量和算法的效率之间通常存在折衷。因此，通过添加数据我们可以降低速度。特别是，我们正在研究Nearest neighbour search，下面的算法使用了一种空间划分的形式。

让我们考虑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，然后选择key = 100等。

您可以将此视为一种哈希函数，它专门用于简化查找关键点。我认为这些被称为Locality-sensitive hashing

数据的高维度使事情变得更加棘手。仅使用坐标符号的128个维度就可以得到2 ^ 128 = 3.4E + 38种可能性。这是太多的散列桶，需要某种形式的降维。

您可以根据您最接近的那些选择k点和分区空间。