3

对于一个特定的项目，我们会获取许多事件的数据并同时收集有关这些事件的变量。收集数据后，我们对所述数据执行用户可自定义的分析，以确定用户感兴趣的内容。

数据以类似于以下的形式收集：

时间戳事件
0 x = 0
0 y = 1
3 事件 A 发生
3 x = 1
4 事件 A 发生
4 x = 2
9 事件 B 发生
9 y = 2
9 x = 0

要随时了解整个状态，最直接的方法是遍历整个数据集。例如，如果我从时间 0 开始，并“分析”到时间戳 5，我知道在该点 x = 2，y = 1，并且事件 A 已经发生了两次。这是一个非常简单的例子。用户可能（并且经常）对事件之间的时间感兴趣，比如从 A 到 B，他们可能会指定第一次出现 A，然后是 B，或者最后一次出现 A，然后是 B（分别为 9-3 = 6 或 9-4 = 5)。就像我说的，当你走过整个场景时，这很容易分析。

现在，我们需要调整模型以分析任意时间窗口。如果我们看一下 0-N，那就很简单了。但是，例如，如果我查看 1-5，我没有 y 的概念，除非我从 0 开始并且知道 y 最初是 1 并且在窗口 1-5 中没有改变。

我们的方法本质上是创建一个变量字典，并对事件运行回调。如果一个分析是“当事件 A 发生并且时间大于 3 时 x 是什么”，那么我们将在第一个事件 A 上运行该回调，它会立即返回，因为时间不大于 3。它将在 4 处再次运行，并且它会报告在 t=4 时 x 为 1。

为了适应“时间窗口”，我想我将（在后台）为分析添加额外的条件。如果他们的分析只是“事件A发生时x是什么”，并且当前窗口是1-5，那么我将其更改为“事件A发生并且时间> = 1并且时间<= 5时x是什么”。然后如果下一个窗口是 6-10，我可以根据需要重新调整条件。

我的主要问题是：这适合什么模式？ 我们显然不是第一个处理此类问题的人，但我一直无法找到其他人是如何处理它的。我可能只是不知道在 Google 上究竟要搜索什么。 除了保存整个全局状态的字典以在给定时间查找单个状态之外，还有其他方法吗？ 另请注意，数据可能有几条甚至数万条记录，因此对数据集的迭代越少越好。

4

2 回答 2

4

我认为您最好的方法是定期对完整状态数据进行“快照”，例如每 1000 个样本（例如），同时记录增量。当您将数据存储为与某个原始值（也称为增量）的偏移量时，您别无选择，只能从原始值开始重建完整数据。存储定期快照将减少您必须执行的重建量 - 设计权衡是一方面低存储要求但重建时间长，另一方面存储要求更高但重建时间更短。

MPEGs, for example, store each frame as the differences between the current frame and the previous frame. Ordinarily, this would force an MPEG to be viewed from the beginning, but the format also periodically stores full frames so that the decoder doesn't have to backtrack all the way to the beginning of the file.

于 2009-07-09T12:59:28.913 回答
1

您可以在 Log(N) 中按时间搜索，并且您可以了解可以接受多少更新......因此这是我的解决方案：

选择 N 个可接受的更新以返回结果。鉴于您到目前为止提到的音阶，256 可能会很好。

每 N 条记录，将所有状态的条目提交到字典中，并带有时间戳。

现在，您需要权衡字典大小与速度。N->\infty 是常规搜索。N<-1 是您当前的解决方案，其他任何地方的 N 都需要更少的内存，但速度会更慢。

您现在的实现是（对于时间 X）：对子采样全局字典的 Log(n) 搜索到 X 之前的时间戳，（时间戳为 Y）。Log(n) 搜索事件列表到时间戳 Y，并执行少于 N 次更新。

选择 N 作为 2 的幂甚至可以让你做一些很好的移位技巧来快速地进行四舍五入的整数除法。

于 2009-07-09T12:52:39.677 回答