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

Question

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

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

我想在此序列中找出定期出现的键.

例如,如果我有序列(1,a)(2,b)(3,c)(4,b)(5,a)(6,b)(7,d)(8,b)(9) ,a)(10,b)

算法应该发出(a,4)和(b,2).这是一个周期为4的情况,b发生的周期为2.

如果我构建所有键的哈希并存储每个键的连续时间戳之间的差异的平均值以及它的std偏差,我可能能够进行传递,并仅报告具有可接受的std偏差的那些(理想情况下,0).但是,每个唯一键需要一个桶,而在实践中,我可能只有很少的真正周期性模式.有更好的方法吗？

Answer 1

这或多或少就是发明傅里叶变换（快速傅里叶变换等）的原因。

您本质上是将序列从时域（或某些类似维度）转换为频域。这是一个非常古老的问题，早于计算机的应用，并且关于这个主题有大量的理论。另请参阅离散傅里叶变换。

编辑：您必须以某种方式转换您的值 k1，k2，...，但假设这是可行的，这种方法也应该是。