Быстрый поиск словарного вектора для данного вектора. Высокие размеры

Question

Я ищу ответ, который масштабируется, но для моей конкретной цели у меня есть вектор 48-го измерения.Это можно представить в виде массива из 48 целых чисел от 0 до 255.

У меня есть большой словарь этих векторов, примерно 25 тысяч из них.

Мне нужно иметь возможность взятьвектор, который может или не может быть в моей базе данных, и быстро найти, какой вектор из базы данных является ближайшим.Под самым близким я имею в виду традиционную формулу расстояния.

Мой код закончится на python, но это более общий вопрос.

Brute Force слишком медленный.Мне нужен почти словарь скорости поиска.У кого-нибудь есть идея?

Answer 1

Я бы предложил реализовать kd-дерево , на котором вы можете выполнить Поиск ближайших соседей .Время поиска в худшем случае для N точек в k измерениях составляет O(k.N^(1-1/k)), поэтому оно должно масштабироваться сублинейно в N.

Если у меня будет время, я вернусь к этому ответу и предоставлю менее сжатое объяснение, чем в Википедии.

Поскольку вы работаете в Python, эта запись в кулинарной книге Scipy по kdtrees должна помочь.

Answer 2

Другая техника, которая окажется полезной, - это хеширование, чувствительное к месту: http://en.wikipedia.org/wiki/Locality_sensitive_hashing

Из вашего вопроса не ясно, нужны ли вам -точные ближайшие соседи. Если вы довольны возвратом вектора, который приблизительно равен ближайшему соседу, есть более быстрые решения. Смотрите здесь (http://www.cs.umd.edu/~mount/ANN/)