3

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

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

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

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

编辑：

我正在寻找可以在亚线性时间内计算最近邻的结构。至少在某些情况下。像kd 树或覆盖树之类的东西。

我的问题有以下特点：

  1. kd 树的维度太高（5 - 50 维度）
  2. 频繁的插入和删除
  3. 我总是很好地猜测哪个向量靠近查询

我想在用于连续数学优化的进化算法中使用这种结构。该算法包含大量候选解决方案。在此算法中，每个解决方案都应了解其周围环境。

通过稍微修改现有解决方案来创建新的候选解决方案。那是创建新解决方案的现有解决方案是我想要使用的提示。

4

4 回答 4

1

我相信您应该尝试瞄准R-Tree或M-Tree。

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

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

  • 在与节点本身相同的边界体积中找到最近的邻居，这是候选。
  • 如果这个候选项比卷的边界更近，你就完成了。
  • 如果不是，那么您需要在比候选者更近的相邻卷中进行搜索。

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

于 2013-08-23T09:37:44.260 回答
0

有最近邻图。您可以通过寻找离该点最近的边和所有最近的边（即德劳内三角剖分中的三角形）来找到它。或者您可以使用空间索引，例如空间填充曲线。你可以在 phpclasses.org 下载我的 php 类希尔伯特曲线。它使用希尔伯特曲线来寻找哈密顿路径。

于 2013-08-23T08:34:27.623 回答
0

你可以这样做：

#include <vector>
#include <iostream>

struct Point { int x; int y; int z; };

inline std::ostream& operator << (std::ostream& stream, const Point& p) {
    return stream << p.x << ", " << p.y << ", " << p.z;
}

struct NearestNeighborStructure
{
    NearestNeighborStructure(std::size_t num_points) {
        m_points.reserve(num_points);
    }

    void insert(const Point& p) {
        m_points.push_back(p);
    }

    int manhattan_distance(const Point& a, const Point& b) const {
        using std::abs;
        return abs(b.x - a.x) + abs(b.y - a.y)  + abs(b.z - a.z);
    }

    const Point& find(const Point& query /* ignored hint*/) const {
        std::size_t result = 0;
        int distance = std::numeric_limits<int>::max();
        for(std::size_t i = 0; i < m_points.size(); ++i) {
            int d = manhattan_distance(query, m_points[i]);
            if(d < distance) {
                result = i;
                distance = d;
            }
        }
        return m_points[result];
    }

    private:
    std::vector<Point> m_points;
};

int main()
{
    Point p[3] = { {1,0,0}, {1,1,0},  {1,1,1} };
    NearestNeighborStructure structure(3);
    structure.insert(p[0]);
    structure.insert(p[1]);
    structure.insert(p[2]);

    Point query = {0,0,0};
    std::cout << "Nearest: " << structure.find(query) << std::endl;
    return 0;
}

如果您不知道要插入的点数，您可能会使用不同的容器（例如双端队列）。

于 2013-08-23T07:33:04.563 回答
0

您可能要考虑球树：http ://citeseer.ist.psu.edu/viewdoc/download;jsessionid=54F6006443B8E4623DF398158E3284FF?doi=10.1.1.91.8209&rep=rep1&type=pdf

于 2013-08-24T13:53:32.280 回答