问题标签 [kdtree]

人们总是吹捧KD树非常适合最近邻搜索。但是，如果您的数据集都是离散值，没有真正的距离度量，它们仍然有效吗？

例如，如果您的属性类似于[black, blue, red], [bread, milk, cheese], [right, left, straight, curved]没有连续性，并且测量距离的唯一方法是汉明距离（我们检查有多少与测试示例等效）。KD树在这些情况下仍然有效吗？怎么来的？

我正在查看 KD 树的 Wikipedia 页面。例如，我在 python 中实现了用于构建列出的 kd 树的算法。

然而，使用 KD 树进行 KNN 搜索的算法会切换语言并且并不完全清楚。英文解释开始有意义，但其中的一部分（例如他们“展开递归”以检查其他叶节点的区域）对我来说并没有任何意义。

这是如何工作的，如何在 python 中使用 KD 树进行 KNN 搜索？这不是一个"send me the code!"类型问题，我不希望这样。请简单解释一下:)

我有一组格式如下的数据：

日期/时间 | 纬度 | 经度 | 身高 | 温度

用户可以根据不同空间和时间的大气温度测量值输入这些数据。空间由纬度、经度和高度表示。现在从这组数据中，我必须通过插值。我不确定在这种情况下我必须使用什么样的数据结构。我读过Kd-tree，这是一个选项吗？

我目前正在为物理引擎（爱好项目）编写 KDTree。

KDTree 不包含点。相反，它包含 Axis Aligned 边界框，用于绑定环境中的不同对象。

我的问题是决定如何在 KDTree 节点满时拆分它们。我正在尝试两种方法：

方法1：始终在最大轴上将节点精确地分成两半。

• 这具有相当均匀间隔的树的优点。
• 大缺点：如果对象集中在节点的小范围内，会产生多余的细分。这是因为所有卷都被精确地分成两半。

方法2：找到包含对象的节点区域。拆分平面上的节点，该平面在其最大轴上将该区域分成两半。示例 - 如果所有对象都集中在节点的底部，则它会纵向拆分，从而将底部一分为二。

• 这解决了上面方法的问题
• 当索引存在于同一平面（例如地形）上的东西时，它会创建又长又窄的节点。如果稍后我要添加一些不在同一平面上的其他对象，这些细长节点提供的索引非常差。

所以我在这里寻找的是一种更好的方法来分割我的 KD-Tree 节点。考虑到这将是一个物理引擎，决策需要足够简单以便实时做出。

这个问题应该很容易回答，我感觉可能有很多关于这个主题的文档，但我在搜索中找不到任何东西，所以我认为我正在寻找错误的东西。

假设我有一个大小相等的立方体的世界，每个立方体的值都是 1 或 0。

将具有相似值的立方体合并到最大可能的立方体中的最佳方法是什么。我考虑随机抓取一个并检查相邻节点并将它们组合起来，如果它们都是相同的模糊和重复，但显然结果不会特别优化。我还考虑检查立方体的所有可能组合并比较结果，但这将非常昂贵。

任何人都可以提供的任何帮助都会非常有帮助。

哦，澄清一下，我正在寻找一种从正交碰撞数据中构建 KD 树的方法，以帮助优化路径查找。

我正在实现一个 KD-tree 来将地图点聚类成组。我一直在使用Wikipedia 的 KD-tree 文章作为参考。搜索返回正确的最近邻点，但它比我预期的要慢。这是我的代码：

我的问题是我对“一个简单的比较，看看搜索点和当前节点的分裂坐标之间的差异是否小于搜索点到当前最佳位置的距离（整体坐标） ”的解释是否正确。我将其解释为：

if (fabs(point.coordinate.latitude - self.location.coordinate.latitude) < best.distToPoint)

和

if (fabs(point.coordinate.longitude - self.location.coordinate.longitude) < best.distToPoint)

分别。也欢迎任何其他建议。

谢谢。

我有一个递归函数（在树上），我需要让它在没有递归的情况下工作，并将树表示为隐式数据结构（数组）。

这是功能：

我正在使用此属性将树表示为数组：

这就是我所做的：

现在最后一步是摆脱递归，但我找不到方法，有什么提示吗？谢谢

我正在尝试解决 3 空间中一组对象的 k 最近邻问题。这些对象存在于 MongoDB 集合中，具有基于文档的存储带来的所有欢乐和悲伤。给定一个对象，我想在尽可能少的查询中找到 k 个最近的邻居。集合大小预计约为 10^5，k 在 10 到 50 之间。我真的不希望将整个树存储在内存中。

如何将 KD-Tree 存储在 MongoDB 集合中？

有人知道用 SQL 实现的KD-Tree或类似的空间索引吗？我正在考虑使用 Python 和 Django 的 ORM 编写自己的代码，但我想避免重新发明轮子。

我有一个包含数百万行的表，每行包含 128 列代表图像特征数据。给定一个任意的 128 元素长的图像特征列表，我想使用 KD-Tree 在数据库中找到 N 个最相似的图像。我发现了很多 KD-Tree 实现，但它们似乎都只加载到本地内存中，不能扩展或与数据库通信。

我正在尝试利用 k 最近邻来解决字符串相似性问题，即给定一个字符串和一个知识库，我想输出与给定字符串相似的 k 个字符串。是否有任何教程解释了如何利用 kd-trees 有效地对字符串进行 k-最近邻查找？字符串长度不会超过 20 个字符。