c++ - 是否有使用用户提供的提示的最近邻数据结构？

Question

我在 R^n 中寻找一个包含 vector 的数据结构，它可以使用用户提供的关于哪个 vector 可能接近查询的提示来执行最近邻查询。例如:

class NearestNeighborStructure;
...
NearestNeighborStructure structure;
Vector vec1 = {1,0,0};
Vector vec2 = {1,1,0};
Vector vec3 = {1,1,1};
structure.insert(vec1);
structure.insert(vec2);
structure.insert(vec3);

现在让我们假设我想找到最近的邻居

Vector query = {0,0,0};

出于某些神秘的原因，我相信 vec2 非常接近 query。所以我打电话:

Vector nn = structure.findNNusingHint(query, vec2);  // vec2 is a hint
assert(nn == vec1); // vec1 is the correct nearest neighbor

数据结构应该使用我提供的提示。它应该对其进行改进，直到它获得真正的最近邻居。

如果结构支持插入和删除，则加分。

编辑:

我正在寻找可以在亚线性时间内计算最近邻居的结构。至少在某些情况下。类似于 k-d trees或 cover trees .

我的问题有这些特点:

1. k-d 树的维数太高(5 - 50 维)
2. 频繁插入和删除
3. 我总能很好地猜测哪个 vector 最接近查询

我想在 evolutionary algorithm 中使用这个结构用于连续mathematical optimization .该算法包含大量候选解决方案。在这个算法中，每个解决方案都应该知道它的周围环境。

新的候选解决方案是通过稍微修改现有解决方案创建的。这是我要使用的提示，即从现有解决方案中创建新解决方案。

Answer 1

我相信您应该尝试并以 R-Tree 为目标或 M-Tree .

在这两种情况下，我们的想法都是使用边界体积方法。例如，如果您构建一棵二叉树，您可以使用超计划(表示为 vector )将空间分成两半。超计划可能未在特定轴上对齐，并且 vector 与点积的符号指示是继续向左还是向右看(在放置/删除 vector 时)。

对于最近邻搜索，您必须:

• 在与节点本身相同的包围体中找到最近的邻居，这就是候选。
• 如果这个候选比体积的边界更近，你就完成了。
• 如果不是，则需要在比候选对象更近的相邻卷中搜索。

我意识到这是非常高层次的……具体来说，我不知道有效的分区或更新策略。 R-Tree 文章引用了几种方法。