高效集合交集 - 判断交集是否大于k

Question

我面临一个问题，需要计算一组集合中所有成对集合之间的交集。其中任何一个集合都不小于一个小常数k，并且我只对两个集合是否有一个大于k-1个元素的交集感兴趣。我不需要实际的交集或确切大小，只需要知道它是否大于k-1。是否有一些巧妙的预处理技巧或漂亮的集合交集算法可以加速处理？

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

- 集合表示大型无向稀疏图中的极大团。集合数量可能达到数万个或更多，但大多数集合可能很小。 - 集合已排序，每个集合成员按递增顺序排列。它们实际上是排序列表-我从用于查找最大团的底层库中以这种方式接收它们。 - 不知道集合中元素的分布情况（即它们是否紧密聚集在一起）。 - 大多数集合交集可能为空，因此理想的解决方案是一个巧妙的数据结构，帮助我减少必须进行的集合交集数。

- Tamás

---

每个集合的内容本质上是随机的吗？如果不是，也许您可以按其最大元素对左侧的集合排序，并按其最小元素对右侧的集合排序，从而避免考虑许多空交集。如果大多数集合包含附近值的团块，则此方法将非常有效，但如果大多数集合都包含最小和最大可能的元素，则效果会非常差... - Steve Jessop

在比较两个集合时，任意将其中一个称为“左侧”，另一个称为“右侧”。 - Steve Jessop

@Steve Jessop：我也鼓励你把你的解决方案发布为答案，尤其是现在这个问题上有一个开放性赏金。你写的内容实际上给了我一个想法；在计算交集之前，我将查找每个集合的最小和最大元素，并使用它们来提前退出，如果所考虑的两个集合是不相交的话。 - Tamás

“the sets are already sorted”是什么意思？你是指可以枚举这些集合并对这些枚举进行排序，还是指集合成员可以被枚举并且你已经对所有集合的成员进行了排序？你使用了什么样的枚举方式？ - Sjoerd C. de Vries

我已经将每个集合的成员按递增顺序排序。实际上，每个集合都可以被视为一个排序列表，并且可以使用有序序列的朴素交集算法在线性时间内相交任何两个集合。 - Tamás

Answer 1

一种可能的优化方法，其效果取决于每个集合中值的范围大小：

• 创建一个按它们第k大元素排序的所有集合列表（这很容易找到，因为您已经有了每个集合及其元素的顺序）。将此列表命名为L。
• 对于任何两个集合A和B，如果A中第k大的元素小于B中最小的元素，则它们的交集不能有多达k个元素。
• 因此，依次计算每个集合与L中相关部分的集合的交集。

您可以使用同样的事实提前退出计算任意两个集合的交集-如果在其中一个集合中只剩下n-1个要比较的元素，并且迄今为止交集最多包含k-n个元素，则停止。上述过程只是将此规则应用于L中的所有集合，当我们查看集合B的最小元素和集合A的第k大元素时，n=k。

- Steve Jessop

---

这个很好用；我成功地将我那个不太天真的实现从7.61秒（对于20000个团）降低到了5.8秒；每次都进行了三次试验，这些时间是最好的。我正在调查其他提出的解决方案，但这个真的很有前途（而且简单）。 - Tamás

Answer 2

考虑一个mapping，其中所有大小为k的集合作为键，相应值为包含该键作为子集的集合列表。给定此映射，您无需执行任何交集测试：对于每个键，列表中的所有集合对将具有至少k个交集。这种方法可能会多次产生相同的一对集合，因此需要检查。

计算映射很容易。对于集合中的每个集合，计算所有大小为k的子集，并将原始集合附加到该键集的列表中。但是这实际上更快吗？一般来说，不是。此方法的性能将取决于集合中集合大小的分布和k的值。对于集合中的d个不同元素，您可以拥有多达d个选择k键，这可能非常大。

然而，基本思想可用于减少交集的数量。不使用大小为k的集合，而是使用固定大小q的较小集合作为键。值再次为具有该键为子集的所有集合的列表。现在，测试列表中每对集合的交集。因此，当q=1时，您仅测试具有至少一个共同元素的集合对，当q=2时，您仅测试具有至少两个共同元素的集合对，依此类推。我认为，最佳的q值将取决于集合大小的分布。

对于所讨论的集合，q=2可能是一个不错的选择。然后，键只是图的边缘，为映射提供了可预测的大小。由于大多数集合预计是不相交的，因此q=2应该消除了很多比较，而没有太多额外的开销。

- Michael J. Barber

---

最后，我终于有时间来实现和测试这个版本，结果证明它是迄今为止发布的所有解决方案中速度最快的。对于20K个圆孔，它比亚军快了近10倍。 - Tamás

Answer 3

以下策略应该非常有效。我已经在许多情况下使用了这种变体来相交升序序列。

首先，我假设您有某种优先队列可用（如果没有，自己编写堆很容易）。还有快速的键/值查找（btree、哈希等）。

有了这些条件，下面是一个伪代码算法，应该可以高效地完成您想要的操作。

# Initial setup
sets = array of all sets
intersection_count = key/value lookup with keys = (set_pos, set_pos) and values are counts.
p_queue = priority queue whose elements are (set[0], 0, set_pos), organized by set[0]

# helper function
def process_intersections(current_sets):
    for all pairs of current_sets:
        if pair in intersection_count:
            intersection_count[pair] += 1
        else:
            intersection_count[pair] = 1

# Find all intersections
current_sets = []
last_element = first element of first thing in p_queue
while p_queue is not empty:
    (element, ind, set_pos) = get top element from p_queue
    if element != last_element:
        process_intersections(current_sets)
        last_element = element
        current_sets = []
    current_sets.append(set_pos)
    ind += 1
    if ind < len(sets[set_pos]):
        add (sets[set_pos][ind], ind, set_pos) to p_queue
# Don't forget the last one!
process_intersections(current_sets)

final answer = []
for (pair, count) in intersection_count.iteritems():
    if k-1 < count:
        final_answer.append(pair)

运行时间将是O(集合大小之和 * log(集合数量) + 点在一对集合中出现的次数)。特别注意，如果两个集合没有交集，您永远不会尝试对它们进行交集运算。

- btilly

---

如果可以的话，我会给这个点赞两次；昨天我成功地在C++中实现了它，速度非常快。我会在一天左右发布一些基准测试结果。 - Tamás

Answer 4

如果你使用预测子集作为初步筛选器，会怎样呢？预先排序，但使用子集交集作为阈值条件。如果子集交集> n％，则完成交集，否则放弃。n然后成为您对误判的可能性舒适水平的倒数。

您还可以按早期计算的子集交集(m)进行排序，并开始运行按m降序排序的完整交集。因此，您最高的m交集中的大多数可能会跨越全子集的k阈值，并且达到k阈值的可能性将不断减少。

这确实开始将问题视为NP-Complete。

- Rikon