问具有给定集合的集合中最大集合相交的算法/数据结构

EN

我不认为有一种聪明的数据结构可以帮助提高渐近性能。但这是一个完美的map reduce问题。GPGPU会做得很好。对于一个有2048个元素的世界来说，设置为位图只有256个字节。400万只是一个千兆字节。即使是中等规格的Nvidia也有这一点。例如，在CUDA编程中，你可以将C语言复制到显卡内存中，将千兆字节的一大块映射到每个图形处理器核心进行搜索，然后跨核心进行缩减以找到最终答案。这应该只需要几毫秒的时间。还不够快？就买下hotter hardware吧。

如果你按照这些思路重新表达你的问题，你可能会从这类编程的专家那里得到答案，而我不是。

一个简单的技巧是按大小按降序对集合C的列表进行排序，然后像往常一样继续进行暴力相交测试。在你前进的过程中，跟踪到到目前为止具有最大交集的集合b。如果您发现一个集合与查询集合s的交集的大小为|s| (或者等价地，具有等于s的交集--使用这些测试中较快的一个)，您可以立即停止并返回它，因为这是可能的最佳答案。否则，如果C中的下一个集合的元素少于| b |个，您可以立即停止并返回b。这可以很容易地推广到查找前k个匹配。

我看不到任何方法可以在每个查询少于O(C)的情况下做到这一点，但我有一些关于如何最大化效率的想法。这个想法基本上是为每个元素建立一个查找表。如果有些元素是稀有的，有些是常见的，您可以使用正向查找表和负向查找表：

s[i] // your query, an array of size 2 thousand, true/false
sign[i] // whether the ith element is positive/negative lookup. +/- 1
sets[i] // a list of all the sets that the ith element belongs/(doesn't) to

query(s):
  overlaps[i] // an array of size C, initialized to 0's
  for i in len(s):
    if s[i]:
      for j in sets[i]:
        overlaps[j] += sign[i]

  return max_index(overlaps)

特别是如果您的许多元素具有非常不同的概率(如您所说)，这种方法应该会为您节省一些时间:非常罕见或非常常见的元素几乎可以立即处理。

为了进一步优化:您可以对结构进行排序，以便首先处理最常见/最罕见的元素。在你完成了第一个，例如3/4之后，你可以做一个快速遍历，看看最接近的匹配集是否比下一个集领先太多，以至于没有必要继续，尽管这是否值得取决于你的数据分布的细节。

还有另一种改进:使setsi成为两种可能的结构之一:如果元素非常稀有或常见，则setsi只是第i个元素所在/不在的集合的列表。然而，假设第i个元素在集合的一半中。那么setsi只是一个索引列表，长度是集合数量的一半，循环遍历它并增加重叠是浪费的。为signi设置第三个值:如果signi ==为0，那么第i个元素相对接近50%的共性(这可能意味着在5%到95%之间，或者其他任何东西)，而不是它出现的集合列表，它将只是长度等于C的1和0的数组。然后，您可以将整个数组添加到重叠中，这样会更快。