一种基于内存计算的时间序列数据相似性查询方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利(10)授权公告号CN108549696B(45)授权公告日2022.02.01(21)申请号201810338574.8(56)对比文件CN10418246(22)申请日2018.04.160A,2014.12.03CN105589951A,2016.05.18(65)同一申请的已公布的文献号CN105740431A,2016.07.06申请公布号CN108549696ADongXie等.DistributedTrajectory(43)申请公布日2018.09.18SimilaritySearch.《Proceedingsofthe(73)专利权人安徽工业大学VLDBEndowment》.2017,第10卷(第11期),1478-地址243002安徽省马鞍山市湖东路59号1489.专利权人飞马智科信息技术股份有限公司审查员杨春颖(72)发明人秦锋茆凯成郑啸(74)专利代理机构安徽知问律师事务所34134代理人平静胡锋锋(51)Int.Cl.G06F16/2458(2019.01)G06F16/27(2019.01)权利要求书3页说明书7页附图4页(54)发明名称一种基于内存计算的时间序列数据相似性查询方法(57)摘要本发明公开了一种基于内存计算的时间序列数据相似性查询方法，属于分布式数据库、内存计算及信息检索技术领域。本发明使用分布式计算节点组成的集群，通过内存存储数据，通过扩展分布式节点来扩展集群计算能力；将时序数据分配至计算节点，并形成索引驻留内存，当集群接收搜索请求后，调度各个计算节点进行搜索；各节点数据的分区和索引构建都在本地内存中进行，可以和其他节点或整体外部子模块通信；查询过程会在部分节点读取数据，经过驻留在内存中的索引的引导，不需要扫描整个集群。本发明可以对用户任意给定的一条时间序列，快速地从大规模使用内存计算的集群中找出大部分相似序列。CN108549696BCN108549696B权利要求书1/3页1.一种基于内存计算的时间序列数据相似性查询方法，其特征在于：其使用分布式计算节点组成的集群，通过内存存储数据，通过扩展分布式节点来扩展集群计算能力；其将时序数据分配至计算节点，并形成索引驻留内存，当集群接收搜索请求后，调度各个计算节点进行搜索；各节点数据的分区和索引构建都在本地内存中进行，可以和其他节点或整体外部子模块通信，以达到汇聚、移动和处理数据；查询过程会在部分节点读取数据，经过驻留在内存中的索引的引导，不需要扫描整个集群；包括以下步骤：(1)数据预处理：(1.1)将时序数据从数据库读入集群中各个计算节点；(1.2)依次读取集群中的每条时间序列T＝{t1，t2，...，ti，...tn}进入各个计算节点内存；(1.3)将时间序列进行特征提取，并视集群各计算节点为一整体，将特征序列平均存储在各节点内；(2)数据分区：(2.1)选取随机一组个数为Z的特征序列样本，根据节点内存大小确定计算节点最大容量为M，并确定每个计算节点负载容量为M/2个，将所有特征序列按照其中第一个元素q1从小到大进行插入排序；(2.2)按照上一步的排序结果，将特征序列在q1轴方向上分成S个切片，使得每个切片至少包含S·M个矩形；(2.3)在每个切片中对每个特征序列的q2从小到大进行插入排序；(2.4)根据排序结果，将特征序列在q2轴方向上分成S个切片，使得每个切片包含S·M个矩形；(2.5)在特征序列q2‑qK‑1元素上重复步骤(2.2)‑(2.4)的操作；(2.6)在每个切片中对每个特征序列的qD进行排序；(2.7)在每一个切片中依次将每M个特征序列对象分配为一组，形成一组MBR节点，MBR为最小边界矩形；(2.8)扩展MBR节点，至覆盖所有剩余节点；(2.9)根据MBR节点的边界，指定每个记录到各自的计算节点内，并设为分区；(3)索引构建：(3.1)检索分区内节点的特征序列子项个数N，若N＞M，则对该分区实现分裂算法，具体包括以下步骤：(3.1.1)将在该分区内1到N子项循环截取两个序列Ns和Nt，并在子项中从1到平均维度K之间循环，并使其满足等式|Nsb‑Ntb|＝MAX(|Nqd‑Nrd|)，其中b∈{1，2，...，K}；若等式成立，将两子项Ns和Nt分别放入两新增节点Set1和Set2中；(3.1.2)把Set1和Set2中的所有包围矩形中面积最小的矩形用MBR(Setj)表示，则可得到最小矩形新增节点面积差最小矩形面积接着将分区内剩余特征序列Ni分别划分到Set1和Set2中，Ni是除却Ns和Nt以外的剩余的序列子项；2CN108549696B权利要求书2/3页(3.2)将Set1和Set2作为原分区的子结点增加一层；(3.3)以此类推重复步骤(3.1)‑(3.2)；(