sql - oracle中n维的曼哈顿距离

Question

我有一个大约有 500 万行的表，每行有 10 列代表 10 个维度。我希望能够在有新输入时在表中执行搜索以使用曼哈顿距离返回最近的行。距离是 abs(Ai-Aj)+abs(Bi-Bj) 的总和...问题是，目前如果我进行查询，它会对整个表进行全扫描，以计算距离每行，然后对它们进行排序以找到前 X。

有没有办法加快流程并提高查询效率？

我在网上查看了 SDO_GEOMETRY 的距离函数，但找不到超过 4 个维度的。

谢谢

Answer 1

如果您要插入一个点A并且您想查找半径r附近的点（即，在任何度量上都小于r），您可以执行一个非常简单的查询：

select x1, x2, ..., xn
from   points
where  x1 between a1 - r and a1 + r
and    x2 between a2 - r and a2 + r
...
and    xn between an - r and an + r

...其中A = (a1, a2, ..., an), 找到一个界限。如果您对 的所有x1, ...,xn字段都有索引points，则此查询不需要完全扫描。现在，此结果可能包括邻域之外的点（即角落中的位），但很容易找到合适的子集：您现在可以检查此子查询中的记录，而不是检查每个点在你的桌子上。

您可能可以进一步细化这个查询，因为使用曼哈顿度量，邻域将是方形的（尽管与上面成 45 度），并且方形相对容易处理！（即使是 10 维。）然而，最终所需的更复杂的逻辑可能比优化更多的开销。

Answer 2

我建议使用基于函数的索引。您需要计算此距离，因此使用基于函数的索引预先计算它。

您可能想阅读以下问题及其链接。基于函数的索引为您创建隐藏列。这个隐藏列将保存 manhanttan distance ，因此排序会更容易。

感谢@Xophmeister 的评论。基于函数的索引不会帮助您获得任意点。我不知道这里有什么 sql 函数可以帮助你。但是如果你愿意使用机器学习数据挖掘算法。

我建议使用k-means clustering对 500 万行进行聚类。假设您找到了 1000 个集群中心。将此集群中心放到另一个表中。根据定义聚类，您的点将被分配到聚类中心。因此，您知道哪些点最接近该集群中心，例如集群 (1) 包含 20.000 个点，...集群 (987) 包含 10.000 个点...

您的任意点将靠近一个集群。您发现您的点最接近集群 987。运行您的 sql ，仅使用属于该集群中心的点，即 10.000 个点。

您需要在架构中添加几个表/列以使其有效。如果您的 5.000.000 行不断变化，您需要在它们发生变化时再次运行 k-means 聚类。但如果它们是相当恒定的值，则每周或每月一次聚类就足够了。