查找具有特定子集的集合

Question

我是一名物理学研究生，我正在编写一些代码来对数百on的数据进行排序，并在我请求时返回这些数据的切片。这里是诀窍，我知道没有好的方法来排序和搜索这种数据。

我的数据基本上是由大量的数字集组成的。这些集合中可以包含从1到n的任何数字(尽管在99.9%的集合中，n小于15)，并且大约有15~20亿个这样的集合(不幸的是，这种大小排除了暴力搜索)。

我需要能够指定一个包含k个元素的集合，并将包含指定子集的每个包含k+1元素或更多元素的集合返回给我。

简单的例子：

假设我的数据集如下：

(1,2,3)

(1,2,3,4,5)

(4,5,6,7)

(1,3,8,9)

(5,8,11)

如果我给出请求(1,3)，我会得到以下集合：(1,2,3)，(1,2,3,4,5)和(1,3,8,9)。

请求(11)将返回集合：(5,8,11)。

请求(1,2,3)将返回集合：(1,2,3)和(1,2,3,4,5)

请求(50)将不返回任何集合：

到目前为止，模式应该是清晰的。这个例子和我的数据之间的主要区别是，包含我的数据的集合更大，集合中每个元素使用的数字从0到16383 (14位)，并且还有更多的集合。

如果重要的话，我正在用C++写这个程序，虽然我也知道java，c，一些汇编，一些fortran和一些perl。

有谁有任何关于如何完成这件事的线索吗？

编辑：

要回答几个问题并添加几点：

1.)数据不会更改。这一切都是在一组长长的运行中拍摄的(每个运行被分成2个gig文件)。

2.)至于存储空间。原始数据大约占用250 up。我估计，在处理和剥离了许多我不感兴趣的无关元数据之后，我可以根据我决定保留多少元数据(没有索引)，将其减少到36到48 on。此外，如果在我最初处理数据时遇到足够多相同的集合，我也许能够通过为重复事件添加计数器来进一步压缩数据，而不是简单地一遍又一遍地重复事件。

3.)经过处理的集合中的每个数字实际上包含至少两个数字，14位用于数据本身(检测到的能量)和7位用于元数据(检测器编号)。所以我需要每个数字至少三个字节。

4.)我的“尽管在99.9%的集合中，n小于15”的评论具有误导性。在初步浏览一些数据块时，我发现我的集合包含多达22个数字，但中位数是每个集合5个数字，平均是每个集合6个数字。

5.)虽然我喜欢在文件中建立一个指针索引的想法，但我有点怀疑，因为对于涉及多个数字的请求，我要做的是半缓慢的任务(至少我认为它很慢)，那就是寻找列表中所有公共指针的集合，即找到给定数量的集合的最大公共子集。

6.)就我可用的资源而言，在系统上有原始数据(该系统上配额的剩余部分)后，我可以收集大约300 In的空间。该系统是一个双处理器服务器，具有2个四核和opteron以及16 of的ram。

7.)是的，可以发生0，当它发生时，它是数据采集系统的伪像，但它也可能发生。

Answer 1

我最近发现了使用空间填充曲线将多维数据映射到单维的方法。然后，可以基于数据的一维索引对数据进行索引。通过找到与表示曲线的框相交的曲线的线段，然后检索这些线段，可以很容易地执行范围查询。

我认为，这种方法比建议的疯狂索引要好得多，因为在查看之后，索引将与我希望存储的数据一样大，这几乎不是一件好事。关于这一点的更详细的解释可以在：

http://www.ddj.com/184410998

和

http://www.dcs.bbk.ac.uk/~jkl/publications.html

Answer 2

你的问题和搜索引擎面临的问题是一样的。“我有一大堆文档。我需要那些包含这组单词的文档。”您只需要(非常方便地)使用整数而不是单词，以及较小的文档。解决方案是inverted index。Manning等人的Introduction to Information Retrieval (在该链接上)可以在线免费获得，可读性很强，并将详细介绍如何做到这一点。

您将不得不在磁盘空间上付出代价，但它可以并行化，并且一旦构建了索引，它的速度应该足以满足您的计时要求。

Answer 3

假设随机分布为0-16383，每个集合具有一致的15个元素，20亿个集合，每个元素将出现在大约180万个集合中。您是否考虑过(以及您是否有能力)构建一个16384x~1.8M (30B条目，每个条目4字节)的查找表？给定这样一个表，您可以查询哪些集合包含(1)、(17)和(5555)，然后找到这三个1.8M元素列表的交集。