算法 – 在大图中的常见子结构的引导挖掘

首先，创建一个过滤器，允许您忽略大多数(如果不是全部)非重复模式。为此：

>分配两个位数组(并在执行此操作时考虑高速缓存大小)。第一个是一个简单的bloom过滤器。第二个将是一个重复的bloom过滤器。
>在第一遍遍历结构时，对于每个可索引结构，计算哈希值。在第一个布隆过滤器中选择适当的位并设置它。如果该位已经设置，还要设置重复的bloom过滤器中的相应位。

在你的第二遍，你将需要做实际确认比赛的“较重”的过程。为了实现这一点：

>再次扫描图形，并记录与第一遍中生成的重复bloom滤镜匹配的任何结构。
>将那些匹配的哈希表放置在哈希表中(理想情况下使用计算的哈希中的不同位)
>当检测到重复时，将该信息存储在您要收集的地方。

此算法将对大型数据集运行非常快，因为它将显着减少适当缓存级别的压力。还有一些增强，你可以做，以使它在不同的情况下表现更好。

>为了提高多线程系统的性能，并行化第一步实际上是安全的。为此，给每个线程(或集群中的计算机)一块图。每个人都应该计算自己的两个绽放的副本。然后可以将大花结合成最终的大花。减少函数只是(存在，复制)=(存在1或存在2，复制1或复制2 OR(存在1和存在2))。这一步非常快。
>并行化第二步也是完全安全的，但必须稍微修改。为了做到这一点，你将从第一步采取重复bloom过滤器，并在第二步使用它作为过滤器，与以前一样。但是，您无法轻松完成最终的比较。您必须将潜在的重复项放在哈希桶中。然后，在每个分片的数据已经被写入其自己的潜在重复哈希表的列表之后，将数据向上由哈希桶分割，并且在第三步骤中找到重复的哈希表。每个哈希桶(从第二步中的任何输出)必须由同一个工作程序处理。
>如果你有大量的结构，你正在索引，你可以通过递归应用上述算法提高性能。调整是您使用每个匹配类别作为上述算法的输出作为递归传递的输入。例如，如果在算法的第一次运行中仅索引最多具有5个项目的结构，则可以在递归时获取每组重复的子图，并仅对这些子图运行算法。这显然只对非常大的数据集是必要的。
>如果图表非常大以提高布隆过滤器的有效性，您可以考虑的另一个调整是迭代算法。例如，在第一遍中，您可能只考虑将第一个标签作为子图的基础的子图。这将减少您的bloom过滤器所需的大小和/或允许您在第一遍过滤出更多的子图。

一对夫妇注意到调整以上：

>考虑缓存大小。例如，在Intel Haswell芯片上，每个内核在L1缓存中有32K，在L2缓存中有256K。每个缓存行将包含512位，因此，如果你填充了1％的bloom过滤器，大多数缓存行将被触摸。根据算法其他部分的速度以及其他东西使用这些缓存的情况，您可以安全地创建一个具有高达512 * 1024个条目(每个过滤器每位8个条目，在超线程系统上为128个条目)的bloom过滤器，是你得到多少L2)，仍然保持大部分的数据集在L2缓存和真正活跃的东西在L1。对于较小的数据集，请保持此数字下降，因为没有点使它大。如果你只是标记功能作为潜在的重复，当他们不小于1％的时间，这是完全正常。
>并行化，再次，只有真正有用的情况下，你有大量的数据。我假设你可能。如果你做并行化，你应该考虑几何。在每台计算机上放置部分数据集将使用此算法。然后，您可以在每台计算机上运行每个迭代(变体#4)。如果你有巨大的数据集，将避免必须将所有的数据传输到所有的计算机。

无论如何，总结一个关于运行时复杂性的声明，我会说，它真的依赖。许多人忽略了增加数据的工作集合将导致存储器访问不是在成本上相等的事实。从根本上说，上述算法虽然高性能，如果调整得适当，将在一个小的数据集上运行得非常快，但它真的闪耀着更大的数据集，因为它允许高效率的方式保持数据的工作集在任何缓存级别是合适的(L1，L2，L3，RAM，本地磁盘，本地网络等)算法的复杂性将取决于数据，但我不认为一个算法可以创建得更快。我没有留下你如何表示子图，有工作要做，以实现最优算法，但不知道更多，我不能确定最好的方式来存储的信息。

算法不能比我提出的运行得快得多的原因是，第一遍需要比第二遍少得多的工作量，因为它不需要分支，并且执行逐位操作的工作较少。因此，我们可以说，它对我们正在做的整体工作增加很少。第二阶段也是尽可能高效。你必须(禁止一种方法来完美地描述每一种可能性与有限的一组位，我会解释一秒钟)实际上比较每个图形功能，写信息在某个地方。唯一的变量是多少工作是检查是否需要这样做。检查一个位，您可以任意地将错误率扩展到0％，这是你可以得到的。

对于小型数据集，两次传递有利于您的原因是，在较小的内存量中，您可能拥有大量的bloom基数。但对于真正小的数据集，你可能只是使用第二步，忽略第一步。但是，至少，你需要为每个散列目标存储一个指针。这意味着您将需要为同一级别的过滤写入32或64倍的数据。对于足够小的数据集，这并不重要，因为读取是读取，写入是写入，但对于较大的数据集，这可以允许您在保持给定级别的缓存时完成相同级别的过滤。在必须跨多个计算机或线程工作的情况下，该算法中提供的机制将更有效率，因为数据可以更快地组合，并且可以交换更多关于潜在匹配的信息。

现在，最后，正如我提到的，如果在每次迭代中检查的要素数量进一步减少，您可能会得到稍微好一些。例如，如果您只检查32个可能的标签和每次通过具有特定标签的孩子的数量(并且这是限制为1024)，您可以完美地用15位表示。如果你将计数限制为255，你可以存储这个信息与32K完美。为了在你的情况下解决这个问题，你需要使用我上面提到的迭代，递归和分片策略，然后你还需要跟踪源图和一些其他信息。我真诚地怀疑这将工作很好，除非在非常有限的情况，但我包括它的完整性。

无论如何，这是我的第一个答案Stack Overflow，所以不要太难我。我希望这是有帮助的！