我的磁盘上有大量的元组序列
(t1，k1)
(t2，k2)
...
(tn，kn)
ti是单调增加的时间戳，而ki是关键(如果需要，请假定使用固定长度的字符串)。 ti和ki都不保证是唯一的。但是，唯一的tis和kis数量庞大(百万)。 n本身非常大(超过1亿)，k的大小(约500字节)使得不可能将所有内容存储在内存中。
我想找出此序列中 key 的周期性出现。
例如，如果我有序列
(1，一)
(2，b)
(3，c)
(4，b)
(5，一)
(6，b)
(7，d)
(8，b)
(9，一)
(10，b)
该算法应发出(a，4)和(b，2)。即a的周期为4，b的周期为2。
如果我建立所有键的哈希值并存储每个键的连续时间戳与相同键的标准差之间的差的平均值，则我可能能够通过，并仅报告具有可接受的标准差的键(理想情况下为0)。但是，每个唯一 key 需要一个存储桶，而实际上，我可能只有很少的真正的周期性模式。还有更好的方法吗？
最佳答案
您可以使用离散的autocorrelation查找句点，然后搜索键。自相关的优点是，它更容易理解离散域中发生的事情，并且您不必担心将键映射到任何东西—只需使用两个键相等的特征函数(当它们相等时为1)如果不相等，则为0。
关于algorithm - 发现大型数据集中的周期性模式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2582131/