问题标签 [kdtree]

我想在可以支持多维搜索的数据库（例如 KDTree 或 RTree）之上构建一个 C++ 应用程序。启用 R-tree 的 SQLite 最多只支持 5 个维度，这比我需要的要小得多。有什么建议吗？

我有一个 MongoDB，里面有大约 100 万个文档。这些文档都有一个字符串，表示 1 和 0 的 256 位二进制文​​件，例如：

0110101010101010110101010101

理想情况下，我想查询接近二元匹配。这意味着，如果两个文档具有以下编号。是的，这就是汉明距离。

Mongo 目前不支持此功能。所以，我被迫在应用层做这件事。

因此，鉴于此，我试图找到一种方法来避免在文档之间进行单独的汉明距离比较。这使得做这件事的时间基本上是不可能的。

我有很多内存。而且，在 ruby​​ 中，似乎有一个很棒的宝石（算法）可以创建许多树，但我似乎都无法完成（但）这会减少我需要进行的查询数量。

理想情况下，我想进行 100 万次查询，找到几乎重复的字符串，并能够更新它们以反映这一点。

任何人的想法将不胜感激。

我有一组线段。我想对它们执行以下操作：

1. 插入新的线段。
2. 查找给定点半径 R 内的所有线段。
3. 找到给定点的半径 R1 内的所有点。
4. 给定一条线段，找出它是否与任何现有线段相交。不需要确切的交点（尽管这可能不会简化任何事情。）

问题是像 kd/bd 树或 BSP 树这样的算法是它们假设一组静态点，在我的例子中，这些点会不断地增加新的点，需要重建树。

哪种数据结构/算法最适合这种情况？

编辑：接受最简单的答案并解决我的问题。谢谢大家！

我正在编写一个使用kd 树在二维空间中查找点的应用程序。在开发过程中，如果能够“看到”每个点周围的最近邻区，那就太好了。

在附图中，红点是 kd 树中的点，围绕每个点的蓝线界定了最近邻搜索将返回包含点的区域。

图像是这样创建的：

这个算法有两个问题：

• （更重要的是）我的（相当快的Core i7）计算机上它很慢。
• （不太重要）它很草率，你可以从不同宽度的蓝线看出。

一组点的这种“可视化”叫什么？

有哪些好的算法可以创建这样的可视化？

我想知道是否有人可以提供一些关于从二维二叉搜索树中删除节点的有用见解。

我知道有四种情况，我已经完成了第一种情况：

1. 删除没有子节点（叶子）的节点，很简单，只需将指向该节点的指针设置为 null。
2. 删除左节点有一个子节点且右节点为空的节点。
3. 删除右节点有一个子节点且左节点为空的节点。
4. 删除具有左右两个子节点的节点。

我不确定如何准确地执行 2,3 和 4。我尝试迭代地执行它，但是，这似乎不起作用。我假设这必须递归完成。有人可以详细说明如何做到这一点。这是在java中，不过没关系:)

前几天，我正在阅读有关kd-trees 的信息。我一直在寻找这样一种数据结构可能有用的具体而简单的情况。有人有这样的例子吗？

我需要根据两个值的范围查询我的数据库，这两个值本质上是我的数据库中的两列 float 类型。

在做了一些研究之后，我缩小了我的选择范围，使用以下任一算法来实现它：

1. 二维正交范围搜索
2. kd树结构

现在我取消了第一个选项，因为我的数据是聚集的，因此它不会有用。

所以我需要使用kd树结构。但是怎么做？我从来没有做过，也不知道从哪里开始。我在我的一个控制器中有一个方法，该方法设置为存根来检索此搜索的结果，但搜索本身并未实现。

我试图获得创建此功能所涉及的系统步骤。到目前为止，这是我认为我需要做的，但不知道这是否是正确的方法。

1. 必须根据数据库中的数据在内存中构建 kd 树。（但不确定何时应该这样做——无论是在 rails 启动时还是在请求到来时？）

2. 当数据发生更新时，编辑树并将整个树保存到数据库中

3. 是否有任何方法可以将 kd 树数据结构保存在数据库本身而不显式构建它？

