algorithm - 查找具有高交集的集合的最快算法

Question

我有大量的用户 ID(整数)，可能有数百万。这些用户都属于不同的组(整数集)，因此有大约 1000 万个组。

为了简化我的示例并了解它的本质，我们假设所有组都包含 20 个用户 ID。

我想找到所有具有 15 或更大交集的整数集对。

我应该比较每对集合吗？ (如果我保留将用户 ID 映射到设置成员资格的数据结构，则没有必要这样做。)执行此操作的最快方法是什么？也就是说，我的底层数据结构应该是什么来表示整数集？已排序的集合，未排序的——散列可以以某种方式帮助吗？我应该使用什么算法来计算集合交集)？我更喜欢与 C/C++(尤其是 STL)相关的答案，但也欢迎任何更一般的算法见解。

更新另外，请注意，我将在共享内存环境中并行运行它，因此首选完全扩展到并行解决方案的想法。

另外，请注意绝大多数集合对的交集大小为 0——这意味着使用将用户 ID 映射到集合的数据结构以避免计算每对集合的交集可能是有利的的集合。

Answer 1

我会完全按照您的建议进行:将用户映射到他们的组。也就是说，我会为每个用户保留一个组 ID 列表。然后我会使用以下算法:

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) 中运行的组的简单成对比较快得多。