Самый быстрый алгоритм для нахождения наборов с высоким пересечением
У меня есть большое количество идентификаторов пользователей (целые числа), потенциально миллионы. Эти пользователи все принадлежат различным группам (наборы целых чисел), такой, что существует на порядке 10 миллионов групп.
Чтобы упростить мой пример и добраться до сущности его, давайте предположим, что все группы содержат 20 идентификаторов пользователей.
Я хочу найти всех пар целочисленных наборов, которые имеют пересечение 15 или больше.
Я должен сравнить каждую пару наборов? (Если я сохраняю структуру данных, которая отображает идентификаторы пользователей для установки членства, это не было бы необходимо.), Что самый быстрый путь состоит в том, чтобы сделать это? Таким образом, чем моя базовая структура данных должна быть для представления целочисленных наборов? Отсортированные наборы, неотсортированный---хеширование может так или иначе помочь? И какой алгоритм я должен использовать для вычислений пересечения набора)? Я предпочитаю ответы, которые связывают C/C++ (особенно STL), но также и больше общее, алгоритмическое понимание приветствуется.
Обновление кроме того, обратите внимание, что я буду выполнять это параллельно в среде общей памяти, таким образом, идеи, которые чисто расширяются на параллельное решение, будут предпочтены.
Кроме того, обратите внимание, что у подавляющего большинства пар набора будет перекрестный размер 0---, означающего, что могло бы быть выгодно использовать структуру данных, которая отобразила идентификаторы пользователей на наборы, чтобы не вычислять пересечение каждой пары наборов.
4 ответа
Я бы сделал именно то, что вы предлагаете: сопоставил пользователей с их группами. То есть я бы вел список идентификаторов групп для каждого пользователя. Затем я бы использовал следующий алгоритм:
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) .
Если подавляющее большинство перекрестков равно 0, это означает, что количество непустых перекрестков относительно невелико. Попробуйте это:
- Выбросьте все наборы размером <15 перед тем, как начать
- Рассчитайте поиск по идентификатору пользователя -> список наборов, к которым он принадлежит
- Создайте
карту <пара <набор пользователей, userset>, int> - Для каждого пользователя увеличьте (после создания, если необходимо),
n * (n-1) / 2записей этой карты, где n - количество наборов, для которых пользователь принадлежит. - Когда это будет закончено, просканируйте карту на предмет записей, где значение больше 15.
Он будет использовать больше памяти, чем простой подход вычисления каждого перекрестка.Фактически, это столкнется с тем, что возможно: если каждый набор в среднем пересекается всего с 10 другими, возможно, на очень маленьких пересечениях, тогда карте требуется 50M записей, что начинает занимать много оперативной памяти. Это также прискорбно недружелюбно к кеш-памяти.
Это может быть быстрее, чем выполнение всех пересечений множеств, потому что члены O (n ^ 2) относятся к количеству непустых пересечений и количеству групп, к которым принадлежит каждый пользователь, а не к количеству наборы.
Распараллеливание нетривиально из-за разногласий на гигантской карте. Однако вы можете разделить это на карту для каждого потока и периодически давать одному потоку новую пустую карту и добавлять полученные на данный момент результаты в общие результаты. Затем различные потоки большую часть времени выполняются полностью независимо, каждому из которых предоставляется список пользователей для обработки.
Следует ли мне сравнивать каждую пару наборов? (Если я сохраню структуру данных, которая сопоставляет идентификаторы пользователей, чтобы установить членство, в этом не было бы необходимости.)
Чтобы подсчитать степень пересечения, вам все равно нужно посетить другие группы, которые есть у пользователя, которые все еще являются кубическими. У вас может быть хэш-таблица или другой разреженный массив для подсчета, но все равно в лучшем случае потребуется приращение для каждого пользователя для каждой пары групп, в которых находится каждый пользователь.Если у вас есть N пользователей в группах G со средним числом S пользователей на группу и 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 общих элементов имеет более очевидную оптимизацию.
- Если группы отсортированы, вам не требуется рабочая память, просто выведите степень различия между входными группами напрямую.
- Большинство обращений к памяти будут линейными в смежных областях памяти, и результаты зависят только от двух сравниваемых наборов, а не от суммирования по всему набору данных. Случайный доступ к основной памяти значительно медленнее, чем линейный доступ к ней.Случайное изменение основной памяти с помощью блокировки шины на порядки медленнее, чем доступ к кешу без необходимости блокировать шину (хотя, если у вас есть пара ГБ на ядро, вы можете использовать подход «пользователь-> группа» без необходимости выполнять какую-либо синхронизацию).
- Необходимо подсчитать только 5 элементов, которые различаются между наборами; если данные случайны, то большинство наборов не пересекаются, поэтому среднее количество посещаемых элементов меньше.
- Вы можете быстро сбрасывать со счетов определенные группы, рассматривая разницу как расстояние (если A на 11 отличается от B, а C на 5 отличается от B, тогда C на 6–16 отличается от A, поэтому может быть сброшен без сравнения A и C напрямую). Поскольку большинство наборов полностью не пересекаются, это не принесет вам многого.
Существует также вариант гибридного подхода, использующего карту «пользователь-> группа» для сокращения набора групп для сравнения групп, которые необходимо выполнить. Это имеет то преимущество, что не требует увеличения общей структуры данных:
- для каждой пары групп, в которых находится пользователь, добавьте эту пару в список для исследования.
- сортирует список пар групп, по крайней мере, с одним общим пользователем.
- количество раз, когда каждая пара встречается в списке, - это количество общих пользователей.
Использование сортировки слиянием позволяет распараллелить каждое из них на чистые потоковые блоки. Вы должны отсортировать примерно 20 * 200 * 10 миллионов / 2 = 20 миллиардов пар идентификаторов групп (каждая группа из 20 пользователей умножается на количество групп, в которых находится каждый пользователь / 2).
Один из способов - рассматривать вашу проблему как проблему метрического пространства радиуса поиска , где функция расстояния - это число не совпадающие записи и радиус r = max (количество элементов в наборах) - количество равных . Фильтрация найденных элементов необходима, чтобы увидеть, что в наборе достаточно значений. Поэтому, если кто-то не предложит метрическую функцию, которую можно использовать напрямую, это решение имеет множество ограничений.
Одной из структур данных для поиска по показателям является BK-Tree , которое можно использовать для поиска по сходству строк.
Кандидатами на решение вашей задачи являются VP-дерево и M-деревья.
Худший случай для дерева показателей - O (n ^ 2), когда вы ищете расстояние> m (максимальное количество элементов в наборах), когда вы строите дерево за O (log n * n) и поиск в O (n ^ 2).
Кроме того, фактическая сложность выполнения зависит от возможности обрезать поддеревья дерева показателей при выполнении поиска. В дереве показателей поддерево можно пропустить, если расстояние от опорного элемента до поискового элемента больше, чем радиус опорного элемента (который является, по крайней мере, максимальным расстоянием от предков до опорного элемента). Если ваши наборы записей довольно разобщены, в общем времени выполнения будет доминировать время построения дерева показателей O (log n * n).