我在磁盘上有一个很大的元组序列(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).但是,每个唯一键需要一个桶,而在实践中,我可能只有很少的真正周期性模式.有更好的方法吗？
algorithm ×1