有效的集合交集 - 决定交集是否大于k

Question

我遇到了一个问题,我必须计算集合中所有对之间的交叉点.这些集合都不小于小常数k,并且我只关心两个集合是否具有大于k -1元素的交集.我不需要实际的交叉点和确切的大小,只需要它是否大于k -1.是否有一些聪明的预处理技巧或整齐的交集算法可以用来加快速度？

更多信息可用于回答问题:

• 这些集合表示大的无向稀疏图中的最大集团.集合的数量可以是数万或更多,但是大多数集合可能很小.
• 这些集合已经是每个集合的成员按递增顺序排列.实际上它们是排序列表 - 我从底层库中以这种方式接收它们以进行最大集团搜索.
• 关于集合中元素的分布(即它们是否是紧密团块),我们都不知道.
• 大多数设置交叉点可能都是空的,因此理想的解决方案是一个聪明的数据结构,可以帮助我减少必须设置的交叉点的数量.

Answer 1

一种可能的优化,每个集合中包含的值范围越小,效果越有效:

• 创建一个所有集合的列表,按其第k个最大元素排序(这很容易找到,因为您已经按顺序拥有了每个集合的元素).叫这个清单L.
• 对于任何两个集合A和B,如果A中的第k个最大元素小于B中的最小元素,则它们的交集不能具有k个元素.
• 因此,对于每个集合依次计算其交集仅与L的相关部分中的集合.

您可以使用相同的事实从计算任意两个集合的交集中提前退出 - 如果在其中一个集合中只剩下n-1个元素进行比较,并且到目前为止交叉点最多包含kn元素,则停止.上面的过程就是这个规则简单地应用于L中的所有集合,其中n = k,在我们查看集合B的最小元素和A的第k个最大元素的点处.

Answer 2

考虑将所有大小为k 的映射作为关键字以及集合中包含密钥作为子集的所有集的列表的相应值的映射.给定此映射,您不需要执行任何相交测试:对于每个键,列表中的所有对集将具有至少为k的大小的交集.这种方法可以多次生成同一对集合,因此需要进行检查.

映射很容易计算.对于集合中的每个集合,计算所有size-k子集并将原始集合附加到该密钥集的列表中.但这实际上更快吗？一般来说,没有.这种方法的性能取决于集合中集合的大小分布和k的值.在集合中有d个不同的元素,你可以选择多个d键,这可能非常大.

但是,基本思想可用于减少交叉点的数量.不使用大小为k的集合,而是使用固定大小为q的较小的密钥作为密钥.这些值再次列出了将密钥作为子集的所有集合.现在,从交叉列表中测试每对集合.因此,在q = 1的情况下,您只测试那些至少有一个共同元素的集合对,q = 2您只测试那些至少有两个共同元素的集合,依此类推.我认为,q的最佳值将取决于集合大小的分布.

对于有问题的集合,一个好的选择可能是q = 2.然后,键只是图形的边缘,为映射提供可预测的大小.由于大多数集合预计是不相交的,因此q = 2应该消除大量的比较而没有太多额外的开销.