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 treesやcover treesのようなもの。

私の問題には次の特徴があります。

  1. kd ツリーの次元が高すぎます (5 ～ 50 次元)
  2. 頻繁な挿入と削除
  3. どのベクトルがクエリに近いかについて、私は常に良い推測をしています

この構造を、連続的な数学的最適化に使用される進化的アルゴリズムで使用したいと考えています。アルゴリズムには、多数の解候補が含まれています。各ソリューションは、このアルゴリズムの周囲を認識している必要があります。

新しい候補ソリューションは、既存のソリューションをわずかに変更することによって作成されます。それが既存の解決策から新しい解決策を生み出すヒントです。

4

4 に答える 4

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;
}

挿入するポイントの量がわからない場合は、別のコンテナー (deque など) を使用できます。

于 2013-08-23T07:33:04.563 に答える