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

我有大量的用户id（整数），可能有数百万。这些用户都属于不同的组（整数集），因此大约有1000万个组。
为了简化我的示例并了解其本质，我们假设所有组都包含20个用户id。
我想找到所有的整数集的交集大于等于15的对。
我应该比较每一组吗？（如果我保留一个将用户id映射到设置成员身份的数据结构，这是不必要的。）最快的方法是什么？也就是说，我的底层数据结构应该用来表示整数集吗？排序集，未排序---散列有什么帮助吗？我应该用什么算法来计算集合交集呢？我更喜欢与C/C++（特别是STL）相关的答案，但也欢迎任何更一般的算法洞察力。
更新
另外，请注意，我将在共享内存环境中并行运行这个程序，因此最好使用干净地扩展到并行解决方案的思想。
另外，请注意，绝大多数集合对的交集大小为0，这意味着使用将用户id映射到集合的数据结构可能有利于避免计算每对集合的交集。

最佳答案

我会按照你的建议做：将用户映射到他们的组。也就是说，我会为每个用户保留一个组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 )中运行的组的简单成对比较快得多。

关于algorithm - 查找高交集的最快算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2697183/