Дано: антивирусоподобная система, хранящая в себе до хрена и больше бинарных сигнатур.
Требуется: искать сигнатуры по совпадению с бинарной подпоследовательностью за асимптотическое время меньшее, чем O(N).

Для текстовых данных существует великое множество систем полнотекстового поиска, и казалось бы, бери да переводи бинарщину в hex или base64, да пользуйся всеми этими Сфинксами, Эластиками, Мантикорами, или Постгресовским FTS. Однако, помимо неизбежных накладных расходов, есть еще вот какой нюанс: FTS кушают не просто тексты, а желательно тексты на человеческих языках: все эти стемминги, лемматизаторы, нормализаторы как бы намекают, что на "нечеловеческом" материале их производительность неизбежно выродится в линейный поиск.

Существует ли FTS-подомбые движки, заточенные под бинарные данные?

PS. Внутренний голос мне подсказывает, что с этим, скорее всего, на ура справится Постгрес, достаточно лишь правильно его приготовить. Например, индексировать N-грамы, а не корни слов. Если кто-либо из присутствующих занимался чем-то подобным, буду очень благодарен ссылочкам на книги и статьи.