标签: kdtree

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

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

我正在寻找一种方法来做快速最近邻居(希望是O(log n))的高维点(通常是~11-13维).我希望它在初始化结构后的插入过程中表现得最佳.KD树出现在我的脑海中,但是如果你不进行批量加载但是进行动态插入,则kd树不再平衡,并且afaik平衡是一项昂贵的操作.

所以,我想知道你喜欢哪种数据结构进行这种设置.您有高维度点,并且您想要插入并查询最近邻居.

我正在查看KD树最近邻搜索的维基百科页面.

维基百科中给出的伪代码在点为2-D(x,y)时起作用.

我想知道,当点是3-D(x,y,z)时,我应该做出什么改变.

我google了很多,甚至在堆栈溢出中经历了类似的问题链接,但我没有找到任何地方的3-d实现,所有以前的问题都需要2-D点作为输入,而不是我的3-D点寻找.

用于构建KD树的Wiki中的伪代码是::

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, …

我正在使用BOW对象检测,我正在编码阶段.我已经看到一些在编码阶段使用kd-tree的实现,但大多数写作都表明kmeans聚类是要走的路.两者有什么区别？

我有一大堆在html5画布上绘制的矩形.

我希望能够使用鼠标跟踪与此图像进行交互(我不能使用SVG,因为它不能扩展到10-100k矩形).有没有任何数据结构/算法,给定鼠标x,y坐标能够告诉你鼠标在哪个框(使用矩形的计算位置)？我在想像kd树,但不确定.

我正在研究一个kd-tree实现,我现在正在使用std :: nth_element来按照中位数对元素的向量进行分区.但是std :: nth_element占用树构造的90%的时间.有谁能建议更有效的替代方案？

提前致谢

我一直在向google查询有关kd-trees和图像比较的一些材料,但我无法在使用kd-trees进行图像比较的技术之间建立"链接".首先,我发现一些文章谈论随机kd树的速度提升,然后我被介绍给SIFT.在基本了解了SIFT如何工作之后,我读到了最近邻搜索.

我真正的问题是:如果我有来自SIFT的点网格,那么我为每个图像创建kd树.最近邻搜索如何帮助我比较图像？起初,我认为将图像与树进行比较可以使用一些算法来检查树结构以及每个点距离图像A的距离是来自同一节点和图像B中的点.

如果问题太愚蠢,请提供材料或搜索​​主题.

谢谢!

因此,在平衡KD树时,您应该找到中位数,然后将所有较少的元素放在左子树上,而将更大的元素放在右侧.但是如果你有多个与中位数具有相同价值的元素,会发生什么？他们是左边的子树,右边还是丢弃它们？

我问,因为我尝试过多次操作,它会影响我最近邻搜索算法的结果,并且在某些情况下,树的给定部分的所有元素都将具有完全相同的值,因此我不这样做知道在这种情况下如何拆分它们.

我们知道 kd-tree 的最近邻搜索的复杂度是 O(logn)。但是如何计算呢？主要问题是回溯的平均时间复杂度。我曾尝试阅读论文“在对数预期时间中寻找最佳匹配的算法”，但对我来说太复杂了。有谁知道一个简单的计算方法？

我有一组经纬度用于各种位置,也知道我当前位置的纬度和经度.我必须从当前位置找出最近的地方.哪种算法最好来自Kdtree和四叉树来找出纬度和经度集中的邻居位置？一个优于其他的优势是什么？你能否对此有所了解？另外,为了上述目的,我们如何在c#中实现这些算法呢？提前谢谢你的答案.