Реализация алгоритма поиска ближайшего вектора с O (log (n))

Question

1. Предположим, у меня есть n документов, представленных в виде единичных векторов, назовите его X.
2. У меня есть векторное представление одного документа, назовите его Xi.
3. Как я могу найти ближайший * вектор в X к Xi без поиска грубой силы (линейное время).

* Расстояние может быть L2; пропорционально равно косинусоподобию, когда мы говорим об единичных векторах.

Мой приблизительный подход (постоянное время): 1. Отсортируйте все документы по каждому векторному измерению. 2. Использование индекса сортировки для грубой силы только через подмножество данных: например, включение всех ближайших 1000 документов для каждого векторного измерения, грубое вычисление расстояния L2 через те документы (1000), которые кажутся близкими во всех (или большинство) габариты. (макс. 1000)

Однако я хотел бы знать, есть ли «более чистое» точное решение, такое как алгоритм «разделяй и властвуй» для проблемы ближайшей пары точек, которая выполняется за время log (n).

PS: Память тоже должна масштабироваться линейно. Но это должно быть нормально.

Пример: я сохраняю 100-мерные векторные представления для 1M документов как 32-битные числа с плавающей запятой.

• Векторные представления: 1M * 100 dims * 32bit = 3.2Gbit = 400MB
• Индексы сортировки: 1M * 100 сортировок * 32 бит = 3,2 Гбит = 400 МБ

Answer 1

Насколько мне известно, не существует алгоритма, который работал бы в худшем случае за O (log n). Однако для более или менее случайно распределенных точек существуют некоторые точные методы разделения пространства, которые работают в среднем за O (log n). Если ваш набор документов X неизменяем, вы можете использовать kd tree . Если вам нужно поддерживать модификации, вы должны попробовать R * tree , которое намного сложнее, но поддерживает вставки и удаления в X, а также имеет более согласованное время запроса (но все же в среднем до O (log n) ). Обе эти структуры используют линейное пространство.