我的数据基本上由大量数字集合组成。这些集合中的数字数量可以从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.) 数据不会改变。它们都是在一长串运行中获取的(每个运行分成2GB文件)。
2.) 至于存储空间。原始数据占用大约250GB。我估计,在处理和剥离了许多我不感兴趣的冗余元数据后,我可以将其缩小到36至48GB,具体取决于我决定保留多少元数据(没有索引)。此外,如果在数据的初始处理过程中我遇到足够多的相同集合,我可能可以通过为重复事件添加计数器而不是简单地反复重复事件来进一步压缩数据。
3.) 在处理的每个数据集中,每个数字至少包含两个数字:14位用于数据本身(检测能量),7位用于元数据(探测器编号)。因此,每个数字至少需要三个字节。
4.) 我之前的“尽管在99.9%的数据集中,n小于15”的评论是有误导性的。通过初步查看一些数据块,我发现有些数据集包含多达22个数字,但中位数为每组5个数字,平均数为每组6个数字。
5.) 尽管我喜欢构建文件指针索引的想法,但我还是有点担心,因为对于涉及多个数字的请求,我需要执行相对较慢的任务(至少我认为它很慢),即查找所有列表共同的指针集合,即查找给定数量集合的最大公共子集。
6.) 就我可用的资源而言,在将原始数据存储到系统后,我可以调动约300 GB的空间(该系统上剩余的配额)。该系统是一台双处理器服务器,配备2个四核AMD Opterons和16 GB内存。
7.) 是的,0可能出现,这是数据采集系统的一个产物,但它确实可能出现。