LVS:高效的时间序列上的语义窗口查询算法

近年来,物联网、智能电网和可穿戴设备等应用产生了海量的历史时间序列数据.传统的时间序列处理技术主要包括分类、聚类和异常检测等数据挖掘技术,以及范围查询、相似查询、聚集查询等查询处理技术.最近研究者们开始关注探索式的查询处理技术.这些查询的典型特征为:由于查询的任意性和巨大的搜索空间,无法采用固定的索引技术来加速查询处理,而需扫描整个数据集.提出了一种新的探索式查询:基于条件的最长子序列查询,并给出了一种高效的处理算法.算法主要创新点包括:1)通过将原始的时间序列转换为正?负分段序列,从而大大降低了搜索空间的规模;2)通过分析LVS的结构,提出了一种基于上界的搜索算法.还提出了若干种剪枝策略来进一步提高效率.在大规模的模拟数据和真实数据上进行了实验,验证了算法的有效性和高效性.