另外，我在谷歌上搜索过，但想知道是否有人可以为此推荐任何资源？

我正在寻找一种方法来为高维点（通常为~11-13 维）做快速最近邻（希望是 O(log n)）。我希望它在初始化结构后的插入过程中表现最佳。我想到了 KD 树，但是如果您不进行批量加载而是进行动态插入，那么 kd 树就不再是平衡的，并且 afaik 平衡是一项昂贵的操作。

所以，我想知道对于这种设置，您更喜欢哪种数据结构。你有高维点，你想插入和查询最近的邻居。

我一直在研究Delaunay 三角剖分（不是作业），我想到了以下问题：给定S平面上的一组点（基数为n）和一组三角形T（基数应为n-2） - 如何确定是否三角形设置T形成一个德劳内三角剖分DT(S)？

第一个问题是 Delaunay 三角剖分不是唯一的，因此再次为点集重建它并与三角形集进行比较不会给我们答案。此外，最优的 Delaunay 三角剖分算法很难实现（但是，使用像 CGAL 这样的库就可以了）。

假设我们知道如何检查三角形集是否是三角剖分（不一定是 Delaunay）。那么我们应该使用 Delanuay 三角剖分的定义：对于三角剖分中的每个三角形t，没有一点 inS严格位于 的圆周内t。这导致我们采用以下方法：

1. 琐碎的方法。只需迭代T，计算圆周并迭代S，检查点是否在圆周内。然而，这需要O(n^2)时间，这不是非常理想的。
2. 迷人的方法。再次，迭代T并计算周长。如果有一点s在圆周内，则表示它到圆周中心的距离小于半径。使用最近邻搜索结构S，我们将加快我们的算法。例如，简单的 kd-tree结构将我们引导到O(n log n)平均和O(n sqrt(n))最坏情况下的算法。
3. 有没有人有更简单的想法？

现在让我们回到检查是否T是三角剖分的问题。诸如 的相等性S和三角形的顶点集之类的琐碎先决条件的执行速度不会比O(n log n). 剩下的——检查每两个三角形是否T在一个共同的面上相交，或者根本不相交。

1. T同样，我们可以通过一遍又一遍地迭代来做到这一点T，检查交叉点，但这是O(n^2)算法。
2. 让我们想想«三角形t1和t2相交»是什么意思？如果它们的边相交或者如果一个三角形完全位于另一个三角形中，则它们相交。O(n log n)使用Bentley-Ottmann 算法可以及时解决所有边相交的问题（最坏的情况是O((n + k) log n)，其中k是交叉点的计数，但我们可以在找到第一个交叉点的那一刻停止算法）。此外，我们没有认识到一个三角形完全包含另一个三角形的情况，但我相信我们可以修改 Bentley-Ottmann 算法以保持三角形穿过扫描线而不是线段，正如我所说，这产生了我们的O(n log n)算法。但是，实现起来确实很复杂。
3. 我考虑过迭代算法——让我们保持不相交（或仅通过边相交）三角形的结构（它应该与 kd-tree 非常相似）。然后我们尝试添加下一个三角形t：首先检查t' 的任何顶点是否已经在其中一个三角形中——然后我们得到了一个交点。否则，添加t到结构中。但是，如果我们想要O(log n)或O(sqrt(n))有时间进行搜索和添加查询，我们必须平衡这个结构的高度，这对于 kd-trees 来说也太难了。

那么，有没有人知道这个问题的任何简单解决方案？

我有一个图像库，有约 5000 张图像和约 150 个特征。现在我有另一个具有约 300 个特征的图像，我想在我的库中找到 5 个最相似的图像。

蛮力大约需要 300 * 5000 * 150 * 128 次操作，花费太多时间。所以我为我库中每个图像的特征构建了一个 kd-tree，这意味着大约 5000 个 kd-tree。我像其他筛选库一样使用bbf 搜索近似最近的邻居。但是性能变得比我的蛮力算法还要慢。为了确保这不是我实现的错，我修改了其他库的匹配算法以蛮力，它们的性能也有所提高。

我的问题是有没有可能将〜5000 kd-trees组合成一棵树？或者是否有其他方法可以在匹配多个图像时提高性能？