主页 / 问题 / 764135
Accepted
Eugene Bartosh
Asked:2020-12-28 01:31:57 +0000 UTC2020-12-28 01:31:57 +0000 UTC

按给定向量与数据库中向量之间的最小欧几里得距离搜索

  • 772

在 PostgreSQL 表中，double[] 类型的字段存储高维向量（准确地说是 128 个坐标）。

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

对于给定的向量，您需要从数据库中返回一条记录，其中该向量与表记录中的向量之间的欧几里得距离最小。

有一个函数可以使用众所周知的公式计算两个向量的欧几里得距离SQRT((v1[1]-v2[1])^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(target_vector,tab.vector) as eucl from tab 
order by eulc ASC
limit 1

到目前为止，一切都很好。但不难看出，查询只能通过穷举表中的所有记录来执行。在某种程度上，这适合每个人，但是现在数据库正在增长，并且出现了一个问题，即详尽的搜索并不是很好，委婉地说。现在数据库中有几千条记录，还没有明显的性能问题，但几万条记录已经不远了。

问题 - 在执行查询时，如何设计并在选项卡表中提供索引搜索？这样至少 90% 的不必要记录被索引丢弃，剩下的 10% 已经允许通过完整的枚举。

PS 寻找解决方案的当前方向之一：PostGIS扩展允许您在 3 维空间中按距离搜索和排序 (ST_3DDistance)、按距离过滤 (ST_3DWithin) 等 - 这可以通过索引快速完成。也许有人以某种方式将其抽象为 N 维空间的情况？

PS2。气象观测数据：

  • 做了一个查询 select max(val), min(val) from (select unnest(vector) as val from tab) as tab1 - 0.485470712185 -0.41735497117 - 我不确定，我认为坐标值理论上可以不超过 1.0 模
  • 虽然向量未归一化，但距 (0,0,...0) 的距离在 1.2 到 1.6 的范围内。

PS3。这不是我第一次解决这样的问题 - 上一次它与在点云 (3D) 中查找最近的点有关，但是我在内存中（iBoxDB 数据库）本地拥有一切，我什至没有尝试摆脱一个完整的枚举......这就是postgresql服务器的全部力量——从我想要解决的原理来看）。

PS4。根据观测数据，点之间的最大距离（基于可用的统计数据）约为 3.2 - 让我们将其扩展为 5，以防万一，或最多 10。我绝对对相距超过 1.0 的点不感兴趣从彼此。让我们从 128 维空间中挑出几个（多少不介意，比如说 10.20）三维投影 - 坐标集 (v1,v2,v3)、(v4,v5,v6) 等。显然，如果在其中一个三维投影中距离超过极限（1.0），那么在全坐标组上它肯定不会变小。接下来，我们尝试应用 PostGIS 中的内容 - 我们索引它们的每个向量的三维投影，然后在搜索时，我们使用 ST_3DWithin < 1.0 设置过滤器（过滤器的数量将等于选择的三个 -尺寸投影）。值得一试的新年前夜：-) 我真的很想从 PostGIS 专家那里得到一个称职的评论 - 奇迹会在除夕发生，还是我们可以玩得开心？:-)

PS5。在水桶的方向上，我建议不要再挖了-首先，无论您如何分散它们，它们都会很多-即使您建立在投影上而不是在全维度上，假设取前64个坐标并将它们分散在花束中（<0，>=0） - 它将起作用 18446744073709551616 可能的花束 - 它在哪里......其次，存在花束边界的问题 - 点可以在最小距离处但落入相邻花束，在查询中必须考虑到这一点，为此，您需要为每个花束保留邻居图...如果您应用最简单的分区 (<0,>=0) - 原则上，它失去了所有意义，因为对于一个轴，只有一个边界，您仍然需要在这里和那里查看...如果您将每个轴分为 4 个范围 - 花束的数量肯定会达到无穷大... 第三，

sql

3 个回答

  1. Best Answer

    当从 N 个测量中进行两个或三个测量时，存在降维技术。例如：

    还有许多其他方法可以解决过多维度的问题。包括你可以看看聚类算法。

    不一定在您的数据上，这些算法中的任何一个都可以很好地工作，但有些可能会给出可接受的结果。

    另一件事是，考虑到您的数据是不透明的，您不会走得太远。您最好了解哪些坐标意味着什么。当然，这些向量不是随机数。您很可能从神经网络的倒数第二层获取它们。这意味着对于一些已知的样本，它在某些因素上是完全不同的，有可能找出哪个神经元对应于这个因素。现在您已经有了一个 3 维向量的坐标，您可以快速搜索它。

    • 5

  2. 这更像是评论而不是答案，但它不适合评论。

    在这里，我看到了两个方向 - 在哪里挖掘。第一个是来自 PostgreSQL 的“桶”。我不能确切地说它们如何适合这里 - 我自己没有使用它们，我只是阅读它们。第二个是用于从最接近给定点的集合中找到点的旧单元格。我们将您的 128 维世界划分为立方体。立方体的大小将取决于坐标范围，立方体可以是平行六面体。所有立方体都有编号 - 立方体的数量可以从它沿所有 128 个轴的索引计算（沿轴的索引通过简单除法找到）。所有点都预先分配到立方体中。我们找到给定点落在哪个立方体中。很大程度上取决于空间中点的均匀分布。可以仅计算同一个立方体中或其中的点以及它周围的立方体的 [square] 距离（但是，它们中的三个在 128 度）。

    更新

    我绝对对相差超过 1.0 的点不感兴趣。

    这是一个很好的预取条件：

    WHERE ABS(v1[1]-v2[1]) < 1 AND ABS(v1[2]-v2[2]) < 1 AND ... AND ABS(v1[128]-v2[128]) < 1
    • 2

  3. 可以不是均匀地而是自适应地划分为立方体，并且不是存储所有立方体，而只存储包含元素的立方体。

    例如，如果一个立方体包含多个元素，例如超过 15 个，那么我们将其拆分为多个部分。

    结果是一组不同大小的立方体，或一棵立方体树。

    那么求解算法如下。我们正在寻找元素进入的最小立方体，如果向量集中在一个点，则此操作介于复杂度常数和对数复杂度之间。然后我们只检查这个立方体和相邻的元素（如果向量靠近立方体的边界）。

    更新：

    但是这里出现了相邻正方形的问题......事实上，在相邻的平面中 - 8，在 3 维空间 26 ...... 和 128 维空间中，会有很多。

    在这种情况下，您可以这样做，计算到边缘的最小距离，如果从同一个立方体中找到的距离小于到最近的边缘，则找到向量。如果边缘更近，那么我们已经在寻找邻居或完全枚举。

    • 2

相关问题