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

Question

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

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

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

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

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

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

Answer 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).

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

Кандидатами на вашу проблему являются VP-дерево и M-деревья.

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

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