Oracle中点数据表无索引的最近邻查询的pl/sql代码

Question

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

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

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

Answer 1

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

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

正确的方法是创建自定义索引，但这只是重新发明 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 太低，查询可能不返回任何行。另一方面，这可能是一个有用的功能，具体取决于您的需求。

Answer 2

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

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

前3行是最近的3个点。