-
题名支持均匀缩放的不等长时间子序列查询方法
- 1
-
-
作者
熊浩然
何震瀛
-
机构
复旦大学软件学院
复旦大学计算机科学技术学院
-
出处
《计算机工程》
CSCD
北大核心
2024年第1期60-67,共8页
-
基金
国家重点研发计划(2021YFB3300502)。
-
文摘
作为时序数据分析中的基础技术之一,时间序列的子序列查询旨在寻找与目标序列相似的子序列。现有的子序列查询方法大多仅支持查询与目标序列长度相同的子序列,因而均匀缩放技术常被用于解决子序列查询中的不等长问题。但现有支持均匀缩放的子序列查询技术大多未考虑子序列的Z-标准化,且对查询效率仍有改善的空间。针对该问题,提出一种基于索引技术且支持均匀缩放的子序列查询方法。结合现有索引方法 ULISSE提供的树状数据结构,设计可保证非漏报的下界距离,为索引结构的剪枝提供理论保证,并利用索引中存储的元数据,提出精确K-近邻查询算法。所提方法适用于非归一化和归一化两种场景。实验结果表明,较UCR-US和ULISSE基线方法,该基于索引的不等长子序列查询方法在CAP、GAP两个真实数据集以及随机游走人工合成数据集上均实现了查询效率的显著提升,针对在非归一化和归一化两种场景下的不等长子序列查询,该方法的平均效率提升分别为2.33和2.51倍。
-
关键词
时间序列
子序列查询
均匀缩放
索引
下界距离
K-近邻
-
Keywords
time series
subsequence query
uniform scaling
index
lower bound distance
K-Nearest Neighbor(K-NN)
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名改进DTW下界函数的距离度量方法研究
被引量：1
- 2
-
-
作者
王超
龙英文
殷炜宏
黄勃
-
机构
上海工程技术大学电子电气工程学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2022年第23期316-326,共11页
-
基金
国家自然科学基金(61603242)
上海市青年科技英才扬帆计划(281)。
-
文摘
动态时间弯曲算法(DTW)是一种常见的时间序列相似性度量方法,对数据挖掘任务起着至关重要的作用。针对现有DTW算法的时间复杂度高、度量精确度一般的特征,提出一种DTW下界函数的提前终止算法(LB_ESDTW)。引入提前终止思想,提高算法的执行效率;再在提前终止算法思想的基础上,与DTW下界函数相结合,提出一种基于提前终止DTW的下界函数算法(LB_ESDTW)。该算法在保证高效的运行时间效率的同时,也使得算法的度量准确率得到了提升。实验结果表明,LB_ESDTW在绝大部分时间序列数据集中,都表现出良好的适应性,针对不同类别的时间序列,都能有良好的度量性能。
-
关键词
时间序列
动态时间弯曲
提前终止
下界距离
相似性度量
-
Keywords
time series
dynamic time warping
early termination
lower bound distance
similarity measure
-
分类号
TP399
[自动化与计算机技术—计算机应用技术]
-
-
题名基于滑动窗口分段的动态时间弯曲下界算法
被引量：1
- 3
-
-
作者
孙宏伟
王会青
张建辉
-
机构
太原理工大学计算机科学与技术学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2016年第4期768-772,共5页
-
基金
国家自然科学基金项目(61373101
61402318)资助
+2 种基金
博士点基金项目(20131402120009)资助
山西省科技攻关项目(20130313012-2)资助
校青年团队项目(2013T049)资助
-
文摘
下界算法可以简化时间序列相似性查询的计算过程.现有的基于点对累积近似表示法的下界算法,相似度计算的时间代价较小,但当时间序列振幅波动较大时,往往不能紧致地拟合时间序列.针对这一问题,在下界算法中引入滑动窗口分段表示法,提出一种基于滑动窗口分段的动态时间弯曲下界算法,构建拟合度更高的上下边界曲线,对时间序列进行过滤,筛除相似性较差的时间序列.实验结果表明,该算法能够有效地简化时间序列相似度的计算过程,降低时间复杂度,提高相似性查询效率,且当时间序列的振幅波动较大时,相似度计算的紧致度和修剪率更高.
-
关键词
动态时间弯曲距离
下界距离
点对累积近似
滑动窗口分段
-
Keywords
dynamic time warping distance
lower bound distance
piecewise aggregate approximation
sliding Windowfragment
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名大规模图像特征检索中查询结果的自适应过滤
被引量：7
- 4
-
-
作者
艾列富
于俊清
管涛
何云峰
-
机构
华中科技大学计算机科学与技术学院
安庆师范学院计算机与信息学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2015年第1期122-132,共11页
-
基金
国家自然科学基金(61173114
61202300
+1 种基金
61272202)
武汉市应用基础研究计划项目基金(2014010101010027)资助~~
-
文摘
针对大规模图像的快速检索问题,提出了面向倒排索引结构的检索方法中查询结果的自适应过滤方法:全面过滤和不完全过滤.目的是在不影响查询精度的前提下,提高查询效率.根据查询特征所在的空间位置,全面过滤通过构造以查询特征点为球心的超球体并自适应地计算半径,只对位于超球体内部的查询结果进行排序,从而减少需要排序的查询结果数量,提高查询效率.在此基础上,为了降低过滤查询结果的时间开销,不完全过滤将倒排列表划分为若个子倒排列表并将对应的聚类中心用于过滤查询结果.为了验证所提出方法的有效性,以一种典型检索方法:基于残差量化的检索方法为应用实例,分别将全面过滤和不完全过滤与该检索方法相结合.此外,为了提高特征量化效率,将一种欧式距离下限定理与残差量化相结合并用于过滤特征量化过程中非近邻聚类中心.通过在公开数据集进行实验,实验结果表明在保证具有相同平均查全率的前提下,全面过滤和不完全过滤都能明显减少基于残差量化的检索方法的查询时间,不完全过滤比全面过滤具有更快的检索速度.此外,非近邻聚类中心过滤可以有效提高残差量化的特征量化效率.
-
关键词
大规模图像特征
查询结果
自适应过滤
超球体
距离下限
-
Keywords
large scale image feature
query results
adaptive filtration
hyper-sphere
lower bound of distance
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
