在时间序列数据库中查找给定时间序列的近似序列的方法

摘要

本发明属于数据挖掘技术领域，具体为一种在海量时间序列数据库中查找给定时间序列的近似序列的方法。该方法包括：采用树状索引的结点表示方式；根据索引的算法框架，逐条构建索引；选择最优策略进行结点分裂；最后基于DSTree索引进行查询，海量时间序列数据库中查找给定时间序列的近似序列。本发明提出的索引方法，根据时间序列的数据分布情况调整索引子序列长度和维度，新的索引表示方式也满足提供距离上界的需求，大幅提高查询效率。

主权项

一种在海量时间序列数据库中查找给定时间序列的近似序列的方法，其特征在于具体步骤为：(一)构建树结构索引：在海量时间序列插入数据库时，利用索引构建算法逐条构建树结构索引，构建索引的算法步骤如下：(1)对于新插入的时间序列X和索引结点N，N的初始值为根结点，首先计算X的平均值和标准差m_Q、s_Q，更新索引结点N的平均值上、下界：m_u、m_l，和标准差上、下界：s_u、s_l；(2)如果索引结点N是叶结点，将时间序列X放入索引结点N指向的文件F中，并执行步骤(3)‑步骤(5)，否则跳过步骤(3)‑步骤(5)，直接执行步骤(6)；(3)如果索引结点N中时间序列数量超过指定的阈值th，选择一个最优结点分裂策略SP；(4)把索引结点N设为非叶子结点，新建两叶子结点作为N的子结点；(5)将索引结点N结点对应的F文件中的时间序列逐条插入到子结点中；(6)判断时间序列X属于索引结点N的哪个子结点，将X插入对应的子结点；其中，步骤(3)中，所述一个最优结点分裂策略SP从如下3种结点分裂策略中选择，并按照该策略对叶子节点进行分裂；所述3种结点分裂策略分别如下：(a)根据平均值纵向分裂：假设选中将要分裂的索引结点N所指向的时间序列平均值的取值范围为[μ_l,μ_u]，其中μ_l，μ_u分别表示平均值上、下界，那么将N分裂为两个新结点N_l，N_r，它们所指向的时间序列的平均值取值范围分别为(b)根据标准差纵向分裂：假设选中将要分裂的索引结点N所指向的时间序列方差的取值范围为[σ_l,σ_u]，其中σ_l，σ_u分别表示标准差上、下界，那么将N分裂为两个新结点N_l，N_r，它们所指向的时间序列的标准差取值范围分别为(c)根据时间跨度横向分裂：假设选中将要分裂的索引结点N所指向的时间序列的时间取值范围为[r_i‑1+1,r_i]，其中r_i表示时间第i段时间序列中最后一个点的时刻，那么将N分裂为两个部分S₁和S₂，它们所指向的时间序列的时间取值范围分别为再从S₁和S₂中选择一个， 根据平均值或者标准差进行纵向分裂，得到R₁，R₂两个值域,再依据R₁，R₂对N进行划分；其中，假设被选中的S₁平均值取值范围为[μ_l,μ_u]，则R₁，R₂分别为对于3种分裂策略，最优策略SP的选择依据是：(a)定义结点计算指标：其中μ_u，μ_l分别表示节点包含的所有时间序列的平均值的上、下界，σ_u表示标准差上界；(b)对于结点N的三种分裂策略，用N_l，N_r表示分裂后结点，分别计算分裂策略的收益B：其中和分别是原始节点N、分裂得到的两个节点N_l和N_r的质量；选择B值最大的策略对N进行分裂；(二)基于DSTree索引的查询：索引构建完成后，在海量时间序列数据库中查找给定时间序列的近似序列，其步骤为：(1)对于待查的时间序列Q，先以步骤(一)的构建树结构索引算法，计算得出距离Q最近的索引结点N₀，对于时间序列Q，其均值记为μ_Q，标准差记为σ_Q；索引节点N中的均值最大值为μ_u，最小值为μ_l；标准差最大值为σ_u，最小值为σ_l；由表1得出Q与N₀之间的均值和标准差上下界UB_μ/n、LB_μ/n、UB_σ/n和LB_σ/n，取LB_μ/n和LB_σ/n之和为Q与N₀之间距离平方的下界LB_dist，开方可得距离下界初始值BSF；(2)接下来从根结点root开始自顶向下广度优先遍历索引树，对于树中的一个结点N，若N与Q的距离下界LB_dist大于BSF，则忽略N及其所有子孙结点；若N与Q距离下界LB_dist小于BSF，更新BSF，遍历N的所有子结点；对于遍历过程中小于BSF的叶子结点N_leaf，将其中包含的每一条序列取出与Q直接计算距离，用最小距离更新BSF；索引遍历结束时，BSF的值为最小距离，所对应的序列即最近似序列：表1.时间序列与时间序列集合距离上、下界计算表Case UB_σ/n LB_σ/n σ_Q≤σ_l(σ_u+σ_Q)²(σ_l‑σ_Q)²σ_l≤σ_Q≤σ_u(σ_u+σ_Q)²0 σ_u≤σ_Q(σ_u+σ_Q)²(σ_u‑σ_Q)²                                                                     。