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

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

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

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

Ответ 1

Рассмотрим отображение со всеми наборами размера k в качестве ключей и соответствующими значениями списков всех наборов из вашей коллекции, которые содержат ключ в качестве подмножества. Учитывая это сопоставление, вам не нужно выполнять какие-либо тесты пересечения: для каждого ключа все пары наборов из списка будут иметь пересечение с размером не менее k. Этот подход может производить одни и те же пары множеств более одного раза, поэтому их необходимо будет проверить.

Отображение достаточно просто для вычисления. Для каждого набора в коллекции вычислите все подмножества size-k и добавьте исходный набор в список для этого набора ключей. Но разве это быстрее? В общем, нет. Производительность этого подхода будет зависеть от распределения размеров наборов в коллекции и значения k. С d различными элементами в наборах вы могли бы выбрать до k ключей, которые могут быть очень большими.

Однако основная идея позволяет сократить количество пересечений. Вместо использования наборов размера k используйте меньшие фиксированные размеры q в качестве ключей. Значения снова представляют списки всех наборов, у которых есть ключ в качестве подмножества. Теперь проверьте каждую пару наборов из списка для пересечения. Таким образом, при q = 1 вы проверяете только те пары множеств, у которых есть хотя бы один общий элемент, при q = 2 вы проверяете только те пары множеств, которые имеют как минимум два элемента, и так далее. Оптимальное значение для q будет зависеть от распределения размеров наборов, я думаю.

Для рассматриваемых множеств хорошим выбором может быть q = 2. Ключи - это только края графа, дающие предсказуемый размер отображения. Поскольку ожидается, что большинство множеств будут непересекающимися, q = 2 должно устранить множество сравнений без особых дополнительных издержек.

Ответ 2

Одна возможная оптимизация, которая более эффективна, чем меньше диапазон значений, содержащихся в каждом наборе:

Создайте список всех наборов, отсортированных по их k-му наибольшему элементу (это легко найти, поскольку вы уже имеете каждый набор со своими элементами в порядке). Вызовите этот список L.
Для любых двух множеств A и B их пересечение не может содержать в себе k элементов, если k-й наибольший элемент в меньше наименьшего элемента в B.
Итак, для каждого набора, в свою очередь, вычислите его пересечение только с наборами в соответствующей части L.

Вы можете использовать тот же самый факт, чтобы выходить раньше из вычисления пересечения любых двух наборов - если осталось только n-1 элементов для сравнения в одном из множеств, а пересечение пока содержит не более kn элементов, то стоп. Вышеприведенная процедура - это просто это правило, применяемое ко всем наборам в L одновременно, с n = k, в точке, где мы смотрим на наименьший элемент множества B и k-й наибольший элемент A.

Ответ 3

Следующая стратегия должна быть достаточно эффективной. Я использовал вариации этого для пересечения восходящих последовательностей в нескольких случаях.

Сначала я предполагаю, что у вас есть какая-то очередность приоритета (если нет, то перемещение вашей собственной кучи довольно просто). И быстрый поиск ключа/значения (btree, hash, что угодно).

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

# Initial setup
sets = array of all sets
intersection_count = key/value lookup with keys = (set_pos, set_pos) and values are counts.
p_queue = priority queue whose elements are (set[0], 0, set_pos), organized by set[0]

# helper function
def process_intersections(current_sets):
    for all pairs of current_sets:
        if pair in intersection_count:
            intersection_count[pair] += 1
        else:
            intersection_count[pair] = 1

# Find all intersections
current_sets = []
last_element = first element of first thing in p_queue
while p_queue is not empty:
    (element, ind, set_pos) = get top element from p_queue
    if element != last_element:
        process_intersections(current_sets)
        last_element = element
        current_sets = []
    current_sets.append(set_pos)
    ind += 1
    if ind < len(sets[set_pos]):
        add (sets[set_pos][ind], ind, set_pos) to p_queue
# Don't forget the last one!
process_intersections(current_sets)

final answer = []
for (pair, count) in intersection_count.iteritems():
    if k-1 < count:
        final_answer.append(pair)

Время работы будет O(sum(sizes of sets) * log(number of sets) + count(times a point is in a pair of sets). В частности, обратите внимание, что если два набора не имеют пересечения, вы никогда не пытаетесь пересечь их.

Ответ 4

Что делать, если вы использовали предсказуемое подмножество. Предварительно сортируйте, но используйте пересечение подмножества в качестве порогового условия. Если пересечение подмножествa > n%, то завершите пересечение, иначе откажитесь. n затем становится обратным вашему уровню комфорта с перспективой ложного позитива.

Вы также можете отсортировать по пересечениям подмножества (m), рассчитанным ранее, и начать выполнение полного пересечения, упорядоченного по m по убыванию. Таким образом, предположительно большинство ваших высоких пересечений m, вероятно, пересекут ваш k-порог на полном подмножестве, и вероятность попадания вашего k-порога будет постоянно уменьшаться.

Это действительно начинает рассматривать проблему как NP-Complete.