Существуют ли структуры данных ближайшего соседа, использующие подсказку, предоставленную пользователем?

Question

Существуют ли структуры данных ближайшего соседа, использующие подсказку, предоставленную пользователем?

Я ищу структуру данных, содержащую векторы в 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

Структура данных должна использовать подсказку, которую я предоставил. Это должно улучшиться, пока не получит истинного ближайшего соседа.

Бонусные баллы, если структура поддерживает вставки и удаления.

РЕДАКТИРОВАТЬ:

Я ищу структуры, которые могут вычислить ближайшего соседа в сублинейное время. По крайней мере, в некоторых случаях. Что-то вроде k-d деревья или же покрывать деревья.

Моя проблема имеет следующие характеристики:

Слишком высокая размерность для деревьев k-d (5 — 50 размеров)
Частые добавления и удаления
Я всегда догадываюсь, какой вектор находится рядом с запросом

Я хочу использовать эту структуру в эволюционный алгоритм используется для непрерывного математическая оптимизация. Алгоритм содержит большое количество возможных решений. Каждое решение должно знать свое окружение в этом алгоритме.

Новые варианты решений создаются путем незначительного изменения существующих решений. То есть существующее решение, из которого создается новое решение, является подсказкой, которую я хочу использовать.

3

algorithm c++computational-geometry data-structures nearest-neighbor

Решение

Другие решения

Вы могли бы сделать так:

#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), если вы не знаете, сколько очков вы будете вставлять.

0

Есть график ближайших соседей. Вы можете найти его, отыскивая ближайший край к точке и весь ближайший край, т.е. треугольники в триангуляции Делоне. Или вы можете использовать пространственный индекс, например, кривую заполнения пространства. Вы можете скачать мою кривую Гильберта класса php на phpclasses.org. Он использует кривую Гильберта, чтобы найти гамильтонову траекторию.

0

Вы можете рассмотреть шариковое дерево: http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=54F6006443B8E4623DF398158E3284FF?doi=10.1.1.91.8209&Rep = REP1&тип = PDF

0

Источник

Accepted Answer

Я считаю, что вы должны попытаться R-Tree или же M-Tree.

В обоих случаях идея заключается в использовании подхода ограничивающего объема. Например, если вы строите бинарное дерево, вы разделяете пространство пополам с помощью гиперплана (представленного как вектор). Гиперплоскость может быть не выровнена по определенной оси, и знак точечного произведения с вашим вектором указывает, продолжать ли смотреть влево или вправо (при размещении / удалении вектора).

Для поиска ближайшего соседа вы должны:

найти ближайшего соседа в том же ограничивающем томе, что и сам узел, это кандидат.
если это кандидат ближе, чем граница объема, все готово.
если это не так, то вам нужно искать в соседних томах, которые ближе, чем кандидат.

Я понимаю, что это очень высокий уровень … в частности, я не знаю эффективных стратегий разбиения или обновления. Статья R-Tree ссылается на несколько подходов.

1