查找具有特定子集的集合

StackOverflow https://stackoverflow.com/questions/494502

  •  20-08-2019
  •  | 
  •  

题

我是一名物理学研究生，我正在编写一些代码来对数百GB的数据进行排序，并在我需要时返回该数据的切片。这是技巧，我不知道有什么好的方法来排序和搜索此类数据。

我的数据本质上由大量数字组成。这些集合可以包含 1 到 n 个数字（尽管在 99.9% 的集合中，n 小于 15），并且这些集合大约有 1.5 ~ 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 个演出文件）。

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

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

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

5.）虽然我喜欢在文件中构建指针索引的想法，但我有点怀疑，因为对于涉及多个数字的请求，我留下了查找集合的半慢速任务（至少我认为它很慢）列表共有的所有指针，即找到给定数量的集合的最大公共子集。

6.) 就我可用的资源而言，在系统上拥有原始数据后，我可以聚集大约 300 GB 的空间（该系统上剩余的配额）。该系统是一个双处理器服务器，具有 2 个四核 amd opterons 和 16 GB 内存。

7.) 是 0 可能会发生，它是数据采集系统的产物，但它可能会发生。

有帮助吗？

解决方案 4

我最近发现，使用空间填充曲线多维数据映射到一个单一的尺寸的方法。人们可以那么指数基于其1D索引的数据。范围查询可以通过寻找相交，表示曲线的框曲线的段，然后检索这些段可以容易地进行。

我认为，这个方法看它以后，因为是远远优于使疯狂指标的建议，该指数将是我希望来存储数据，几乎没有一个好东西一样大。这方面的一个稍微更详细的说明，可以发现：

http://www.ddj.com/184410998 结果 和结果 http://www.dcs.bbk.ac.uk/~jkl/ publications.html

其他提示

您的问题是相同的所面临的搜索引擎。 “我有一个bajillion的文件。我需要包含这个词的集合的人。”你只需要（很方便），整数代替文字，和短小的文件。该解决方案是一种反向索引。 现代信息检索通过Manning等是（在该链接）提供的免费在线，是非常具有可读性，并且将进入一个关于如何做到这一点很多细节。

你将不得不支付磁盘空间的价格，但它可以被并行化，应该比足够快，以满足您的时序要求，一旦该指数构建多。

假设0-16383的随机分布，每个组一致的15种元素，以及两个十亿集，各元素将出现在大约1.8M集。你有没有考虑过（并且你有能力）建设16384x〜1.8M（30B项目，4个字节每个）查找表？鉴于这样的表，可以查询其设定包含（1）和（17）和（5555），然后找到这三个〜1.8M-元件列表的交叉点。

我的猜测如下。

假设每个集合都有一个名称或 ID 或地址（如果只有 20 亿个集合，则 4 字节数字即可）。

现在遍历所有集合一次，并创建以下输出文件：

  • 包含所有包含“1”的集合的 ID 的文件
  • 包含所有包含“2”的集合的 ID 的文件
  • 包含所有包含“3”的集合的 ID 的文件
  • ...ETC ...

如果每组有 16 个条目，那么平均每个 2^16 个文件将包含 2^20 个组的 ID；每个 ID 为 4 字节，这将需要 2^38 字节 (256 GB) 的存储空间。

在处理请求之前，您将执行上述一次。

当您收到请求时，请按如下方式使用这些文件：

  • 查看请求中的几个数字
  • 打开几个相应的索引文件
  • 获取这两个文件中存在的所有集合的列表（每个文件中只有一百万个 ID，所以这应该不难）
  • 查看这几个集合中的哪一个满足请求的其余部分

我的猜测是，如果您执行上述操作，创建索引将（非常）慢，而处理请求将（非常）快。

创建 16383 个索引文件，每个可能的搜索值一个。对于输入集中的每个值，将该集开头的文件位置写入相应的索引文件中。重要的是，每个索引文件包含同一组的相同编号。现在，每个索引文件将由主文件中的升序索引组成。

要进行搜索，请开始读取与每个搜索值对应的索引文件。如果您读取的索引低于从另一个文件读取的索引，请丢弃它并读取另一个文件。当您从所有文件中获得相同的索引时，即为匹配 - 从主文件中获取该集，并从每个索引文件中读取新索引。一旦到达任何索引文件的末尾，就完成了。

如果您的值均匀分布，则每个索引文件将包含 1/16383 的输入集。如果您的平均搜索集由 6 个值组成，则您将对原始输入的 6/16383 进行线性传递。它仍然是一个 O(n) 解决方案，但你的 n 现在有点小了。

附：零是一个不可能的结果值，还是你真的有 16384 可能性？

只是唱反调，采用包括暴力+索引查找的方法：

  1. 使用集合元素的 min 、 max 和 no 创建索引。
  2. 然后应用蛮力，排除 max < max（正在搜索的集合）和 min > min（正在搜索的集合）的集合
  3. 在暴力破解中，还排除集合的整个元素计数小于正在搜索的集合的元素计数。

95% 的搜索实际上是暴力破解一个非常小的子集。只是一个想法。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top