Быстрий trigram поиск на миллионах строк

Или, еще лучше - поиск ближайших соседей в векторном пространстве, конверсию строки -> триграм-вектора я сам сделаю.

Есть что? В postgresql есть такой поиск, но он работает только до сотен тысяч а если больше начинает тормозить.

Вроде "триграмм" для текстов используют. trigrammnyy-poisk
Что за пространство будет? с целочисленными координатами ? Поиск в векторном пространстве зависит от метрики. Метрика выбирается из адекватности физики данных ментальному представлению.
Для текстовых соображений используют аналоги расстояния редактирования, но можно и самописное.
Из альтернативного в голову приходит что-то вроде квадратно-гнездового метода на целочисленной решётке. Например покоординатный интервальный уточняющий поиск, или половинного деления. В принципе всё равно те же индексы.

Например множество векторов флоат -1..1 с размерностью 100 элементов. Дистанция - косинус или евклидова.

Ага, есть множество подходов - все так или иначе сводится - грубо разбить пространство на бакеты и уже вести точный поиск только внутри нужного бакета.

Но хотелось бы что-то готовое из коробки...

Из коробки для таких размеров не в курсе. Рядом тема про R, мож в нём есть что-то.
А так половинное деление нетрудно реализуется и работает быстро даже без индексов. Вот мож его и поискать?