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

У меня есть большая коллекция из нескольких миллионов наборов, C. Элементы моих наборов происходят из вселенной из примерно 2000 возможных элементов. Мне нужно знать, что для заданного множества s, которое установлено в C, имеет наибольшее пересечение с s? (Или k множеств в C с k-наибольшими пересечениями). Я буду выполнять многие из этих запросов, последовательно, для разных s.

Я знаю, что очевидный способ сделать это - просто перебрать все точки в C и вычислить пересечение и взять max. Существуют ли какие-либо интеллектуальные структуры данных/трюки программирования, которые могут ускорить мой поиск? Было бы здорово, если бы я мог сделать это быстрее, чем O (C).

ИЗМЕНИТЬ: приблизительные ответы тоже будут в порядке.

Ответ 1

Я не думаю, что есть умная структура данных, которая поможет с асимптотической производительностью. Но это идеальная проблема с уменьшением карты. GPGPU будет хорошо. Для юниверса из 2048 элементов набор как растровое изображение составляет всего 256 байт. 4 миллиона - это всего лишь гигабайт. Даже скромная спецификация Nvidia имеет это. Например. программирование в CUDA, вы должны скопировать C в ОЗУ графической карты, отобразить кусок гигабайта на каждый ядро графического процессора для поиска, а затем уменьшить количество ядер чтобы найти окончательный ответ. Это должно быть порядка нескольких миллисекунд. Не достаточно быстро? Просто купите более горячее оборудование.

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

Ответ 2

Один простой трюк состоит в том, чтобы отсортировать список наборов C в порядке убывания по размеру, а затем выполнить тесты пересечения грубой силы, как обычно. Когда вы идете вперед, следите за множеством b с самым большим перекрестком. Если вы найдете набор, пересечение которого с набором запросов s имеет размер | s | (или, что то же самое, имеет пересечение, равное s - используйте любое из этих тестов быстрее), вы можете немедленно остановить и вернуть его, поскольку это наилучший ответ. В противном случае, если следующий набор из C имеет меньше, чем | b | элементов, вы можете немедленно остановить и вернуть b. Это можно легко обобщить на поиск совпадений верхнего k.

Ответ 3

Я не вижу никакого способа сделать это менее чем за O (C) для каждого запроса, но у меня есть некоторые идеи о том, как максимизировать эффективность. Идея состоит в том, чтобы создать таблицу поиска для каждого элемента. Если некоторые элементы являются редкими, а некоторые являются общими, вы можете иметь положительные и отрицательные таблицы поиска:

s[i] // your query, an array of size 2 thousand, true/false
sign[i] // whether the ith element is positive/negative lookup. +/- 1
sets[i] // a list of all the sets that the ith element belongs/(doesn't) to

query(s):
  overlaps[i] // an array of size C, initialized to 0's
  for i in len(s):
    if s[i]:
      for j in sets[i]:
        overlaps[j] += sign[i]

  return max_index(overlaps)

Особенно, если многие из ваших элементов имеют самые разные вероятности (как вы сказали), этот подход должен сэкономить вам некоторое время: очень редко или очень общие элементы могут быть рассмотрены почти мгновенно.

Для дальнейшей оптимизации: вы можете сортировать структуру так, чтобы сначала обрабатывались элементы, наиболее распространенные/наиболее редкие. После того, как вы сделали первый, например, 3/4, вы можете сделать быстрый проход, чтобы увидеть, находится ли ближайший набор соответствия до того, как он будет установлен следующий набор, который не нужно продолжать, хотя опять же, стоит ли это, зависит от деталей вашего распределения данных.

Еще одно уточнение: сделайте sets [i] одной из двух возможных структур: если элемент очень редок или распространен, sets [i] - это просто список наборов, в которых i-й элемент находится в/не в. Однако, предположим, что i-й элемент находится в половине множеств. Тогда наборы [i] - это всего лишь список индексов наполовину, если количество наборов, проходящих через него и увеличивающих перекрытия, является расточительным. Иметь третье значение для знака [i]: если знак [i] == 0, то i-й элемент относительно близок к 50% общности (это может означать только от 5% до 95% или что-то еще), а вместо список наборов, в котором он появляется, он будет просто массивом из 1 и 0 с длиной, равной C. Затем вы просто добавите массив целиком к перекрытиям, которые будут быстрее.

Ответ 4

Поместите все свои элементы из миллиона наборов в Hashtable. Ключ будет элементом, значением будет набор индексов, указывающих на содержащий набор.

HashSet<Element>[] AllSets = ...

// preprocess
Hashtable AllElements = new Hashtable(2000);
for(var index = 0; index < AllSets.Count; index++) {
    foreach(var elm in AllSets[index]) {
        if(!AllElements.ContainsKey(elm)) { 
            AllElements.Add(elm, new HashSet<int>() { index });
        } else {
            ((HashSet<int>)AllElements[elm]).Add(index);
        }
    }
}

public List<HashSet<Element>> TopIntersect(HashSet<Element> set, int top = 1) {
    // <index, count>
    Dictionar<int, int> counts = new Dictionary<int, int>();
    foreach(var elm in set) {
        var setIndices = AllElements[elm] As HashSet<int>;
        if(setIndices != null) {
           foreach(var index in setIndices) {
               if(!counts.ContainsKey(index)) {
                   counts.Add(index, 1);
               } else {
                   counts[index]++;
               }
           } 
        }
    }
    return counts.OrderByDescending(kv => kv.Value)
        .Take(top)
        .Select(kv => AllSets[kv.Key]).ToList();
}