我可以使用任意指标来搜索KD-Trees吗？ [英] Can I use arbitrary metrics to search KD-Trees?

问题描述

我刚刚完成了执行快速最近邻搜索的 kd-tree 。除了欧几里德距离之外，我有兴趣玩不同的距离指标。我对kd-tree的理解是，如果度量是非欧几里德，那么快速的kd-tree搜索不能保证给出精确的搜索，这意味着如果我想尝试，我可能需要实现一个新的数据结构和搜索算法我的搜索出了新的指标。

I just finished implementing a kd-tree for doing fast nearest neighbor searches. I'm interested in playing around with different distance metrics other than the Euclidean distance. My understanding of the kd-tree is that the speedy kd-tree search is not guaranteed to give exact searches if the metric is non-Euclidean, which means that I might need to implement a new data structure and search algorithm if I want to try out new metrics for my search.

我有两个问题：

1. 使用 kd-tree 永久地将我绑定到欧几里德距离？


2. 如果是这样，我应该尝试其他类型的算法， href =http://en.wikipedia.org/wiki/Metric_(mathematics）rel =noreferrer>指标？我没有足够的时间来实现许多不同的数据结构，但我正在考虑的其他结构包括覆盖树和 vp-trees 。

1. Does using a kd-tree permanently tie me to the Euclidean distance?
2. If so, what other sorts of algorithms should I try that work for arbitrary metrics? I don't have a ton of time to implement lots of different data structures, but other structures I'm thinking about include cover trees and vp-trees.

推荐答案

您所链接的维基百科页面上描述的最近邻搜索过程当然可以推广到其他距离度量，只要您将hypersphere替换为给定度量的等效几何对象，并测试每个超平面与此对象的交叉。

The nearest-neighbour search procedure described on the Wikipedia page you linked to can certainly be generalised to other distance metrics, provided you replace "hypersphere" with the equivalent geometrical object for the given metric, and test each hyperplane for crossings with this object.

示例：如果您使用的是曼哈顿距离相反（即矢量分量中所有差异的绝对值的总和），您的超球体将成为（多维）钻石。 （这最容易在2D中可视化 - 如果您当前的最近邻居距离查询点 p 在距离 ，则不同超平面后面的任何更靠近的邻居必须相交钻石形状的宽度和高度为2x，并以 p 为中心）。这可能使超平面穿越测试更难编码或运行较慢，但是一般原则仍然适用。

Example: if you are using the Manhattan distance instead (i.e. the sum of the absolute values of all differences in vector components), your hypersphere would become a (multidimensional) diamond. (This is easiest to visualise in 2D -- if your current nearest neighbour is at distance x from the query point p, then any closer neighbour behind a different hyperplane must intersect a diamond shape that has width and height 2x and is centred on p). This might make the hyperplane-crossing test more difficult to code or slower to run, however the general principle still applies.

这篇关于我可以使用任意指标来搜索KD-Trees吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！