1

我正在尝试构建一个程序来获取到具有选定 ID 的点的 k 最近邻点。我需要在不使用任何空间定位器功能（如 sdo_geometry 或 nn）的情况下执行此操作。

基本上我在oracle中有一个ID，Data_X，Data_Y的表。假设我的表中有 10 个条目，并且我需要与虚构点 target_x、target_y 最接近的 3 个点。

我们需要用我给定的虚构点计算表中每个点的欧几里得距离。我只是不知道 pl/sql 中的算法会返回最近的邻居 ID。

4

2 回答 2

3

计算每个点与所选点之间的距离（毕达哥拉斯）并按距离排序。伪sql：

select id from points
order by sqrt(sqr(Data_x - target_x) + sqr(Data_y - target_y))

前 3 行是最近的 3 个点。

于 2011-04-04T12:38:34.937 回答
2

nang 的回答是一个很好的起点，如果可以，我会使用它。不幸的是，它很可能需要全表扫描（或者如果您有覆盖索引，则可能需要全索引扫描）。

如果性能成为问题，您可能会考虑在数据上创建一个穷人的空间索引。它不会像“创建索引”那么简单，但它可能会起作用。

正确的方法是创建一个自定义索引，但这只是重新发明 sdo_geometry 轮，你说你希望避免的路径。

一种简单但粗略的方法（免责声明：这只是我脑海中的一个想法，未经测试）可能是创建一个基于函数的索引，将 2D 空间中的所有点分组为方形块。您基本上创建一个索引以将每个 (x,y) 对映射到块列表。每个块都有定义的宽度和高度，要进行搜索，您首先要找出需要搜索的块网格，然后仅在该网格中的点列表中进行查询。

一个示例索引将类似于：

CREATE INDEX grid_block_i ON points (TRUNC(Data_X/100), TRUNC(Data_Y/100), id);

您用什么值代替 100 将取决于您的分数所取值的范围。您将希望将平面划分为大量网格块，以便索引具有合理的选择性；但不会太大，以至于典型的查询必须搜索太多块才能找到候选者。

您可以通过使用如下查询来使用上面的索引：

select id
from (select id, Data_X, Data_Y
      from points
      where TRUNC(Data_X/100) BETWEEN TRUNC(:target_x/100)) - :threshold
                                  AND TRUNC(:target_x/100)) + :threshold
      and   TRUNC(Data_Y/100) BETWEEN TRUNC(:target_y/100)) - :threshold
                                  AND TRUNC(:target_y/100)) + :threshold
     )
order by sqrt(sqr(Data_x - :target_x) + sqr(Data_y - :target_y))

然后，您可以设置 :threshold 以基本上从查询中消除一大组点。我认为如果函数索引的值（即 100）和阈值设置正确，您会看到查询使用基于函数的索引来获取一小组候选对象，而不是计算每个点的距离桌子。

缺点是如果 :threshold 太低，查询可能不会返回任何行。另一方面，这可能是一个有用的功能，具体取决于您的需要。

于 2011-04-04T13:55:52.337 回答