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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 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). В частности, обратите внимание, что если два набора не имеют пересечения, вы никогда не пытаетесь пересечь их.

Answer 4

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

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

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