Эффективное пересечение множеств - решить больше ли пересечение, чем k

Я столкнулся с проблемой, когда мне нужно вычислить пересечения между всеми парами в наборе множеств. Ни один из наборов не меньше небольшой константы k , и меня интересует только, имеют ли два набора пересечение больше, чем k -1 элементов, или нет. Мне не нужны ни фактические пересечения, ни точный размер, только , больше, чем k -1, или нет. Есть ли какой-нибудь хитрый трюк с предварительной обработкой или аккуратный алгоритм пересечения множеств, который я мог бы использовать для ускорения?

Дополнительная информация, которая может быть полезна для ответа на вопрос:

• Множества представляют собой максимальные клики в больших, неориентированных , разреженный граф. Количество наборов может быть порядка десятков тысяч или больше, но большинство наборов, вероятно, будут небольшими.
• Наборы уже отсортированы. элементы каждого набора находятся в порядке возрастания. По сути, это отсортированные списки - я получаю их таким образом из базовой библиотеки для поиска по максимальным кликам.
• Ничего не известно о распределении элементов в наборах (то есть находятся ли они в тесных группах или нет).
• Большинство из установленных пересечений, вероятно, будут пустыми, поэтому идеальным решением была бы продуманная структура данных, которая поможет мне сократить количество пересечений, которые мне нужно сделать.