algorithm - 发现大型数据集中的周期性模式

Question

我在磁盘上有大量的元组序列 (t1, k1) (t2, k2) ... (tn, kn)

ti 是一个单调递增的时间戳，而 ki 是一个键(如果需要，假设一个固定长度的字符串)。 ti 和 ki 都不能保证是唯一的。然而，独特的 tis 和 kis 的数量是巨大的(数百万)。 n 本身非常大(1 亿+)并且 k 的大小(大约 500 字节)使得不可能将所有内容都存储在内存中。

我想找出这个序列中周期性出现的键。

例如，如果我有序列 (1,一个) (2, 二) (3, 三) (4, 二) (5,一个) (6, 二) (7, 四) (8, 二) (9,一个) (10, 二)

算法应该发出 (a, 4) 和 (b, 2)。即 a 出现的周期为 4，b 出现的周期为 2。

如果我构建所有键的散列并存储每个键的连续时间戳和相同的标准偏差之间的差异的平均值，我可能能够通过，并仅报告具有可接受的标准偏差(理想情况下为 0)。但是，每个唯一键需要一个桶，而在实践中，我可能只有很少的真正周期性模式。有什么更好的方法吗？

Answer 1

您可以使用离散的 autocorrelation找到句点，然后搜索键。自相关的优点是更容易理解离散域中发生的事情，并且您不必担心将键映射到任何东西——只需使用两个键的特征函数，当它们相等时为 1不相等时为 0。