在大型数据集中搜索

计算科学 数据管理
2021-12-16 06:22:57

我正在研究小鼠社交互动模型。我有鼠标和盒子以及一个模拟,它输出哪个鼠标在哪个时间段内停留在哪个盒子中(这是随机选择鼠标来更改盒子的结果)。问题是如何最终并由此获得两只老鼠在同一时间段内在同一个盒子里的会面。我需要这个来查看会议持续时间的 CDF、每天建立一个社交网络等。

现在我有一个 MySQL 数据库,其中模拟直接插入每个逗留结果。然后另一个用 Scala 编写的工具,只检索所有的停留结果,以几百个的部分为单位,循环遍历它们,并为每个询问数据库哪些停留与它重叠,并将每一对插入数据库,如下所示:

box, id1, res_id1, id2, res_id2, from, to, dt,typ

这意味着小鼠 id1 和 id2 在“from”和“to”之间的间隔中的“box”框中,持续时间为“dt”,并且会议类型为“typ”。可能有四种会议类型,具体取决于每只鼠标何时在框中(例如,当一个鼠标相对于另一个鼠标进入和退出时)。“res_id1”和“res_id2”告诉我们使用了哪些逗留结果来生成会议结果。

显然,这是非常低效的。有什么更好的方法呢?我不受限于使用 RDMS,但我认为这将是最简单的,因为我正在阅读并进一步分析 R 中的数据。将停留输出到文本文件中然后使用 Hadoop 以某种方式生成会议是否有意义?还是别的什么?

在大约四分之一的模拟试验期间,我产生了大约 150 万个住宿结果。

1个回答

您需要“开箱即用”(双关语)。因为你有一个盒子里的逗留数据库,你想到了循环所有逗留的算法。但是要找到重叠,您需要将每个逗留与其他逗留进行比较——因此您的算法具有复杂性,其中是逗留次数。正如您所注意到的,这很昂贵。O(Ns2)Ns

所以转过来。不是对所有停留进行循环,而是对所有框进行循环并执行以下操作:

  • 对于每个框,将与该框关联的那些停留事件提取到列表或子集中(复杂度:)。O(Ns)

  • 按开始时间对这个子集进行排序(复杂性:其中是在框中停留的次数)。如果您的数据库是以升序的住宿开始时间填充的,则甚至不需要此步骤。O(Ns,blogNs,b)Ns,bb

  • 在这个子集中,遍历所有的停留,比较一个事件的结束时间是否晚于下一个事件的开始时间。这表示重叠。(复杂度:。)O(Ns,b)

我所描述的是一种非常常见的策略:如果对数据集合的循环效率低下,请考虑是否有不同的方式来查看数据集并在其他内容上循环。