Индексирование N-мерных векторов - PullRequest
Новая
       11

Индексирование N-мерных векторов

1 голос
/ 06 ноября 2019

Дано: Огромный набор N-мерных векторов - {V1, V2, V3, ..., Vm} Пример вектора: 

[72, 100, 34, 45, 87, 123, 99, 32] // N = 8

Входные данные: В качестве входных данных нам дается другой вектор с тем же размером, что и набор, описанный выше. Назовем этот вектор X.

Цель: Найти наиболее похожие (или верхние K схожих векторов, K относительно мала) из заданного набора для вектора X. Сходство определяется как https://en.wikipedia.org/wiki/Euclidean_distance.

Я ищу подход, который может дать мне сложность O (log M), где M - это число векторов в наборе.

Заметим, что N может быть относительно большим (например, 100, 500, 1000). M огромен (как несколько миллионов или миллиардов).

Я смотрю в https://en.wikipedia.org/wiki/Locality-sensitive_hashing.

1 Ответ

1 голос
/ 07 ноября 2019

Наивный подход O(N.M), поэтому здесь несколько вариантов:

  1. Упорядочение по одной оси O(N.log(M))

    1. (индекс) сортирует список по одной оси

      , что составляет O(N.M.log(M)), но выполняется только один раз.

    2. Двоичныйискать первый вектор, где упорядоченная ось имеет value>=x-threshold

      это O(N.log(M))

    3. линейно искать векторы, пока упорядоченная ось не имеет value<=x+threshold

      это должно быть около O(N.K) и проверить все обработанные векторы, если они похожи на выбранный вами. Если да, добавьте его в список решений.

  2. Упорядочение с учетом хеширования с учетом локальных особенностей O(N+log(M))

    Да, этоприведет к O(N+log(M)), однако с ложными положительными и отрицательными значениями, поэтому, если вы не можете пропустить решения, это не пойдет, так как вам нужно было бы проверить все векторы, просто чтобы быть уверенным.

  3. Упорядочение по признаку O(N+log(M))

    это похоже на # 2 , но вместо использования хеша вы используете особенность данных, относящихся к сходству. Это может быть любой действительный для сравнения. Благодаря этому нет ни ложных срабатываний, ни ложных отрицаний.

    Вы не указали, что означают данные в векторе или какие-либо диапазоны, поэтому я могу только догадываться здесь. Но вы определили сходство как евклидово расстояние, поэтому наша лучшая особенность - это позиция.

    Таким образом, вы можете создать Octree , чтобы пространственно изменить порядок ваших данных. Исходя из этого, вы просто берете входной вектор, находите область, в которой он находится, и ищите все области рядом, вплоть до некоторого порогового расстояния ...

    Если вы установите размер корзины на ваше пороговое расстояние, то вы будете искать только допервые соседние сегменты (всего 8 + 1).

    получение индекса корзины из вектора должно быть в O(N), преобразуя это в O(N+log(M))

...