我正在处理一个庞大的时间序列数据库。每 n 毫秒保存一个值。必须根据数据库中已有的旧时间序列检查新时间序列。
此刻我陷入困境,因为每个解决方案都像 O(n²) 一样昂贵。
下面我有一些图片,显示了匹配的短时间序列(灰色和橙色)。该算法应该能够识别此类匹配项,而无需像我需要速度那样准确。一个近似值就足够了。
我在网上研究了一些关于“最长公共(public)子序列问题”或“动态时间扭曲”的论文。但要么处理完美的测量值或完美的尺寸,要么处理 O(n²)。
- 完美匹配两个时间序列(灰色和橙色)
- 新测量值不准确(橙色)但仍然匹配
- 一个简短的新测量(橙色)但仍然匹配
- 一个巨大的新测量值(橙色),但仍然匹配
- 新测量失败(橙色)但仍然匹配
最佳答案
关于algorithm - 寻找(子)时间序列的(非常)快速近似匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33392743/