[/b/] [/d/] [/tu/] [/a/] [/ph/] [/wa/] [/cg/] [/t/] [/p/]
Есть N = 10k векторов в памяти. За каждый шаг T маленькое число m = 10 векторов удаляется из памяти и на их место добавляется равное количество новых. Как для каждого шага быстрее всего найти пару векторов с минимальным косинусным коэффициентом (cosine similarity)? Будем считать что попарная матрица, коэффициент для каждой пары, считается относительно быстро. Особенно учитывая что с шага T > 1 нужно вычислять только (N - m) * m новых пар. Но поиск минимального значения из (N*N)/2 занимает вечность (а например иерархическое кластрирование не может в удаление элементов, как и BK-tree, во всяком случае достаточно быстро).
>>201184не совсем понял пост.>коэффициент для каждой пары, считается относительно быстро.держи их в бинарном дереве и потом ищи минимум между листьями и пэрентом?
>>201184не совсем понял пост.
>коэффициент для каждой пары, считается относительно быстро.
держи их в бинарном дереве и потом ищи минимум между листьями и пэрентом?
>>201184Разбить пространство на сегменты и для каждого искомого вектора искать пары только в его сегменте и соседних сегментах? Если в них векторов нет то расширять радиус поиска.
>>201186 Спасибо, начну с этого.
Эта задача называется maximum inner product search. Есть куча методов для этого, и как заметил ОП, не все могут в быстрое удаление.Советую посмотреть в сторону locality sensitive hashing, там более-менее просто и не зависит от конкретной геометрии данных.
Эта задача называется maximum inner product search. Есть куча методов для этого, и как заметил ОП, не все могут в быстрое удаление.
Советую посмотреть в сторону locality sensitive hashing, там более-менее просто и не зависит от конкретной геометрии данных.
- wakaba 3.0.7 + futaba + futallaby -