Nowere Archives — Бред

Файл: 1652531137454.jpg -(1179 KB, 3223x4021, 1652531137454.jpg)

anonymous 2022/05/14(Sat)15:25 No.201184

Есть N = 10k векторов в памяти. За каждый шаг T маленькое число m = 10 векторов удаляется из памяти и на их место добавляется равное количество новых. Как для каждого шага быстрее всего найти пару векторов с минимальным косинусным коэффициентом (cosine similarity)? Будем считать что попарная матрица, коэффициент для каждой пары, считается относительно быстро. Особенно учитывая что с шага T > 1 нужно вычислять только (N - m) * m новых пар. Но поиск минимального значения из (N*N)/2 занимает вечность (а например иерархическое кластрирование не может в удаление элементов, как и BK-tree, во всяком случае достаточно быстро).

>>	anonymous 2022/05/14(Sat)15:53 No.201185 Файл: 1652532794912.jpg -(136 KB, 600x800, 1652532794912.jpg) >>201184 не совсем понял пост. >коэффициент для каждой пары, считается относительно быстро. держи их в бинарном дереве и потом ищи минимум между листьями и пэрентом?

>>	anonymous 2022/05/14(Sat)17:05 No.201186 Файл: 1652537119491.jpg -(2477 KB, 2000x1391, 1652537119491.jpg) >>201184 Разбить пространство на сегменты и для каждого искомого вектора искать пары только в его сегменте и соседних сегментах? Если в них векторов нет то расширять радиус поиска.

>>	anonymous 2022/05/14(Sat)18:12 No.201187 >>201186 Спасибо, начну с этого.

>>	anonymous 2022/05/14(Sat)18:16 No.201188 Эта задача называется maximum inner product search. Есть куча методов для этого, и как заметил ОП, не все могут в быстрое удаление. Советую посмотреть в сторону locality sensitive hashing, там более-менее просто и не зависит от конкретной геометрии данных.