《计算机学报》2009年11期，2009，32（11）
高效时序相似搜索技术(
冯玉才 蒋涛 李国徽 朱虹
(华中科技大学 计算机科技与技术学院 武汉 430074)
摘 要: 时序相似搜索被认为将来最有前途的技术之一. 然而, 时序数据是典型的高维海量数据, 如何开发高效算法非常关键. 概述了时序相似搜索技术的研究现状和进展以及研究的主要内容, 讨论了该技术的几个重要应用范例, 并对一些典型算法进行了定量分析; 然后重点论述了高效时序相似搜索的关键技术, 包括: 边界过滤、三角不等式修剪、多辨析率检索方法、过滤精炼方案等. 最后讨论了并分析了时序的近似相似搜索技术. 上述所有技术通过对比, 其正面和反面都被深入分析. 最后指出了存在的问题和未来研究热点和方向.
关键词: 时间序列; 相似搜索; 高效搜索方法; 子时间序列
中图法分类号: TP311
Underlying Techniques of Efficient Similarity Search on Time Series
FENG Yucai, JIANG Tao, LI Guohui, ZHU Hong
(College of Computer Science & Technology, Huazhong University of Science and Technology, Wuhan 430074, China)
Abstract: Time series similarity search is regarded as one of the most promising technologies in the future. However, time series data is a typical high dimensional and massive data. Developing efficient algorithms is very important for fast time series similarity queries. The paper provides an overview of research progress, and gives main research content and directions in the field. Then, some paradigms in time series applications are introduced and the performance of some typical algorithms is analyzed quantitatively. Next, we survey the underlying technologies of efficient similarity queries on time series, such as bounding filtering, triangle inequality pruning, multi-resolution approach, and filter-refine scheme, etc. Furthermore, the main methods for approximate similarity search are summarized and analyzed. All above-mentioned technologies, the pros and cons of the techniques are discussed by comparison. Finally, some possible research hotspot and directions in the future are given.
Key Words: time series; similarity search; efficient searching methods; subsequence
1 引言
时序数据在医学、金融、传感器网络、移动对象、图像、音频等领域广泛存在, 同时它已经在生物序列分析[1]、金融数据分析[2-3]、移动对象跟踪[4-5]、传感器网络监控[6]、运动捕获[7]等领域成功应用. 由于时序相似搜索技术存在巨大的潜在应用价值, 它一直是学术界研究的热点. 许多研究机构和一些著名的大学纷纷参与进来, 包括: IBM公司的Almaden和Watson研究中心、Maryland大学、Carlifornia University的一些研究小组(Irvine、Riverside和Santa Barbara等)以及Carnegie Mellon大学等. 我国的复旦大学、浙江大学、南京大学和中国科技大学以及香港科技大学、香港城市大学等也参与研究. 近十年来著名的国际学术会议如SIGMOD、VLDB、PODS、ICDE以及期刊如ACM TODS、IEEE TKDE、VLDB Journal等都呈现了大量高水平的研究成果.
时序相似搜索技术已经从早期的一般化研究阶段, 即研究时序度量、时序维度约间和时序索引等方面, 进入到深入的研究阶段, 即如何针对不同的应用领域开发高效的时序搜索算法, 同时保持高的精度并维持低的时间和空间成本. 然而, 时序是典型的高维、海量数据类型. 开发高效的时序相似搜索技术仍然面临极大的挑战, 很多问题有待解决, 具有广阔的研究空间, 我们认为研究高效时序相似搜索的核心支撑技术具有重要的意义. 本文主要从高效性这个角度来阐述时序相似搜索的核心技术, 及应遵循的基本技术框架和解决思路.
本文首先概述时序相似搜索的基本概念及其研究的主要内容, 然后分析了它的应用场景并就有关典型算法的性能进行了定量分析, 接着综述了高效时序相似搜索技术的核心支撑技术以及近似的时序搜索技术, 最后总结全文, 指出时序相似搜索技术可能的研究热点和方向.
2 时序相似搜索基本概念及研究内容
时序及时序相似搜索
时间序列是指随着时间变化而形成的有序数据列表, 简称时序. 它反映了某个事务/事件随着时间变化的状态, 其状态可以用实数值或符号来表示. 通常提到的时序是指通过等间隔时间取样形成的具有实数值的有序数据序列, 也即Time Series, 例如: 股票价格变化序列, 其定义如下:
定义1 时间序列(Time Series) 时间序列S是指按时间顺序排列的, 具有相等时间间隔的实数数据列表,记为: S(={s1,s2,...,sn}). 其中时间序列长度为组成S的实数值个数, 记为|S|=n. 包括现实世界对象或事件通过某种映射转换而来的时间序列, 例如:图像形状映射的时序, 英文手迹映射的时序等.
时序数据通常存储在文件中, 以数据库文件形式存放, 这种数据库称为时间序列数据库TSDB. 文献[8]最早提出时序相似搜索问题, 它是指在TSDB中寻找与查询时序Q具有相似特征的数据序列R, 其定义如下:
定义2 时间序列相似(Time Series Similarity) 给定一个查询序列Q(={q1,q2,…,qm}), 一个数据序列S(={s1,s2,…,sn}), 如果序列Q和序列S满足dist(Q,S)≤ε, 则说时间序列S和Q是相似的. 其中: ε是时序相似门限值, dist(Q,S)是一个距离函数, 例如: Lp(1(p((, p(N)距离函数[8]或动态时间弯曲(Dynamic Time Warping, DTW)[9]距离函数.
Lp距离函数主要包括三种形式: 当p=1时, L1表示Manhattan距离，它实际是两时序所有点对差值绝对值的累积和, 具有单调递增性; 当p=2时, L2称为欧氏距离; 当p=∞时, L(称为最大距离, 其形式变为:, 表示两时序所有点对差值绝对值的最大值. Lp距离函数是度量函数, 因为它满足度量空间的三个性质：(1) 自反性, ; (2) 对称性, d(x, y)=d(y, x); (3) 三角不等式, | d(x, y)−d(y, z)| ( d(x, z) ( d(x, y)+d(y, z). 这三个性质也是度量空间的三个充分必要条件. 时序距离函数满足距离的度量性质具有非常重要的意义: (1) 可以利用三角不等式修剪搜索空间以加快搜索效率; (2) 时序聚类算法要求距离函数具有对称性; (3) 它也是度量空间搜索策略(例如: 深度优先)能够正确执行的必要条件. 而源于语音识别的DTW采用动态规划的思想递归定义, 其形式为:
其中<>表示空时序, First(S)表示时序S的第一个元素, Rest(S)表示时序S从第2个位置到最后的子时序，First(Q)和Rest(Q)可以类似解释, min()是求三个元素中的最小值函数. DTW的缺点在于: 它不是度量函数, 且直接实现的算法具有较低的效率.
DTW函数的优点在于: 去掉了数据时序S(长度n)和查询时序Q(长度m)保持等长的要求(总长L满足条件: m,n≤L≤(m+n)), 容许序列点自我复制后再进行等长匹配, 从而具有较高精度. 运用DTW时, 须建立一个m×n的累积矩阵M以存放动态时间弯曲距离, 运算从M[1][1]开始至M[m][n]结束，最终在M上经过的路径称为动态时间弯曲路径. Lp距离函数与其不同, 它要求两个时序的点之间一一对应匹配(等长匹配), 相对于DTW的O(mn)时间效率其效率为O(n).
时序相似性搜索可以分成全序列匹配和子序列匹配两类. 文献[10]最早提出子序列相似搜索技术, 该技术也称为通用多维索引框架GEMINI(GEneric Multimedia INdexIng), 有的文献也称为FRM. 其主要思想是: 首先使用一个尺寸w的滑动窗口在长Len(S)的数据序列S的每个可能偏移位置, 将数据序列S分成Len(S)−w+1个子数据序列, 同时通过DFT将它们映射成特征空间中的特征点, 再建立以包含一定特征点的最小边界矩阵(Minimal Bounding Rectangle, MBR)为索引节点的R*-tree[11]索引结构(称为ST-index), 类似地处理查询序列Q; 然后构造一个查询序列Q和数据序列R的MBR的范围搜索获得候选项; 最后使用一个后处理过程去掉多报的数据子序列. 从搜索方式来看, FRM属于ε邻域范围搜索, 而如果对ε值进行从小到大排序, 取最小ε值的搜索则称为最近邻(1NN)搜索, 取前k个搜索结果的为kNN(k近邻)搜索.
时序相似搜索应考虑的因素
从需求层面来看, 一方面应该保证时序相似搜索技术具有足够快、正确性、小的空间负荷、动态性及能够处理变长的序列搜索等特性[8]. 足够快是指搜索的时间效率高, 当前的许多搜索算法的效率有待提高; 正确性即指应该返回满足要求的合格时序, 而不能丢失任何符合条件的时序, 例如: 不应出现漏报(false dismissals或false negatives)现象, 但多报(false alarms或 false positives)是容许的, 通常添加一个后处理(post processing)过程可以去除多报; 动态性指索引除了可以供搜索外, 还可在其上删除、插入或追加时序. 另一方面, 我们还应该考虑不同领域时序的本身特性, 即需要考虑噪声以及时序的各种变形[2]对时序相似搜索技术的影响. 例如, Lp度量方法就对噪声非常敏感[12].
从技术层面来看, 应考虑时序相似搜索技术需要解决的关键问题, 这包括时序相似度量、时序转换、高效的时序索引等. 这些构成了高效的时序相似搜索技术基础, 也是一般化研究阶段的主要内容. 之后, 时序相似搜索技术逐渐向深度和广度转移, 也即第二代时序相似搜索技术.
(1) 时序相似度量
时序相似度量是高效时序相似搜索技术的基础. 建立何种度量函数来实现时序相似度量非常关键, 这里不但要考虑各种度量函数的特性, 还应该考虑具体应用领域的实际需求. 相似度量一般可分为基于形状的相似度量[8-9]、基于特征的相似度量[3]、基于模型的相似度量[2,13]以及基于数据压缩的相似度量几种情形. 已有的度量函数主要包括: Lp-norms[8]、DTW[9]、最长公共字串(Longest Common Subsequence, LCSS)[4]、实序列编辑距离(Edit Distance on Real Sequence, EDR)[5]和实补偿编辑距离(Edit Distance with Real Penalty, ERP)[14]、空间装配距离(Spatial Assemble Distance, SpADe)[13]等. 随着研究的深入必将出现新的时序相似度量方法. 表1比较了几种距离函数的特性.
Table 1 Comparison of distance function
表1 距离函数对比
函数
名称
运算
成本
度量
函数
支持
平移
支持
噪声
特性
Lp
O(n)
√
简单高效, 不支持平移,时间和幅度缩放,易受噪声影响,精度差
DTW
O(n2)
√
高精度, 支持平移、非等长匹配
LCSS
O(n2)
√
√
用于移动轨迹匹配, 对异常和噪声有较强适应能力
EDR
O(n2)
√
相对LCSS具有更强的Robust
ERP
O(n2)
√
√
可利用三角不等式, 支持偏移(综合了Lp和DTW的优点)
SpADe
-
√
√
适于形状模式匹配, 支持时间和幅度的偏移、缩放以及噪声,
(2) 时序转换
由于时序是典型的高维数据, 为了避免由于高维(大于16维)而引起相似搜索算法性能急剧下降, 即所谓的维度灾难(dimension curse). 时序降维也称为时序转换, 是一类相对比较成熟的技术, 主要包括: 离散傅里叶变换(Discrete Fourier Transform, DFT)[8]、离散小波变换(Discrete Wavelet Transform, DWT)[15]、主成分分析(Principle Component Analysis, PCA)、奇异值分解(Singular Value Decomposition, SVD)[16]、点对线性近似(Piecewise Linear Approximation, PLA)[17]、点对累积近似(Piecewise Aggregate Approximation, PAA)[18]、自适应累积常量近似(Adaptive Aggregate Constant Approximation, APCA)[19]、切比雪夫多项式(Chebyshev Polynomials, CP)[20]、符号累积近似(Symbolic Aggregate approximation, SAX)[21]和界标模型(Landmarks)[2]等. 降维方法要求能保留大部分时序特征信息, 同时满足降维下界定理, 即特征空间距离小于源空间距离:Dindex(S,Q)≤Dsrc(S,Q)[10], 这是保证无漏报的必要条件. 但不管那种技术和方法, 都应考虑下面的因素: 是否能够有效地降低数据的维度; 尽量保留原时间序列中的信息; 是否有利于索引的建立以及在索引中的搜索; 是否剔除噪声和冗余以利于算法的效率和精度; 是否支持变长时间序列; 是否采用符号表示法等.
(3) 时序索引技术
由于时序广泛存在现实世界的各个领域, 同时许多领域数据也可以转换成时序数据, 因而时序是典型的海量数据类型. 为了提高时序搜索效率, 索引是非常必要的搜索机制. 索引技术的关键问题是如何划分数据空间或向量空间, 以及如何根据划分方法将数据组织起来. 最早的基于向量空间索引技术是1984年由Guttman提出的R-tree, 后来出现了一些变形种类: R*-tree[11]、SS-tree以及SR-tree等. 另一种类型是基于度量空间特征值聚类的索引方法: VP-tree[22]、MVP-tree、M-tree[23]、SA-tree[24]等. 另外, Park等人在基于字符的后缀索引[52]和前缀索引[50]方面也作了大量工作.
时序相似搜索研究的主要内容
从数据挖掘的角度来看, 时序模式匹配[25-26]、时序关联分析[27-28]、时序聚类[29]、时序分类以及时序异常[30]是时序相似搜索技术的主要研究任务. 就时序模式匹配而言, 特定模式匹配[26]、聚集模式(Burst)查询与发现[6]、周期模式发现[31]、主题模式(Motif)发现[32]、异常模式(Discord)发现[30]是其主要研究内容; 从关联分析来看, 局部相关或整体相关是主要研究角度, 同步相关[27]、滞后相关[28]以及突发相关是主要研究类型. 如何定义局部模式并指定模式窗口的大小、基于序列的相关(使用皮尔森Pearson系数)还是序列提取的特征的相关(须定义关联函数)、采用何种特征提取方法(例如: SVD、DFT)、建立何种索引和算法来高效报告相关等都是时序关联分析的重要研究方向; 就时序聚类而言, 由于时序维度高, 时序空间中的点将变得非常稀疏而难以具备聚集特性, 因此时序聚类仍面临很大挑战. 如何提取时序特征(feature extraction)、如何基于子空间(或投影)进行聚类、如何基于网格进行聚类、如何采用监督或约束的方法进行聚类、在分层聚类中聚类合并和分裂策略、如何定义聚类的密度函数等都是时序聚类的重要研究内容; 在时序分类中, 如何利用已有的机器学习分类方法, 例如: kNN分类、神经网络、多分类系统等是须考虑的重要问题. 目前, 时序分类研究相对较少, 在这方面仍有待进一步的深入. 在时序异常分析中, 基于距离的时序异常检测方法是研究的热点. 另外, 基于局部密度的时序异常挖掘算法和基于聚类的时序异常检测算法也是研究的重要方向. 在这个方面, 如何基于索引并考虑页面的I/O效率检测异常时序、如何定义对象在局部空间或聚类中的背离函数、如何定义网格并对网格进行合理分区以及如何综合距离、密度、聚类的异常检测方法都是重要的研究要点.
从维度方面来看, 基于空间的多维时序挖掘是研究的热点, 这包括: 移动对象跟踪[4]、运动捕获[7]等领域. 开发能适应噪声环境及各种变形的时序距离函数是首要解决的问题, 建立基于向量空间时序索引的搜索算法是重要的研究方向. 从现实应用层面来看, 相对于静态时序来说, 数据流、传感器网络将是时序新的应用环境. 目前, 基于数据流环境下的时序搜索技术是仍有待进一步研究的重要方向之一, 这其中包括高效的流时序模式匹配[26]、流时序关联分析(Correlation)[27-28]、流时序分段、流时序摘要(Summarization)、流时序聚类、流时序异常分析等方面. 由于数据流具有高速、不可存储的特性, 具有高效、一次扫描(One-Pass)和增量计算特征[28,49]的算法是研究的热点. 在传感器网络环境中, 数据点可能丢失、延迟, 传感器有限的电源和处理特性, 以及传感器数据非集中分布的特点, 使得高效而具有高精度的算法具有重要的应用价值. 如何建立正确的模型以预测或填充迷失的数据是重要的研究课题, 如何开发分布式时序处理算法非常重要.
从时序研究的效率和精度方面来看, 具有较高复杂度的时序算法一直是研究的热点. 例如: kNN算法、时序关联分析、时序主题发现、异常时序搜索、子时间序列搜索等都具有O(n2)的复杂度, 且常是重点研究对象. 由于时序高维度和大规模数据量的特性, 通常的计算一般须较长的时间, 目前许多研究者提出近似计算和anytime特性(在很短的时间可获得大部分的精度, 而且计算可随时终止; 然而, 可从中断点恢复计算, 且随计算时间的增加可获得更高的精度, 并最终获得精确的结果而退出)计算的思想是在效率和精度间达到平衡的新的思路. 基于近似的相似搜索技术已经成为一个重要的分支, 也是最近几年研究的热点. 从实际的需求方面来看, 成本敏感(Cost Sensitive)查询、噪声敏感(Noise Sensitive)查询、查询敏感(Query Sensitive)搜索、错误边界(Error Bound)控制查询、概率查询(Probabilistic Query)、近似查询(Approximate Query)、分布式查询(Distributed Query)将成为新的研究方向和热点.
3 高效时序相似搜索技术的应用
主要应用领域介绍与分析
高效的时序相似搜索技术已经在医学、网络流量、移动对象轨迹、生物序列、金融、音乐、天文观测、传感器网络等诸多领域的序列数据处理方面成功应用. 而且随着更多领域序列数据的出现, 新的应用领域将不断被开发出来. 随着不同领域数据量的急剧增加, 对设计的算法将提出更高的要求. 本文总结了时序几个主要的应用领域如下:
① 生物序列数据(例如: DNA序列)分析是当前生物信息学(Bioinformatics)的重要研究领域[1,31]. 尽管出现了许多研究成果, 但随着生物序列数据的急剧增加, 该领域仍存在广泛的研究前景;
② 移动对象跟踪与识别在许多场景下具有重要的应用价值[4-5]. 例如: 在辽阔的草原上，借助远程传感器网络，可以通过动物迁移路线挖掘来发现某些类型动物的迁移模式; 在运动领域, 可以通过对优秀运动的运动轨迹进行挖掘, 发现其有价值运动模式；在大型超市监控视频中，通过视频顾客运动轨迹挖掘, 以辅助商品的摆放; 在银行监视系统, 通过对顾客运行轨迹挖掘, 发现可疑的运动模式, 以辅助报警系统报警等. 这里应用的主要技术为多维的空间或时空度量方法: 例如: LCSS、EDR等;
③ 基于医学序列数据(例如: ECG、EEG)的相似搜索技术能够为医生提供重要的医学信息[26,33], 以发现某些异常的病例, 或辅助他们进行病例诊断; 基于音乐数据的相似匹配可以作为重要的工具, 以对音乐进行分类, 识别或搜索出同类的音乐[34];
④ 基于数据流方式的监控在网络、金融、天文等领域已经深入应用. 例如: 基于网络流量监控可以实时发现可疑的流量模式, 进而提高网络的安全管理; 基于金融数据流监控、分析可以提供重要的交易参考价值[27]; 基于天文流序列(如: gamma射线、太阳黑子sunshots等)的监控能实时监测一些重要的天文现象[6,26,28];
⑤ 基于传感器网络获得的序列数据处理是正在快速发展的领域. 由于传感器可以连续、自动地获得某些应用场景下的序列数据(如: 温度、湿度、风力、水文信息)[28,35], 结合传感器网络技术的时序相似搜索技术正在不断开发、应用. 由于传感器网络能够应用的场景非常广阔, 使得时序相似搜索技术在这个领域具有广阔的应用空间;
⑥ 基于图像的形状数据处理在考古学、法律诉讼、历史手迹(manuscript)、医学、运动捕获、机器人以及气象学等领域具有重要的应用价值. 例如: 发现考古学的文化迁移现象, 在法律诉讼中为真假图像的辨别提供帮助, 在历史手迹中识别类似的手迹或对他们进行分类等;
⑦ 基于时序相似模型的数据预测也是一个重要的应用分支. 例如: 在医学领域的放射治疗中, 可以针对患者呼吸运动的相似模型, 预测病人的病变位置; 在数据流环境下，时序数据可能由于网络拥塞或其它原因而滞后到达, 可以基于数据流序列的相似模型预测迷失的数据点.
不同领域典型算法介绍及性能比较
为了比较不同领域不同算法的性能, 下面就一些典型算法使用的数据集和效率进行介绍和讨论.
在关联分析算法中, StatStream算法[27]和BRAID[28]是典型的代表. StatStream算法使用DFT约简维度, 建立基于约简维度k的球形网格投影方法来寻找近邻. 扫描方法时间与数据流数目Ns平方成比例, 而StatStream系统的时间主要依赖网格的计算时间, 它与网格单元平均流数目Ngs的平方成比例, 显然Ngs<<Ns, 从而StatStream计算成本大大减少. 在基于秒记录的500G美国股票交易数据的实验中, 它能在150秒的时间内报告10, 000个以上数据流的相关, 而扫描方法最多只能报告700个左右. BRAID算法的主要思想是分解相关系数公式成增量计算形式和多辨析过滤策略(看小节). BRAID算法在25, 900至100, 000长的太阳黑子(Sunspots)、地震记录(Kursk)和尖峰序列(SpikeTrains)的实验中, 它最大的错误率大约1%, 能够检测半无限长的滞后相关. 在极端长度(例如: 107)的序列中, 它相对直接扫描实现方法(Naive)最高快40, 000倍; 因为, Naive的时间和空间复杂度为O(n), 而其空间复杂度为O(log n), 更新统计值仅须O(1)时间, 修改窗口信息值只须O(log n)时间. StatStream和BRAID的共同缺点在于难于选择一个合适的窗口尺寸以及不适应非等长的相关性监测.
在特定模式匹配中, FTW算法[35]和SPRING算法[26]非常典型而具代表性. FTW算法使用了低边界过滤、多辨析修剪和尽早终止距离计算三个关键技术(看第4节), 在长度从512到2048尺寸为25, 000至100, 000的静态数据集: 来自传感器的温度序列(Temperature)、股票金融时序FinTime以及自动生成的随机漫步序列(RandomWalk)测试中, 相对于文献[34]中的LB_PAA方法最高要快222倍, 而变化数据集尺寸、序列长度以及弯曲程度, 其计算时间只有稍微的变化. SPRING算法的主要思想为: 对长度为m的查询序列Q填充一个特别符号(例如: “*”号), 并使用一个弯曲矩阵STWM[26], 以记录长度为n的序列R的每个候选子序列的起始位置和累积距离值, 从而极大减少了DTW计算的成本. 报告范围查询模式的直接实现方法(Naive)需要O(n)大小的矩阵和每个滴答O(mn)次更新; 然而SPRING报告最好子序列仅须O(m2)大小矩阵和每个滴答O(m)次更新. SPRING使用包括文献[28]的Kursk、Sunpots和文献[35]的Temperature等数据集, 在使用长度为256的查询序列搜索时, 相对Naive最快达到650, 000倍.
在异常时序匹配中, 文献[30]提出的直接序列扫描方法是典型范例. 直接的异常时序搜索算法(Naive)通过两两比较对象间距离从而需要O(n2)次计算, 而文献[30]通过下面三个方法: 基于最近邻距离分布以确定异常门限值(的启发式策略、Filter-Refine过滤策略和尽早终止距离计算, 大大降低了搜索成本. 在序列长度为512共106条RandomWalk时序(磁盘空间)的测试实验中, 该算法仅仅花费27分钟的I/O时间和14分钟的CPU计算时间; 而在另一个长度为140由运动捕获、EEG记录和气象记录数据合成的(106条序列的数据集(磁盘空间)的测试实验中, Filter阶段和Refine阶段的时间分别为15分钟和16分钟.
4 高效时序相似搜索关键技术
从技术层面来分析, 为了提高时序相似搜索技术的效率, 一方面可通过修剪搜索空间来实现, 它即通过已计算出的距离信息来约间不必要的距离计算, 从而减少计算成本, 这里的技术基础是三角不等式和度量空间索引方法(例如: M-tree). 它们须配合启发式的搜索机制: 例如: 分支界限法(Branch and Bound)[36]、深度优先(Depth First, DF)[36]、最好优先(Best First, BF)[37]等一起使用. 常见的修剪策略包括: 三角不等式过滤、过滤精炼(Filter-Refine)策略(或多步过滤策略)等. 另一方面可通过提高距离计算的效率来达到, 有时须辅助向量空间索引方法(例如: R-tree)一起实现, 包括以下几种方法: (1) 转换原始空间(到距离计算成本远小的特征空间(中. 它要求特征空间具有”收缩”特性, 即, 特征空间的对象间距离小于原始空间的距离, 以确保不会产生漏报. (2) 多辨析计算方案(Multi-resolution), 它要求能寻找一个合适的多辨析函数和结构; (3) 边界过滤方法. 它要求寻找一个计算成本远低于原始距离函数的边界函数(包括: 低边界函数和上边界函数); (4) 尽早终止计算算法(Early Stopping); (5) 高效的距离计算算法, 例如: FastDTW[38]、FTW[35]以及SPRING[26]等算法. 另外, 高效的子序列搜索算法也是须重点考虑的问题, 例如: Dual-Match[39]、General-Match[40]算法等. 在上述方法中, 索引方法和时序转换是讨论较多且较成熟的技术, 本文不作讨论.
修剪搜索空间
问题描述
修剪搜索空间通过减少距离比较次数来降低计算成本. 它一般按照距离大小将时序对象划分成具有明显层次特征和聚类特性的度量空间索引结构, 然后通过三角不等式过滤来修剪不必要的索引分支或对象. 例如: 对于三个对象x, y, z, 如果它们的距离函数d满足三角不等式且距离d(x, y)和d(y, z)都已经计算出来, 那么则可利用x和z满足| d(x, y)−d(y, z)| ( d(x, z) ( d(x, y)+d(y, z)这样上下边界的信息, 并结合距离门限值(例如: ()来判断是否需要真正计算距离d(x, z), 以减少距离计算成本.
事实上, 修剪搜索空间的方法已经在时序的范围查询[8]、k近邻查询(kNN)[12]广泛运用. 另外, 可逆近邻(RkNN)查询[41]以及Skyline查询[42]也可运用. RNN的重要作用是识别查询对象q对其它对象的影响力. 对给定一集合D和一查询对象q, 可逆近邻查询RNN(q)检索出所有以q作为其近邻NN的对象. RkNN是RNN的推广, 它检索出以q作为其k个近邻的所有对象. 形式化地, , 对应q的k个近邻集合. 目前, 它在时序中仍然是一个未研究的课题, 我们正在进行这方面研究. Skyline查询从2001年提出以来一直是研究的热点. 给定一个d维的数据集D, 一个Skyline查询返回一个子集, 该子集中的任意一对象都不被D中其它对象所控制. 所谓控制关系是指给定d维空间中的多个对象, 如果对象p至少在某一维上优于另一个对象q, 而在其它的维度上都不比对象q差(p优于或等于q), 则说p控制q. 尽管, Skyline点不同于时序, 但高维的Skyline点可当作时序对象对待. 基于高维的Skyline查询算法是重要的研究方向之一.
研究概述与分析
(1) 三角不等式修剪方法
从三角不等式修剪方法的使用来看, 一方面可以通过预计算方法来实现, 例如: 文献[14]的kNN计算. 假定对象Q与对象R1,R2,…Rm的距离已知, 且R1,R2,…Rm和当前对象S两两之间的距离也已预计算, 现在要计算当前对象S是否为对象Q的kNN时, 就可利用三角不等式修剪方法. 具体过程如下: 首先求出对象Q与Ri的距离与Ri与S的距离之差的最大值(1(i(m), 即最大修剪距离maxPruneDist=; 然后将当前的kNN距离sofarDist[k]与maxPruneDist比较, 如果maxPruneDist>sofarDist[k], 那么对象S即可修剪掉.
另一方面可以通过度量索引来实现. 因为, 索引构造过程将会把对象间的距离信息计算好, 并存于索引当中, 从而在查询时可直接利用它们消除冗余计算. 这里的对象间距离一般是指一个聚类C的其它对象Oi相对于聚类中心对象Oc(或枢轴pivot对象, 即参考点)的距离. 因而, 开发好的基于度量空间的聚类算法也是重要的研究课题. 事实上早期的度量空间索引方法都利用了三角不等式修剪方法, 包括: VP-tree、M-tree和Sa-tree等. 文献[23]P. Ciaccia等人提出的M-tree是运用三角不等式修剪方法非常典型的多维索引例子, 它在范围查询和kNN查询中都可使用, 能修剪相应的索引分支和索引对象以消除大量的冗余计算. 但是应注意到不同的搜索策略将会极大地影响算法的效率. 比较成熟的搜索策略包括: 分支界限法、DF、BF等, 而在kNN算法中通常可使用一个保存了k个对象距离(相对于查询对象q)升序排列的优先队列(Prior Queue)以提高搜索效率. 我们认为这些搜索策略也是开发新的高效算法应遵循的基本框架. 文献[42]中的Chen等人基于M-tree将三角不等式修剪策略引入到动态的Skyline查询, 提出了度量空间动态Skyline查询方法. 其修剪策略概括为: 给定枢轴点为p的对象集合S及查询对象q, 则对象和q之间的距离下界和上界分别为LBi=|dist(q, p) − dist(p,oi)|和UBi= dist(q, p)+ dist(p,oi), 当发现一对象ok的上界不比oi的下界差(UBk(LBi)时, 则可修剪掉对象oi.
2001年Yu等人[43]提出了著名的kNN算法iDistance, 是一维度量索引利用三角不等式修剪的经典案例. 该算法根据参考点将每个聚类的高维数据点转换成单维数据点, 然后索引到一个B+树中, 并依据三角不等式进行修剪. 其本质思想在于: (1) 三角不等式保证了相对于参考点, 易判断查询点和数据点是否相似; (2) 数据点相当于参考点的距离可以排序且能被索引到一个B+树当中. 最近, Lian等人[44]提出了基于多枢轴(multipivot)成本模型的任意子空间的相似搜索方法, 它是结合统计分析、多枢轴点索引, 并利用三角不等式修剪的一维典型案例. 他们的主要贡献之一在于定义了两个可以运用三角不等式, 对象o与枢轴距离的一维边界函数: minscore(o(k))和maxscore(o(k))[44]. 这样便可以利用minscore(o(k))>Lp(q(k), piv(k))+(或maxscore(o(k))< Lp(q(k), piv(k)) − (修剪对象o, k指查询对象q或枢轴piv的子空间维度, .
(2) Filter-Refine修剪策略
前述基于度量索引的修剪策略的缺点在于: 不能适应非常高维(例如: 256维以上)的情形. 然而, 这个问题可以通过Filter-Refine修剪策略来解决. 在该策略下, 首先将原始空间Ro映射到低维空间Rf(也称为特征空间)中, 然后在Rf中使用类似于度量索引的三角不等式修剪方法, 以过滤掉大部分的不相似的对象, 此即Filter阶段的任务, 而在Refine阶段再在Ro中使用真实的距离函数进行相似比较获得精确的结果. 不过, 须强调的是Filter-Refine修剪策略是一个通用的修剪策略, 并非一定要在特征空间中才可使用, 而原始空间中也可使用, 例如: 文献[30]Yankov等人提出的直接序列扫描的Filter-Refine过滤算法, 这是因为在极高维(例如: 512维)的时序数据中, 结合启发策略的直接序列扫描算法可能比索引方法更有效.
传统的高维kNN算法是运用Filter-Refine经典的范例. 它分两步完成: ① Filter步骤通过在原始数据集(上的满足下届定理的索引空间( (或称作特征空间)中执行kNN算法获得一个初步的候选集(, 然后在原始空间(中确定(的对象o(与查询对象q的最大距离dmax=max{do(o, q)| o(}; ② Refine步骤再回到索引空间执行一个门限值为dmax的范围查询获得最终的候选集(={o(|df(((o), ((q))( dmax}, 然后在原始空间(中计算(的精确距离do并排序, 取距离最小的前k个对象作为最终结果. 这里, do和df分别指原始空间(和特征空间(的距离函数, ((o)指对象o在(中的映射对象. 然而, Seidl等人[45]研究发现传统算法dmax比实际的第k个近邻距离distNNk大, 从而造成候选集(比候选集(大得多(例如: (仅是(的40%), 引起大量冗余计算. 为此, 他们提出了一个适合高维数据的最优多步kNN算法. 该算法是迄今为止最好的遵循Filter-Refine框架的高维kNN算法, 其关键思想在于获得精确的dmax(dmax=distNNk). 这可通过下列步骤获得:
① 通过具有增量计算特性的kNN算法(例如: 采用DF策略的kNN算法)迭代地产生一个特征距离df升序排列的候选集;
② 利用一个升序排列的结果列表result存储k个近邻对象及其do距离, 并使用dmax存储result的第k个近邻距离result[k].key, 当出现do(dmax的新对象时, 将其插入result中并更新dmax(dmax=result[k].key), 同时移除距离do>dmax的对象, 经过一定步骤最终dmax将递减到实际的k近邻距离distNNk.
文献[41]中Tao等人最近将Filter-Refine过滤策略引入到RkNN查询中, 提出了度量空间的RkNN查询算法. 该算法首先利用Filter步骤在M-tree上执行一个DF遍历, 利用三角不等式修剪策略获得一个很小的初步候选集(; 然后利用Refine步骤通过维护一个最小堆(min-heap)在(上执行BF遍历, 进一步精炼候选(获得最终的候选集. 它是目前RkNN查询应用Filter-Refine过滤策略最好的范例.
多辨析加速方法
问题描述
多辨析(Multi-resolution)加速方法借助于数据的多辨析表示方法. 多辨析表示是一种由粗到精的多层表示数据方法, 高辨析率相对于低辨析率具有更高的数据表示精度和计算成本, 同时高辨析率表示与低辨析率表示具有某种函数依赖关系. 其工作过程为: 先在使用低辨析率过滤数据对象, 如果不能过滤掉则在更高一级的辨析率下过滤, 直至最高的辨析率或达到预先指定的某个终止条件. 这样, 如果能够在低辨析率表示下, 过滤掉大部分不满足条件的时间序列, 那么在整体上将会极大地节省计算成本. 图1[25]显示了文献[25]中基于段平均的多辨析率表示方法MSM. 从中可以看出, leve11层(最高层)是所有16个数据点的平均值表示, 而level4层是基于每两个相邻点分段的平均值表示. 这种方法的关键在于: 在保证无漏报的情况下, 寻找到一个时序特征抽取函数(例如: 段平均函数、haar小波变换等), 并找出低辨析层Si-1和高一级辨析层Si之间的函数关系, 例如文献[18]提出的函数: αp•Lp(Si-1)≤Lp(Si), 其中αp=(l指每段的段长)为常数.
研究概述与分析
(1) Lp距离函数情形
Chan等人[15]1999年最先提出了基于离散小波变换(DWT)的多辨析率过滤方案, 其主要思想可概述为: 给定两时间序列X和Y及其haar小波变换序列S和R, 它们的长度都为n(其中n≥2且为2的幂次方), 且定义, 那么X与Y的欧氏距离可以用小波系数(C D1 D2…Dn-1)递归得出, 其中, , , 其实质是小波系数表示的层多辨析结构. Yi等人[18]在2000年首次提出了针对任意Lp度量的两层多辨析率的段平均方法SM (Segment Mean), 即两时序等分段后的段平均序列之间的Lp距离的倍是原始序列Lp距离的下界函数. 同时也从理论上证明了段平均表示和段平均序列的haar小波变换的L2度量存在系数为的函数依赖关系.
文献[6]将基于haar小波的多辨析搜索方法引入到变长的子序列模式检测中, 算法主要依赖于提出的多层次小波树(Shifted Wavelet Tree, SWT). SWT层次越高聚集的时间跨度越大段数越少, 同层的各分段半重叠, 这样长为w(w≤2i)的任意子序列将被包含在SWT中的第i+1层的某个分段中. SWT很好地解决了子序列模式持续时间长度不好确定的问题. 2005年Sakurai等人[28]提出的监控流滞后相关的BRAID算法也利用了基于平均值的多辨析计算思想, 他们将其称为平滑(smoothing). 2007年Xiang等人[25]将文献[18]的两层辨析率方法推广到多层, 并将其应用到数据流的相似匹配中, 提出了一种多辨析率的层次段平均表示方法(Multi-scaled Segment Mean, MSM)[25], 该方法实际是文献[18]中取段长为l=2时2层多辨析率段平均方法SM和2层多辨析率haar小波变换方法的推广(如图1所示).
从以上的案例可以发现, 如何寻找适合多辨析的距离函数或结构至关重要, 同时它也是可能的研究方向之一.
(2) DTW距离函数情形
2004年由Salvador等人[38]提出的FastDTW, 是多辨析率方法使用的另一范例, 也是第一个出现的加速DTW执行的算法. 其主要思想是: 先粗略计算然后再逐步修正, 通过图2[38]可以说明, 它包括三个关键操作, 即变粗糙(Coarsening)、投影(Projecting)以及精炼(Refinement). 由于低辨析率弯曲路径可以作为高辨析率弯曲路径的参考, 从而可约束其搜索范围, 进而减少计算量. 文献[38]指出在保持r较小的情况下, 算法的运行时间复杂度和空间复杂度都近似为O(N), N为累积矩阵对角线中方格的数目. 2005年由Sakurai等人[35]提出的FTW算法利用多粒度(对应不同的粗糙程度)逐步求精, 使得出现在累积矩阵中的动态弯曲路径的搜索范围从起点到终点逐渐减少, 计算逐渐精确, 它是多辨析方法的又一范例. 文献[35]指出FTW算法相对当时最好的DTW算法效率提高了222倍以上, 实际上它是目前最好的DTW算法. 综合以上两例可以看出, DTW算法的累积矩阵是多辨析计算的重要基础.
边界距离过滤方法
问题描述
边界过滤方法是通过加速时序距离计算的效率来减少计算成本. 其关键在于寻找一个低计算成本、相对真实距离DRL更小的下界函数DLB以过滤掉满足DLB≥ε的时间序列, 或一个低计算成本、稍大于DRL的上界函数DUB, 以选出那些满足DUB≤ε的时间序列. 形式化地, 对于两时间序列S和Q, (DLB1和DLB2, 且DLB1≤DLB2≤DRL, 则称DLB2是比DLB1严格的低边界距离函数, 且称DLB1(S,Q)下界于DLB2(S,Q), DLB2(S,Q)下界于DRL(S,Q). 类似地, (DUB1和DUB2, 且DUB1(DUB2(DRL, 则称DUB2是DUB1比严格的上边界距离函数. 不过注意, 这种策略需要一个后处理过程来保持没有漏报.
研究概述与分析
(1) Lp度量函数
文献[36]最早定义了基于R-tree的kNN查询的二个边界距离函数: 即查询q和节点N的子树任意点的下界距离MinDist(N,q), 查询q与节点N中最近点的上界距离MinMaxDist(N, q). 该算法从根开始访问, 然后递归地访问与查询q保持最小MinDist距离的节点, 在回朔到上层的过程中, 它仅访问比当前k近邻距离更小的节点, 同时利用上下边界距离修剪分支节点或叶子对象. 文献[46]中的Liu等人通过harr小波变换提出了基于欧氏距离的时间序列的严格上下界函数, 然后把它们运用到时序的相似搜索中. 其主要思想反映在文献[46]的定理1中. 但我们发现运用定理1在进行搜索时并不能明显改善搜索时间, 主要原因在于他们采用顺序扫描的方法; 之后, 文献[47]以预计算的方式建立索引并利用聚类和三角不等式过滤方法提高了他们的算法.
(2) DTW距离函数
由于DTW算法的时间复杂度为O(nm), 相对Lp的复杂度O(n)来说时间成本过大. 为此, 许多研究者针对DTW提出了许多边界距离函数, 这包括LB_Yi[33]、LB_Kim[48]、LB_Keogh[12]、LB_PAA[34]、LB_HUST[29]、LB_Z[49]、UB_Z[49]等. 下面我们将对其原理进行深入的分析和讨论.
LB_Yi是由Yi[33]等人提出的首个针对DTW的低边界函数. 它利用了下面的一个事实, 即一条时间序列比另一序列的最大值(或最小值)要大(或小)的所有点, 将至少为DTW贡献它们与另一序列的最大值(或最小值)的差值的平方距离. 此事实也即两序列值的范围分别为不相交(disjoint)、交错(overlap)以及包含(enclose)三种情形下所得出的下界距离Dlb. 但是, LB_Yi只能起到有限的过滤作用.
之后, Kim等人[48]提出了比LB_Yi更接近真实DTW的下界距离函数LB_Kim, 其主要思想是: 首先抽取两序列的四个特征值(即第一个元素值、最后一个元素值、最大值以及最小值), 然后取两序列对应特征值的绝对差值中的最大值作为低边界距离. LB_Kim使用L∞距离度量函数作为其基本度量函数, 而对其它形式没有讨论. 为此, Park等人[50]扩展了LB_Kim在使用L1距离度量时的情况, 为了方便我们把它称为NLB_Kim. 上述的LB_Kim和NLB_Kim相对于LB_Yi, 其距离更接近于Dtw.
显然, LB_Yi和LB_Kim利用最大值、最小值或首尾元素时序特征得到的下界距离不可能很接近DTW真实下界距离. 为此, Keogh等人利用全局的时间弯曲约束, 从约束动态弯曲路径的上下边界入手, 提出了下界距离函数LB_Keogh[12]. LB_Keogh的优点在于: 它比LB_Kim和LB_Yi更接近真实DTW下界距离, 同时支持形状时序表示和度量保持旋转不变特性. 然而, 它不满足三角不等式, 不能在低维索引空间中使用. 为此, Keogh对其进行了扩展, 将依据PAA[18]分段后由段平均组成的数据序列与查询序列, 依照类似于LB_Keogh的定义得到了索引空间中的下界距离, 即LB_PAA. LB_PAA下界于LB_Keogh, 这样便可以对DTW进行精确的索引. 但LB_PAA相对文献[34]的LB_PAA来说, 并不是严格的索引空间的低边界距离. 将文献[34]中低边界距离称为NLB_PAA, 则有LB_PAA≤NLB_PAA. 它们的主要区别在于: LB_PAA取时序上下边界曲线(文献[34]将其称为信封-Envelope)分段后的绝对最大值和绝对最小值作边界约束, 而NLB_PAA取时序信封分段后的上边界段平均值和下边界段平均值作约束.
虽然, LB_Keogh是很好的下界距离函数, 然而它不是一个对称的距离函数, 即D(S,Q)≠D(Q,S), 这使得它不能用于度量时序聚类的距离. 因为, 使用D(S,Q)计算时发现时序S和Q属于同一聚类, 然而使用D(Q,S)计算时却发现S和Q可能属于不同聚类[29]. 为此, Li等人提出了一个对称的低边界度量函数LB_HUST[29], 并把它应用于时间序列的聚类中. LB_HUST中的思路非常直观, 即: 既然一条时间序列可以有上下边界, 那么另一条时间序列为什么不可以有呢, 因为它们处于平等的位置. LB_HUST下届于LB_Keogh, 即DLB_HUST(S,T)≤DLB_Keogh(S,T), 当将其应用于聚类时, 可以定义聚类的低边界距离函数LB_HUSTcluster(CS,CT), 其定义类似于LB_HUST, 只是CS和CT指两个时间序列聚类.
然而, 上面提到的所有DTW的边界距离函数都不具备增量计算的特性. 换句话说, 对于仅一个元素不同的两个相邻的子序列Si和Si+1, 以及一个查询序列Q, 如果采用前述的边界函数, 则须分别计算DTW(Q, Si)和DTW(Q, Si+1), 从而计算DTW(Q, Si+1)时并不能利用前面DTW(Q, Si)的计算结果, 引起很多冗余计算[49]. 为此, 我国学者Zhou等人[49]最近同时提出了针对于DTW的低边界距离函数LB_Z和上边界函数UB_Z解决了上述问题, 使得他们的边界距离可以运用到高速的数据流环境中. 而且, LB_Z和UB_Z是迄今为止最好的低边界和上边界函数. LB_Z和UB_Z利用了DTW两个重要的特性: (1) 在计算出最终的动态弯曲距离((n, m)=DTW(Q, S)后, 其它的((i, j)也已计算出; (2) DTW计算既可前向(forward)计算, 也可后向(backward)计算.
为了对比, 我们将上述的边界距离函数总结于表2中. 实际上许多时序相似搜索技术都可运用边界技术, 寻求新的边界函数也是重要的研究课题之一.
Table 2 Comparison of bounding distance function
表2 边界距离函数比较
名称
公式
时间成本
适应范围
出现时间
技术思路
MinDist
MinMaxDist
文献[36]
-
L2
1995
对角线端点性质及R-tree中最小边界矩阵MBR每边必包含至少一个点的性质
LB_Yi
文献[33]
O(n)
DTW
1998
利用最大值和最小值特征
LB_Kim
文献[48]
O(n)
DTW
2001
利用首尾元素及最大值、最小值特征
LB_Keogh
文献[12]
O(n)
DTW
2002
利用全局约束缩短累积矩阵中动态弯曲路径的搜索范围和局部极值特征
LB_PAA
文献[34]
O(n)
DTW
2003
利用LB_Keogh、分段线性表示和上下边界平均值
LB_HUST
文献[29]
O(n)
DTW
2006
两个时间序列地位是平等的, 即对称性
见文献[46]
文献[46]
O(n)
L2
2006
利用小波变换中的欧氏距离不变性
LB_Z,UB_Z
文献[49]
O(n)
DTW
2008
利用DTW累积距离特性及双向计算策略, 满足增量计算特性
Early Stopping
尽早终止Early Stopping算法的思想是相当直观的, 它是指在计算两个对象的距离时, 发现本次距离计算所积累的距离信息已经足够判断结果, 则放弃本次计算或本次计算的部分计算(例如: DTW累积计算矩阵的某些单元格)来缩减计算成本. 这种消除冗余计算的方法对于高维距离计算非常有效, 不但能减少CPU运行时间, 同时也可减少部分I/O成本.
(1) Lp距离函数
Lp距离函数的形式为: , 显然当p≠(时, Lp具有单调性, 故在在计算两n维时序R和S的Lp距离Lp(R, S), 当计算到第k维(1(k<n)发现距离超过门限值ε时, 则可终止后面n−k维的距离计算, 此即Lp及早终止计算思想. 另外, 针对于L2的一个改进措施是, 消除距离的平方根计算, 直接使用ε2进行距离比较. 此方法可以推广到Lp-norm(p(1且p((). 例如: 文献[7,30]就利用这种方法来加速距离计算.
(2) DTW距离函数
DTW距离函数运用动态规划算法思想实现, 它具有三个重要的性质: 即从两序列的起始点(s1, q1)开始至终止点(sm, qn)结束; 相邻单元格在弯曲路径w是相邻的(连续性); 弯曲路径w在时间上是递增的(单调性). 因此, DTW算法存在行和列的累加效应, 即该行(或列)的当前单元格的累加距离值将不超过该行(或列)之后单元格的累加距离值. 这样, 将有两种方法来加速DTW距离计算. 一种方法是当累积矩阵的当前值超过门限值ε时, 可放弃本次DTW距离计算, 从而可过滤掉当前正在比较的序列; 另一种是当累加矩阵中出现比当前累积值大的单元格时, 那么该单元格后的行(或列)之后的所有单元格的计算可以终止, 而从对角线的新单元格开始计算, 此即缩小搜索范围来减少计算成本. 如果是kNN计算, 还可以维护第k个当前最好的近邻距离值Dcb, 并在与其它的时序对象比较时不断地更新它, 通过使用它作为门限值来过滤其它时序. 显然, Dcb会不断减少从而使过滤时序越来越容易. 文献[35]的FTW算法是运用这种Early Stopping算法思想很好的例子, 不过须指出的是: FTW还同时运用了多辨析计算和低边界函数过滤方法.
子序列搜索策略
通过长度为m的查询序列Q, 在长度为n的长序列R中搜索相似的子序列, 直接实现的方法具有O(mn)的时间复杂度. 通常n>>m, 因而子序列搜索具有极高的时间成本. 为了提高效率, 通常的子序列搜索分成以下几种类型: (1) 基于空间索引和序列划分的子序列搜索方法, 包括: GEMINI框架[10]、Dual-Match算法[39]、General-Match算法[40]、Rank-Match算法[51]等. 这些方法中需要考虑: 查询序列和原始序列的划分方法以及划分窗口的大小; 索引的磁盘页面I/O效率; 特征抽取方法、窗口尺寸效应以及点过滤效应[39]等; (2) 基于直接距离计算的子序列搜索方法[26]. 由于Lp距离对噪声敏感且要求序列等长, 而DTW算法克服了这些缺点, 故这类算法通常采用快速DTW距离计算方法来实现, 例如: FastDTW算法[38]、FTW算法[35]以及SPRING算法[26]; (3) 转换成字符的前缀和后缀索引的子序列搜索方法[50,52], 这种方法的好处在于可以利用成熟的字符搜索技术. (4) 基于模型的子序列搜索方法: LandMarks模型[2]、SpADe模型[13]以及文献[3]提出的算法等. 这些算法将序列转换成对应的模式, 然后定义模式距离函数进行子序列搜索. 进一步地, 基于kNN子序列算法[51]具有更高的时间成本, 相对于前述的范围查询算法它将是重要的研究方向.
2001年Moon等人[39]在分析了GEMINI框架引起多报的三个原因: 即特征抽取、窗口尺寸效应和点过滤效应之后, 提出了与GEMINI相反的子序列划分策略: 将数据序列S划分成长度为ω的离散子序列, 而将查询序列Q划分成Len(Q)−ω+1个滑动子查询序列, 此即Dual-Match方法[39]. 然而, 它仍留下窗口尺寸效应问题未解决, 为此, 2002年Moon等人又提出了通用的子序列搜索方法, 即General-Match[40], 此方法结合了GEMINI和Dual-Match的共同优点: 既能运用GEMINI框架中的大窗口, 又能利用Dual-Match中的点过滤效应. 它将数据序列划分成J-滑动窗口(J-sliding windows), 将查询序列划分为J-离散窗口(J-disjoint windows). 不同于前述Dual-Match和General-Match的范围搜索方法, 2007年文献[51]Han等人在它们的基础上提出子序列的kNN排序算法Rank-Match, 它的主要思想在于: (1) 通过最小距离匹配窗口对MDMWP来定义所有匹配的窗口对中的最小边界距离; (2) 利用延迟分组子序列检索方法提高搜索的I/O效率.
不同于基于空间索引和直接距离的子序列搜索方法, 文献[52]提出了一种适应变长序列的子序列匹配的后缀树方法: 通过增量构造把数据时序的所有后缀索引在后缀树中, 并在搜索过程中如果累积矩阵某行中所有列的累积距离都大于ε即终止后面元素的匹配直接判断两序列不相似; 文献[52]基于前缀查询的思想: 如果时间序列S和查询序列Q, 它们的弯曲距离在ε范围内, 那么至少有一个查询前缀序列满足它们与S的距离在ε内, 扩展了使用L1距离的前缀查询. 而不同于序列转换成字符的方法, 基于模型的方法通过抽取序列的特征, 并建立基于特征的距离函数来匹配子序列. 文献[2]通过定义界标序列距离函数来匹配模式, 文献[3]定义终端点序列距离函数在线搜索金融流子序列, 而文献[13]提出了一种能够适用时间和幅度的偏移和缩放以及噪声, 基于流时序形状的模式检测方法SpADe. 然而, 一般来说基于模型的子序列匹配方法可能会有较低的精度.
5 近似相似搜索技术
近似相似搜索通过放松相似查询的正确性限制来减少搜索成本, 它已经发展成为高维相似搜索技术的一个重要分支. 这是因为: (1) 通常等待完成精确相似搜索须较长的时间, 而用户可能仅希望快速获得最先出现的近似结果; (2) 用户理解的相似查询跟实际的实现存在差距, 他可能希望通过循环反馈的方式来指定查询, 从而需要获得初步结果以改进查询对象或距离函数. 文献[53]指出通常以精确相似搜索算法1%的成本可以获取99%的搜索结果, 这表明近似相似搜索具有重要的实践意义.
前沿研究成果介绍与讨论
近似相似搜索算法设计的关键在于: (1) 如何在精度(precision)和召回率(recall)之间保持平衡; (2) 如何在运行效率和运行成本上取得平衡. 例如: 如果在5%的时间内已经获得95%的结果, 而剩余5%的结果将需95%的运行时间, 那么可终止算法搜索过程; (3) 如何快速地修剪搜索空间, 包括: 整体的搜索空间(例如: 基于M-tree修剪空间的方法)或单一距离计算空间(一般为尽早终止算法)两种类型; (4) 如何高效地转换空间并能保留较多的原始距离信息, 这类方法包括: 特征抽取、维度约简(例如: SVD方法)以及映射(或称为嵌入Embedding)对象等技术; (5) 如何提供算法的概率保证, 这包括: 利用距离分布信息建立概率模型, 通过概率条件(例如: 基于距离标准和基于精度标准)终止搜索过程等.
基于传统技术(如: 基于索引修剪搜索空间、空间转换或维度约简、特征抽取)是近似搜索技术的一个重要分支. 1998年Zezula等人[54]提出了三种基于M-tree的近似相似搜索算法: (1) 通过修剪搜索空间来缩减当前kNN查询的搜索半径, 并保持相对距离错误为门限值(的算法; (2) 利用距离分布建立概率模型, 并在发现的更好结果不超过用户指定的概率(时终止搜索的算法; (3) 当第k个距离提高低于门限值(时, 然后终止搜索的算法; Castelli等人[55]将同质的数据点分组成聚类, 然后利用奇异值分解SVD技术分别对每个聚类进行维度约简, 提出了近似处理近邻查询的CSVD(Clustering with Singular Value Decomposition)算法; Gionis等人[56]提出了基于局部敏感哈希(Locality-Sensitive Hashing, LSH)方法的提高算法, 它转换一个D维对象p成为一个包含C位二进制的向量v(p), 并近似两个对象间的距离为v(p)的编辑距离, 然后使用哈希技术索引v(p). 其缺点在于仅适应于L1距离度量.
基于对象映射(有时也称为嵌入, Embedding)是近似搜索技术的另一个重要分支. 这类技术的关键在于: (1) 如何定义一个较好的映射函数, 以保证映射空间的距离能够保留较多原始空间信息; (2) 映射函数是否具有“收缩”性质, 即映射空间距离小于原始空间距离; (3) 映射函数是否具有“距离保序”(proximity preservation)性质, 即原始空间的距离顺序关系在映射空间中仍然不变. 映射技术通常使用异常(distortion)和压缩(stress)两个指标, 分别评估映射空间中单一距离和整个映射空间距离的背离程度. Faloutsos等人[57]从正交投影的角度首次提出了映射度量空间对象到K维欧氏空间的高效算法FastMap, 它既可作为高效近似相似搜索方法也可作为数据挖掘可视化工具; Wang等人[58]从应用点积的角度提出了另一对象映射方法MetricMap, 它类似于FastMap算法, 但具有更高的效率.
提供概率保证的近似相似搜索算法也是一种重要的类型, 例如: PAC算法[59]、文献[53,60,61]中的算法. PAC算法的主要思想在于避免搜索太靠近查询对象, 换句话说是在提供质量保证(1−(精度和1−(概率)的基础下尽早终止搜索, 以避免太多的时间成本花费在较少的精度提高上; 文献[53]基于紧密的球面分区方法(例如: SA-tree)和增量的近邻搜索算法, 提出了增量的概率近似搜索算法; 文献[60]通过自动获取距离分布信息来提供概率保证, 以缩减搜索过程中度量空间枢轴的半径; Bennett等人[61]通过K聚类算法和数据高斯分布假设, 并索引构造阶段估计均值向量和协方差矩阵参数, 引入了基于索引聚类密度的概率kNN近似搜索算法DBIN(density based indexing).
综上可以看出, 近似搜索算法一方面可以利用精确搜索算法的原有技术, 另一方面又需开发新的算法, 例如: 文献[62]中的基于有序排列的方法以及文献[63]中基于基因搜索的近似算法.
小结
目前, 已经出现大量基于高维的近似相似搜索技术. 尽管它们各不相同, 一般可从四个角度对它们进行分类: (1) 使用的数据类型-基于向量空间(VS)还是基于度量空间(MS), VS又可分为基于Lp的VSLp和自由定义距离函数的VS两种; (2) 使用的近似类型-通过改变搜索空间(CS)还是减少比较计算的方法(RC), RC又可分为减少整体比较空间的RCAP和尽早结束单次比较计算的RCES; (3) 结果的质量保证-分成没有保证(NG)、确定的保证(DG)以及概率的保证(PG)三种类型, 而PG包括基于参数的概率质量保证PGpar和无参数的概率质量保证PGupar; (4) 交互方式-分为静态的方法(SA)和交互的方法(IA), 在SA中用户不能自由选择参数, 而在IA中用户可在查询时指定参数. 我们总结上面一些典型的近似相似搜索算法于表3中:
Table 3 Classification of algorithms for approximate similarity search
表3 近似相似搜索算法分类
算法名称 数据类型 近似类型 质量保证 用户交互
LSH[56] VSL1 CS PGupar SA
DBIN[61] VS RCES PGpar IA
CSVD[55] VS CS NG IA
FastMap[57] MS CS NG SA
Approximate Search with M-tree[54] MS RCAP/RCES DG/NG IA
PAC[59] MS RC PGupar IA
Probabilistic Proximity Search[60] MS RCAP PGupar IA
Probabilistic Incremental Search[53] MS RCES NG IA
Genetic Search[63] MS RC NG IA
6 总结和展望
随着时序相似搜索技术研究的不断进步, 其应用领域广度正在不断扩展, 它已经扩展到金融数据分析、医学诊断、DNA序列分析、网络流量监控、动物学图像分析、考古学文化迁移、视频监视、气象分析、天文学监控、传感器网络监视、移动对象跟踪以及运动捕获等诸多领域, 其应用深度也在不断取得新的进展. 然而, 随着时序相似搜索技术应用领域的不断扩展、时序数据的高速增长(例如: DNA序列数据)以及新的应用场景的变化, 使得它仍然面临巨大的挑战. 一方面要求进一步提高算法的精度, 因为许多算法计算出的结果仍然不能满足实际的需要; 另一方面要求最大限度地降低算法的成本, 这在kNN查询、RkNN查询、Skyline查询、关联时序搜索、异常时序搜索、主题时序搜索等应用场景下尤为突出. 通过对国内外的已有成果的总结、分析和讨论, 我们认为高效的时序相似搜索技术仍然具有广阔的前景, 以下几个主题将可能成为未来的研究方向或研究热点:
(1) 基于数据安全和数据压缩的时序相似搜索技术将成为一个重要的研究领域[64-65]. 实际上, 这是源于数据隐藏和隐私保护(Privacy Preservation)的实现需要. 而且, 基于隐私保护的数据安全技术已经成为目前的研究热点. 例如: 最近文献[64]Papadimitriou等人研究了在时序中引入干扰(perturbation)造成部分不确定数据来隐藏时序的关键数据点, 同时不丢失时序的固有模式并保持较好的数据压缩性的方法.
(2) 基于生物信息学(Bioinformatics)序列数据的相似搜索技术仍将是重要的研究方向[1,31]. 近年来, 随着生命科学的快速发展, 产生了海量的生物序列数据(例如: DNA序列), 如何处理这样大规模的数据是生物学家迫切需要解决的问题. 相似搜索技术是获取生物数据属性的一种重要方法. 尽管, 这个方面取得了部分研究成果, 但仍需提出新的算法或进一步提高算法的性能.
(3) 基于数据流和传感器网络动态环境下时序相似搜索技术依然是重要的研究方向[3,13,26,28,49]. 一方面, 传感器网络具有广阔的应用前景, 另一方面基于数据流的时序相似搜索具有不同于静态时序处理方法的应用要求, 例如: 不可存储、一次扫描、实时处理等特点. 由于数据流和传感器网络存在安全需要, 因而结合安全技术的数据流相似搜索技术也是新的研究热点, 例如: 基于授权数据流的相似搜索[66].
(4) 基于分布式处理和并行处理方法的时序相似搜索技术将是一个新的研究方向. 首先, 并行处理是提高海量时序处理效率的一种有效方式; 其次, 传统的时序相似搜索技术都是基于集中处理方式. 而实际上, 在很多的场景下海量的时序数据将分布在不同地方, 分布式处理方式是时序相似搜索的必然要求. 例如: 最近文献[67]提出的可扩展分布式R-tree索引SD-Rtree.
(5) 基于概率和不确定数据(Uncertain Data)的时序相似搜索方法将是新的研究热点之一. 一方面概率的相似搜索可以在成本和效率上达到一种平衡, 同时它能提供可确定的质量保证; 另一方面在一些特殊的场合(例如: 传感器网络、移动对象)存在不确定数据是一种必然现象[68], 这些数据通常要求统计概率处理方法. 例如: 空间移动轨迹不确定数据的处理.
(6) 基于移动轨迹的相似搜索技术仍是研究的重要方向. 一方面移动轨迹在一些场合(例如: 交通管理、军事情报等)具有重要的应用价值, 且它具有较强的安全需求; 另一方面基于移动轨迹的研究仍有待进一步深入, 大部分的研究成果基于空间模型进行匹配. 因而, 研究基于时间和空间的移动轨迹跟踪仍需继续研究, 同时结合安全技术的移动轨迹相似搜索方法将是重要的研究方向, 例如: 弹道数据的版权保护问题、基于授权的空间索引[65]等.
综上, 本文详细综述了时间序列中的高效相似搜索算法, 提出了未来在该技术上要取得进一步进展得几个重要研究方向和趋势. 我们已经拥有了部分的研究成果, 同时也正在从事进一步的研究.
参考文献
[1] ZHU YY, Xiong Y. DNA Sequence Data Mining Technique. Journal of Software, 2007, 18(11): 2766-2781 (in Chinese)
[2] Perng CS, Wang H, Zhang S, et al. Landmarks: A New Model for Similarity-Based Pattern Querying in Time Series Databases//Proc. of IEEE ICDE Conf., San Diego, CA, 2000: 33-42
[3] Wu H, Salzberg B, Zhang D. Online event-driven subsequence matching over financial data streams//Proc. of ACM SIGMOD Conference. Paris, 2004: 23–34
[4] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories//Proc. of 18th Int'l Conf. on Data Engineering(ICDE'02). San Jose, CA, 2002: 673-684
[5] Chen L, Ozsu MT, Oria V. Robust and fast similarity search for moving object trajectories//Proc. ACM SIGMOD Conference. Baltimore, Maryland, 2005: 491–502
[6] Zhu Y, Shasha D. Efficient elastic burst detection in data streams//Proc. of the 9th ACM SIGKDD. Washington, 2003: 336-345
[7] E. Keogh, T. Palpanas, V. B. Zordan, et al. Indexing Large Human-Motion Databases //Proc. of VLDB Conference, Toronto, Canada, 2004: 780-791
[8] Agrawal R, Faloutsos C, Swami A. Efficient similarity search in sequence databases//Proc. of the 4th Int’l Conf. on Foundations of Data Organization and Algorithms(FODO'93). Chicago, 1993: 69-84
[9] Berndt DJ, Clifford J. Finding patterns in time series: a dynamic programming approach//Proc. of the Advances in Knowledge Discovery and Data Mining. Menlo Park, CA, 1996: 229-248
[10] Faloutsos C, Ranganathan M, Manolopoulos Y. Fast subsequence matching in time-series databases//Proc. of ACM SIGMOD Conference. Minneapolis, Minnesota, 1994: 419-429
[11] Beckmann N, Kriegel H-P, Schneider R, et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles//Proc. of ACM SIGMOD Conf., Atlantic city, NJ, 1990: 322-331
[12] Keogh E. Exact Indexing of Dynamic Time Warping//Proc. of the VLDB Conf. on Very Large Data Bases. Hong Kong, China, 2002: 406-417
[13] Chen Y, Nascimento MA, Ooi B C, et al. SpADe: On Shape-based Pattern Detection in Streaming Time Series//Proc. of IEEE ICDE Conf., Istanbul, 2007: 786-795
[14] Chen L, Ng RT. On the marriage of Lp-norms and edit distance//Proc. of the 30th Int'l Conf. on Very Large Data Bases(VLDB'04). Toronto, 2004: 792-804
[15] Chan Franky, Fu Wai-chee. Efficient time series matching by Wavelets//Proc. of the 15th IEEE Int’l Conf. on Data Engineering(ICDE'99). Sydney, Australia, Mar. 1999: 126-133
[16] Korn F, Jagadish H, Faloutsos C. Efficiently supporting ad hoc queries in large datasets of time sequences//Proc. of ACM SIGMOD Conf., Birmingham , 1997: 289-300
[17] Qiuxia Chen, Lei Chen, Xiang Lian, et al. Indexable PLA for Efficient Similarity Search//Proc. of ACM VLDB Conference. Vienna, Austria, Sep. 2007, pp. 435–446
[18] Yi BK, Faloutsos C. Fast time sequence indexing for arbitrary Lp norms//Proc. of the 26th Int’l Conf. on Very Large Databases(VLDB 2000). Cairo Egypt, 2000: 385-394
[19] Keogh E. Chakrabarti K, Pazzani M. Locally adaptive dimensionality reduction for indexing large time series databases//Proc. of ACM SIGMOD Conf., Santa Barbara, California, 2001: 151-162
[20] Cai Y, Ng R. Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials//Proc. of ACM SIGMOD, Paris, France: ACM, 2004: 599-610
[21] Lin Jessica, Keogh E, Londardi S, et al. A Symbolic Representation of Time Series, with Implications for Streaming Algorithms//Workshop on Research Issues in Data Mining and Knowledge Discovery, Proc. of the 8th ACM SIGMOD. San Diego, CA, 2003: 2-11
[22] Fu A, Chan P, Cheung Y, Moon Y. Dynamical VP-tree indexing for n-nearest neighbor search given pair-wise distances. VLDB Journal, 2000, 9(2):154-173
[23] Ciaccia P, Patella M, Zezula P. M-tree: An efficient access method for similarity search in metric spaces//Proc of the 23rd Int’l Conf. on Very Large Databases. Athens, Greece, 1997: 426-435
[24] Navarro G.. Searching in Metric Spaces by Spatial Approximation. VLDB Journal, 2002, 11(1): 28-46
[25] Lian X, Chen L, Jeffrey Xu Yu, et al. Similarity Match Over High Speed Time-Series Streams//Proc of IEEE 23rd Int’l Conf. on Data Engineering(ICDE'07). Istanbul, 2007: 1086-1095
[26] Sakurai Y, Faloutsos C, Yamamuro M. Stream Monitoring under the Time Warping Distance//Proc. of IEEE 23th Int'l Conf. on Data Engineering(ICDE'07). Istanbul, 2007: 1046-1055
[27] Zhu YY, Shasha D. StatStream:Statistical monitoring of thousands of data streams in real time//Proc. of VLDB Conf., Hong Kong, 2002: 358-369
[28] Sakurai Y, Papadimitriou S, Faloutsos C. Braid: Stream mining through group lag correlations//Proc. of ACM SIGMOD Conference, Baltimore, Maryland, Jun. 2005, pp. 599–610.
[29] Li J, Wang Y, Li X. LB HUST: A Symmetrical Boundary Distance for Clustering Time Series//Proc. of the 9th Int'l Conf. on Information Technology(ICIT'06). New Delhi, India, 2006: 203-208
[30] Yankov D, Keogh E, Rebbapragada U. Disk Aware Discord Discovery: Finding Unusual Time Series in Terabyte Sized Datasets// Proc of IEEE ICDE Conf., Istanbul, 2007: 381-390
[31] Zhang M, Kao R, Cheung D W, and Yip K Y. Mining Periodic Patterns with Gap Requirement from Sequences. ACM Transactions on Knowledge Discovery from Data, 1(2), 2007: 1-39
[32] Jiang T, Feng YC, Zhang B, et al. L. Finding Motifs of Financial Data Streams in Real Time. Kang et al. (Eds.): ISICA 2008, LNCS 5370, 2008: 546-555
[33] Yi BK, Jagadish HV, Faloutsos C. Efficient retrieval of similar time sequences under time warping//Proc. of 14th Int’l Conf. of Data Engineering(ICDE'98). Orlando, Florida, 1998: 23-27
[34] Zhu Y, Shasha D. Warping indexes with envelope transforms for query by humming//Proc. of ACM SIGMOD Int. Conf. on Management of Data(SIGMOD'03). San Diego, California, 2003: 181-192
[35] Sakurai Y, Yoshikawa M, Faloutsos C. FTW: fast similarity search under the time warping distance//Proc. ACM Symp. on Principles of Database Systems, Baltimore, Maryland, 2005: 326-337
[36] Roussopoulos N, Kelley S, Vincent F. Nearest Neighbor Queries//Proc. of ACM SIGMOD Conference, San Jose, CA, 1995: 71-79
[37] Hjaltason G R, Samet H. Distance Browsing in Spatial Databases. ACM Transaction on Database Systems, Vol. 24, No. 2, June 1999: 265-318
[38] Salvador S, Chan P. FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space//Proc. of KDD Workshop on Mining Temporal and Sequential Data, Seattle, WA, 2004: 70–80
[39] Moon Y S, Whang KY, and Loh WK. Duality-based subsequence matching in time-series databases//Proc. the 17th Int'l Conf. on Data Engineering. Heidelberg, Germany, 2001: 263-272
[40] Moon YS, Whang K, and Han W. General match: A subsequence matching method in time-series databases based on generalized windows //Proc. of ACM SIGMOD, Madison, Wisconsin, 2002: 382-393
[41] Tao YF, Yiu ML, Mamoulis N. Reverse Nearest Neighbor Search in Metric Spaces. IEEE Transactions on Knowledge and Data Engineering, Vol. 18, No. 9, Sep, 2006, pp. 1239-1252
[42] Chen L, Lian X. Dynamic Skyline Queries in Metric Spaces//Proc. of ACM EDBT Conference, Nantes, France, Mar. 2008, pp. 333-343
[43] Yu C, Ooi BC, Tan KL, et al. Indexing the Distance: An Efficient Method to KNN Processing//Proc. of ACM VLDB Conference, Roma, Italy, 2001, pp. 421-430.
[44] Lian X, Chen L. Similarity Search in Arbitrary Subspaces Under Lp-Norm//Proc. of IEEE ICDE Conference, Cancun, Mexico, 2008, pp. 317-326.
[45] Seidl T, Kriegel H P. Optimal Multi-Step k-Nearest Neighbor Search//Proc. of ACM SIGMOD Conference, Seattle, WA, USA, 1998: 154-165
[46] Liu B, Wang Z, Li J. Tight Bounds on the Estimation Distance Using Wavelet//the Seventh Conf. on Web-Age Information Management(WAIM'06). Huang Shan (Yellow Mountain), China, 2006: 460-471
[47] Feng Yucai, Jiang Tao, Zhou Yingbiao, et al. An Efficient Similarity Searching Algorithm Based on Clustering for Time Series. P. Perner (Ed.): ICDM 2008, LNAI 5077, 2008: 360-373
[48] Kim S, Park S, Chu W. An Index-based approach for similarity search supporting time warping in large sequence databases//Proc. of IEEE ICDE Conf., Heidelberg, Germany, 2001: 607-614
[49] Zhou M,. Wong MH. Efficient Online Subsequence Searching in Data Streams under Dynamic Time Warping Distance//Proc. of IEEE ICDE Conference, Cancun, Mexico, 2008, pp. 686-695
[50] Park S, Kim S W. Prefix-querying with an L1 distance metric for time-series subsequence matching under time warping. Journal of Information Science, 2006(32): 387-399
[51] Han W-S, Lee J, Moon Y-S, Jiang H. Ranked Subsequence Matching in Time-Series Databases//Proc. of VLDB Conference, Vienna, Austria, 2007: 423-434
[52] Park S, Chu W, Yoon J, et al. Efficient searches for similar subsequences of different lengths in sequence databases//Proc. of 16th Int’l Conf. of Data Engineering. San Diego, CA, 2000: 23-32
[53] B. Bustos, G. Navarro. Probabilistic proximity searching algorithms based on compact partitions. Journal of Discrete Algorithms, 2(1), 2004: 115-134.
[54] P. Zezula, P. Savino, G. Amato, F. Rabitti. Approximate similarity retrieval with M-trees. The VLDB Journal, 7(4), 1998: 275-293.
[55] V. Castelli, A. Thomasian, C.-S. Li. CSVD: Clustering and singular value decomposition for approximate similarity search in high-dimensional spaces. IEEE Transactions on Knowledge and Data Engineering, 15(3), 2003: 671-685.
[56] A. Gionis, P. Indyk, R. Motwani. Similarity search in high dimensions via hashing//Proc. of VLDB Conf., Edinburgh, Scotland, UK, Morgan Kaufmann, 1999, pp. 518-529.
[57] C. Faloutsos, K.-I. Lin. FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In: Proc. of ACM SIGMOD, San Jose, CA, 1995: 163-174.
[58] .-L. Wang, X. Wang, D. Shasha, K. Zhang. MetricMap: An embedding technique for processing distance-based queries in metric spaces. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 35(5), 2005: 973-987.
[59] P. Ciaccia, M. Patella. PAC nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces//Proc. of IEEE ICDE, San Diego, CA, 2000: 244-255.
[60] E. Chávez, G. Navarro. Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces. Information Processing Letters, 85(1), 2003: 39-46.
[61] . Bennett, . Fayyad, D. Geiger. Density-based indexing for approximate nearest-neighbor queries. In: Proceedings of ACM SIGKDD, San Diego, CA, ACM Press, 1999: 233-243.
[62] E. Chávez, K. Figueroa, G. Navarro. Effective proximity retrieval by ordering permutations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(9), 2008: 1647-1658.
[63] R. Bueno, . Traina, C. Traina Jr. Genetic algorithms for approximate similarity queries. Data and Knowledge Engineering, 62(3), 2007: 459-482.
[64] Papadimitriou S, Li F, Kollios G, and Yu P S. Time Series Compressibility and Privacy//Proc. of VLDB Conference, Vienna, Austria, 2007: 459-470
[65] Yang Y, Papadopoulos S, Papadias D, Kollios G. Authenticated indexing for outsourced spatial databases. VLDB Journal, DOI 2008: 1-18.
[66] Papadopoulos S, Yang Y, Papadias D. CADS: Continuous Authentication on Data Streams//Proc. of VLDB Conference, Vienna, Austria, 2007: 135-146
[67] Mouza C, Litwin W, Rigaux P. SD-Rtree: A Scalable Distributed Rtree//Proc. of IEEE ICDE Conference, Istanbul, Turkey, 2007: 296-305
[68] Soliman M, Ilyas I F, Chang K C-C. Top-k Query Processing in Uncertain Databases//Proc. of IEEE ICDE Conference, Istanbul, Turkey, 2007: 896-905
附中文参考文献:
[1] 朱扬勇, 熊赟. DNA序列数据挖掘技术. 软件学报, 18(11), 2007: 2766-2781
首先对您提到的宝贵而中肯的修改意见表示感谢!具体的修改请您参看下面的修改说明。
修改说明(逐项对应):
(1) 首先，文章对于您提的意见"本文作者的观点较少, 缺乏深刻的总结和高层规律的分析；行文过于冗长，重点不突出"进行了重点修改, 主要的修改如下: 在文章的节增加了研究内容的总结, 在文章的第4节对高效时序相似搜索技术进行了高层规律的总结和分析, 这也是本文的重点(即体现高效性算法应遵循的基本方法和框架, 对于冗余的部分(主要是应用领域的介绍分析)进行了大规模的约简.
其次，对您提到的意见"研究的热点领域的介绍，并不是十分明确；对今后可能的研究方向的介绍，明显不足"修改过程如下: 在整个全文分析过程中总结了研究的热点领域和方向(重点在节、第4节、第6节), 并在最后的第6节(总结和展望)明确了未来的研究方向和热点。
(2) 增加了DTW的铺垫说明在节当中。
(3) 分离了应用领域介绍于第节当中, 并去掉了序列表示、相似度量、子序列匹配方法的介绍.
(4) 增加了不同算法所处理的数据集规模和算法性能的定量介绍和分析于小节, 限于篇幅且不同算法所处理的背景有很大的区别, 我们仅介绍部分典型算法.
(5) 按照您的建议补充了近似相似搜索技术于第5节。
(6) 首先强调了度量对于搜索的意义说明于节当中，即“(1) 可以利用三角不等式修剪搜索空间以加快搜索效率; (2) 时序聚类算法要求距离函数具有对称性; (3) 它也是度量空间搜索策略(例如: 深度优先)能够正确执行的必要条件.”
其次，总结了部分距离函数的性质于表1当中。
(7) 已经将GEMINI框架方法介绍提前在节的最后一段当中。
(8) 对于全文的名词在首次出现时都进行了中英文解释, 但在后面使用过程中为了节省篇幅仅使用缩写形式。
(9) 原来的节图1已经去掉, 对于修改的本次文章的图1和图2都标明了引用的参考文献。
(10) 对相似搜索分类和ε使用混淆已经修正。
(11) 关于原有稿件该点的语法错误已经修正。
其它:
鉴于引用的参看文献较多将占用较大的篇幅, 修改后的参看文献基本上是比较经典的能够说明观点的参看文献, 且对于比较常见的例如: R-tree的参考文献未引用，对于不是文章重点的但不影响说明的参考文献未引用.
Background:
At present, there are more and more time series data owing to its wide application in many domains, such as finance data analysis, Internet traffic analysis, sensor network monitoring, moving object tracking and motion capture. On one hand, it is owing to the increase of user requirement; on the other hand, many data in other domains can be transformed into time series. However, time series data is a typical high dimension and massive data. How to improve the efficiency of similarity search is a key problem on time series. The paper focuses on the efficiency analysis and discussion of time series similarity search.
This subject is supported by the National High Technology Development Program (863 Program) of China under Grant Nos. 2007AA01Z309, 2006AA01Z430. These projects focus on research and development of database management system. The team has made a lot of progress in the area of DBMS and published nearly 20 papers in international and domestic journals or conference proceedings. Although many similarity search algorithms are proposed for time series, however the efficiency of these algorithms still needs to improve and can’t satisfy the practical demand. The content of this paper mainly provides a summary for previous works and helps researchers pay attention to the interesting issues need to address.
作者简历:
第一作者:
冯玉才, 男, 1946年生, 教授, 博士生导师, 主要研究方向为数据库技术.
Feng Yucai, male, born in 1946, professor and . supervisor. His research interests include database technologies.
第二作者(通讯作者):
蒋涛, 男, 1973年生, 在读博士, 研究方向为数据挖掘.
Jiang Tao, male, born in 1973, . His research interests include data mining.
第三作者:
李国徽, 男, 1973年生, 博士, 教授, 博士生导师, 主要研究方向为移动时空数据库技术.
Li Guohui, male, born in 1973, ., professor and . supervisor, His research interests include mobile temporal-space database technologies.
第四作者:
朱虹, 女, 1965年生, 博士, 教授, 博士生导师, 主要研究方向为数据库安全和XML技术.
Zhu Hong, female, born in 1965, ., professor and . supervisor. Her research interests include database security and XML technologies.
(基金项目: 国家863计划项目(编号: 2007AA01Z309, 2006AA01Z430)
通讯作者: 蒋涛, 男, 1973年生, 在读博士, 研究方向为数据挖掘. 联系地址: 华中科技大学计算机学院(湖北武汉, 430074),
1/8
1/4
1/2
1/1
Fig. 2. The four warping paths of different resolutions
图 2 四个不同解析率的弯曲路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
level1
level2
level3
level4
. MSM Approximation
图 1. 多辨析率分段平均近似
