Самый быстрый алгоритм поиска множеств с высоким пересечением

У меня есть большое количество идентификаторов пользователей (целые числа), что потенциально миллионы. Все эти пользователи принадлежат к различным группам (наборам целых чисел), таким образом, что они составляют порядка 10 миллионов групп.

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

Я хочу найти все пары целых множеств, которые имеют пересечение 15 или больше.

Следует ли сравнивать каждую пару множеств? (Если я сохраняю структуру данных, которая сопоставляет идентификаторы пользователей для установки членства, это не обязательно.) Каков самый быстрый способ сделать это? То есть, какова должна быть моя базовая структура данных для представления целых наборов? Сортированные наборы, несортированные --- может хеширование как-то помочь? И какой алгоритм я должен использовать для вычисления набора пересечений)? Я предпочитаю ответы, относящиеся к C/С++ (особенно STL), но также приветствуются любые общие, алгоритмические идеи.

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

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

Ответ 1

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

foreach group:
  map = new Map<Group, int>  // maps groups to count
  foreach user in group:
    foreach userGroup in user.groups:
      map[userGroup]++
      if( map[userGroup] == 15 && userGroup.id > group.id )
        largeIntersection( group, userGroup )

Учитывая, что у вас есть G группы, каждый из которых содержит U пользователей в среднем, и учитывая, что эти пользователи в среднем относятся к G группам, то это будет работать в O( G*U*g ). Что, учитывая вашу проблему, вероятно, намного быстрее, чем наивное попарное сравнение групп, которое работает в O(G*G*U).

Ответ 2

Если подавляющее большинство пересечений равно 0, это означает, что число непустых пересечений относительно невелико. Попробуйте:

Перед тем, как начать, отбросьте все наборы размера < 15.
Вычислите свой поиск из userid → списка наборов, к которым он принадлежит.
Создайте map<pair<userset, userset>, int>
Для каждого пользователя приращение (после создания при необходимости), n*(n-1)/2 записей этой карты, где n - количество наборов, к которым принадлежит пользователь.
Когда это будет завершено, просмотрите карту для записей, где значение больше 15.

Он будет использовать больше памяти, чем простой подход к вычислению каждого пересечения. Фактически, это будет противостоять тому, что возможно: если каждый набор в среднем пересекает только 10 других, возможно, в очень маленьких пересечениях, тогда для карты требуется 50 М записей, которая начинает много ОЗУ. Это также ужасно кэш-недружелюбно.

Это может быть быстрее, чем выполнение всех пересечений множеств, поскольку термины O (n ^ 2) относятся к числу непустых пересечений и количеству групп, к которым принадлежит каждый пользователь, а не к числу множества.

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

Ответ 3

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

Чтобы подсчитать степень пересечения, вам все равно нужно посетить другие группы, которые есть у пользователя, которые по-прежнему кубируются. У вас может быть хеш-таблица или другой разреженный массив для подсчета, но в лучшем случае это потребует инкремента для каждого пользователя для каждой пары групп, в которой находится каждый пользователь. Если у вас есть N пользователей в группах G, в среднем по S-пользователей за группа и количество T групп, в которых находится каждый пользователь, у вас есть GGS/2 для сравнения каждой пары групп и NTT, если у вас есть индекс пользователя для группировки. T = GS/N, поэтому NTT = GGSS/N; для S = 20 и N в миллионах должно быть преимущество. К сожалению, для подсчета пересечений (25 ТБ или около того для 4-разрядного нерезкого счетчика) требуется также, по крайней мере, хранилище G * G, и необходимо обеспечить параллельное наращивание структуры.

Для миллиона пользователей в 10 миллионов групп из 20, примерно с вероятностью, что пользователь находится в данной группе, это 2e-6, а вероятность того, что две группы будут делиться пользователями, будет 40e-6, поэтому 25TB приходит до 1 ГБ данных, что не является невозможным для разреженного массива на обычном компьютере.

Однако сравнение 20 элементов для 15 общих элементов имеет более очевидную оптимизацию

Если группы отсортированы, вам не требуется рабочее хранилище, просто введите степень разницы между группами ввода напрямую.
Большинство обращений к памяти будут линейными в смежных областях памяти, и результаты зависят только от двух сравниваемых наборов, вместо того, чтобы полагаться на суммирование по всему набору данных. Доступ к основной памяти случайным образом значительно медленнее, чем доступ к ней линейно. Случайное изменение основной памяти с помощью блокировок на шине на несколько порядков медленнее, чем доступ к кешу, без необходимости блокировки шины (хотя, если у вас есть несколько ГБ на ядро, вы можете использовать групповой подход user- > без какой-либо синхронизации).
Нужно только подсчитать 5 элементов, которые различаются между наборами; если данные случайны, то большинство наборов будут непересекающимися, поэтому среднее число посещенных элементов меньше.
Вы можете быстро скидывать определенные группы, рассматривая разницу как расстояние (если A отличается от B на 11, а C 5 отличается от B, тогда C находится между 6 и 16 отличными от A, поэтому можно сбрасывать со счетов без сравнения A и C). Поскольку большинство множеств полностью не пересекаются, это не принесет вам многого.

Существует также вариант гибридного подхода, используя карту user- > group, чтобы обрезать набор групп для сравнения групп. Это имеет то преимущество, что не требует увеличения общей структуры данных:

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

Используя сортировку слияния, каждый из них должен распараллеливаться в чистые потоковые единицы. Вы бы сортировали около 20 * 200 * 10 миллионов /2 = 20 миллиардов пар идентификаторов группы (каждая группа из 20 пользователей умножает количество групп, в которых каждый пользователь находится в/2).

Ответ 4

Один из способов - увидеть вашу проблему как метрическое пространство поиск радиуса, где функция расстояния - это количество несоответствующих записей и радиус r = max(number of elements in sets) - number of equal. Фильтрация найденных элементов необходима, чтобы увидеть, что в наборе достаточно значений. Поэтому, если кто-то не придумает метрическую функцию, которая может быть использована напрямую, эти решения должны иметь большие ограничения.

Одной из структур данных для метрического поиска является BK-Tree, который может использоваться для поиска сходства строк.

Кандидаты на вашу проблему - это VP-tree и M-Trees.

В худшем случае для метрического дерева O (n ^ 2), когда вы ищете расстояние > m (максимальное количество элементов в наборах) при создании дерева в O (log n * n) и искать в O (n ^ 2).

Кроме того, фактическая сложность выполнения зависит от возможности отсечения поддеревьев метрического дерева при выполнении поиска. В дереве метрик поддерево может быть пропущено, если расстояние от поворотного элемента до элемента поиска больше, чем радиус элемента поворота (который является, по меньшей мере, максимальным расстоянием от предка до элемента поворота). Если ваши наборы записей довольно дизъюнктивны, общее время выполнения будет определяться временем нарастания дерева показателей O (log n * n).