iSAX: disk-aware mining and indexing of massive time series datasets
TL;DR 精炼摘要
本文提出了一种名为iSAX的多分辨率符号表示法,旨在高效索引海量时间序列数据集。通过构建树状索引结构,实现快速精确和高效近似搜索,显著提升了数据集处理能力,实验表明其在数据规模扩展时表现优越,适用于科学、工程及商业领域的海量数据挖掘。
摘要
Current research in indexing and mining time series data has produced many interesting algorithms and representations. However, the algorithms and the size of data considered have generally not been representative of the increasingly massive datasets encountered in science, engineering, and business domains. In this work, we introduce a novel multi-resolution symbolic representation which can be used to index datasets which are several orders of magnitude larger than anything else considered in the literature. To demonstrate the utility of this representation, we constructed a simple tree-based index structure which facilitates fast exact search and orders of magnitude faster, approximate search. For example, with a database of one-hundred million time series, the approximate search can retrieve high quality nearest neighbors in slightly over a second, whereas a sequential scan would take tens of minutes. Our experimental evaluation demonstrates that our representation allows index performance to scale well with increasing dataset sizes. Additionally, we provide analysis concerning parameter sensitivity, approximate search effectiveness, and lower bound comparisons between time series representations in a bit constrained environment. We further show how to exploit the combination of both exact and approximate search as sub-routines in data mining algorithms, allowing for the exact mining of truly massive real world datasets, containing tens of millions of time series.
思维导图
论文精读
中文精读
1. 论文基本信息
1.1. 标题
iSAX: 面向海量时间序列数据集的磁盘感知挖掘与索引 (iSAX: disk-aware mining and indexing of massive time series datasets)
1.2. 作者
Jin Shieh · Eamonn Keogh
1.3. 发表期刊/会议
该论文发表于 Springerlink.com,并在 Published online: 27 February 2009。Eamonn Keogh 是时间序列数据挖掘领域的著名学者,他在该领域有大量开创性的工作,包括 SAX (Symbolic Aggregate approXimation) 表示法。Springerlink 是知名的学术出版平台,该论文发表于其旗下的期刊,表明其经过了同行评审,具有一定的学术质量和影响力。
1.4. 发表年份
2009 年 2 月 27 日(在线发表时间)。
1.5. 摘要
当前时间序列数据索引和挖掘的研究已经产生了许多有趣的算法和表示方法。然而,这些算法和所考虑的数据集规模通常未能代表科学、工程和商业领域日益增长的巨大数据集。在这项工作中,作者引入了一种新颖的多分辨率符号表示方法,称为 iSAX (indexable Symbolic Aggregate approXimation),它能够索引比文献中任何其他方法大几个数量级的数据集。为了验证这种表示法的实用性,作者构建了一个简单的基于树的索引结构,该结构能够实现快速精确搜索和快几个数量级的近似搜索。例如,在一个包含一亿个时间序列的数据库中,近似搜索可以在一秒多一点的时间内检索到高质量的最近邻,而顺序扫描则需要数十分钟。实验评估表明,iSAX 表示法允许索引性能随数据集规模的增加而良好扩展。此外,作者还分析了参数敏感性、近似搜索的有效性,并比较了在比特受限环境下不同时间序列表示法之间的下界(lower bound)。作者进一步展示了如何利用精确搜索和近似搜索的组合作为数据挖掘算法的子程序,从而实现对包含数千万时间序列的真正海量真实世界数据集的精确挖掘。
1.6. 原文链接
/files/papers/69456529ebe97c515a7cd7de/paper.pdf
发布状态:已正式发表。
2. 整体概括
2.1. 研究背景与动机
2.1.1. 核心问题
当前时间序列数据索引和挖掘领域存在的主要问题是,现有算法和表示方法所能处理的数据集规模普遍较小,通常停留在兆字节级别。然而,随着数据捕获和存储能力的飞速发展,现实世界中的时间序列数据集(如科学、工程和商业领域)已经迅速膨胀到太字节甚至更大的规模,现有的方法无法有效处理如此海量的数据。这导致在进行大规模时间序列数据挖掘时,面临严峻的性能挑战,尤其是对于需要磁盘 I/O 的大规模数据集。
2.1.2. 问题的重要性与现有挑战
处理海量时间序列数据的重要性在于,许多关键决策和科学发现都依赖于对这些数据的有效分析。例如,生物信息学中的基因组序列分析、金融市场中的高频交易数据分析、医疗领域的生理信号监测等,都产生着TB级别的时序数据。
现有研究的挑战在于:
- 规模不匹配: 大多数现有算法在设计时并未充分考虑磁盘 I/O 的开销,假设数据可以全部加载到内存中。
- 索引效率低下: 对于大规模数据集,传统的索引结构(如 R-树)在处理高维时间序列数据时效率不高,容易导致大量的磁盘访问和计算开销。
- 缺乏多分辨率表示: 现有表示方法通常是单一分辨率的,难以灵活地在不同粒度下进行数据表示和比较,这限制了索引的扩展性和灵活性。
2.1.3. 论文切入点与创新思路
本文的创新点在于提出了 iSAX (indexable Symbolic Aggregate approXimation) 表示法,作为对经典 SAX (Symbolic Aggregate approXimation) 的扩展。iSAX 引入了多分辨率和比特感知(bit-aware)的特性,使其能够:
- 动态调整粒度: 允许在不同分辨率下表示和比较时间序列,这对于构建可扩展的索引结构至关重要。
- 支持磁盘感知:
iSAX的设计充分考虑了磁盘访问的成本,通过将相似的时间序列映射到磁盘上的物理邻近位置,从而减少 I/O 操作。 - 结合近似与精确搜索: 提出了一种基于
iSAX的树形索引结构,能够提供超快速的近似搜索和高效的精确搜索,并能将两者结合起来解决复杂的数据挖掘问题。
2.2. 核心贡献/主要发现
本文的主要贡献包括:
-
提出
iSAX表示法: 引入了一种新颖的多分辨率、比特感知、可索引的符号化时间序列表示法iSAX。它通过允许动态改变符号化词语的基数(cardinality),解决了SAX在索引大规模数据时可能出现的倾斜问题(skew problem),并支持不同基数iSAX词语之间的比较。 -
设计基于
iSAX的树形索引结构: 构建了一个简单的、基于文件系统的树形索引结构,用于存储和检索海量时间序列数据。该索引结构具有非重叠区域,并能有效控制扇出率(fan-out rate)。 -
实现超快速近似搜索和高效精确搜索:
- 近似搜索: 证明了
iSAX索引能够实现单次磁盘访问的近似搜索,且在处理一亿个时间序列时,仍能在约一秒内返回高质量的最近邻结果。 - 精确搜索: 提出了一种结合近似搜索和下界距离函数(lower bounding distance functions)的精确搜索算法,显著减少了搜索空间和磁盘 I/O。
- 近似搜索: 证明了
-
大规模数据集验证: 首次在文献中考虑并成功索引了高达一亿个时间序列的数据集(比现有工作大几个数量级),并展示了
iSAX在如此大规模数据集上的良好扩展性和性能。 -
数据挖掘算法应用: 展示了如何将
iSAX的近似搜索和精确搜索能力作为子程序,应用于实际数据挖掘任务,例如时间序列集合差异(Time Series Set Difference,TSSD)和批量最近邻搜索(Batch Nearest Neighbor Search),实现了对海量真实世界数据集的精确挖掘。 -
全面实验评估: 进行了全面的实验评估,包括
iSAX与其他时间序列表示法的下界紧密度比较、参数敏感性分析,以及在合成数据(随机游走)和真实世界数据(心电图、昆虫行为、DNA序列)上的性能测试。核心结论或发现:
-
iSAX可以在比特受限的环境下,提供比其他表示法更紧凑的下界。 -
iSAX索引的性能对参数(如词长 和阈值th)的变化不敏感,易于配置。 -
近似搜索在海量数据集上具有极高的速度和令人满意的准确性(例如,在包含一亿个时间序列的数据库中,平均在1.15秒内返回排名靠前的结果)。
-
通过结合近似和精确搜索,可以实现对海量数据集进行以前无法实现的精确数据挖掘任务。
3. 预备知识与相关工作
3.1. 基础概念
理解本文需要以下几个核心概念:
3.1.1. 时间序列 (Time Series)
概念定义: 时间序列是按时间顺序排列的一系列数据点。这些数据点通常在连续的、相等的时间间隔内测量。时间序列数据广泛存在于各个领域,如金融市场价格、传感器读数、心电图、气象记录等。
3.1.2. 欧几里得距离 (Euclidean Distance, ED)
概念定义: 欧几里得距离是连接两个点在欧几里得空间中的直线段的长度。在时间序列分析中,它通常用于衡量两个长度相同的时间序列之间的相似性,即它们对应数据点之间差的平方和的平方根。值越小表示序列越相似。
数学公式: 给定两个时间序列 和 ,它们之间的欧几里得距离 D(T, S) 定义为:
符号解释:
T, S:两个时间序列。- :时间序列 和 在第 个时间点上的值。
- :时间序列的长度。
3.1.3. 动态时间规整 (Dynamic Time Warping, DTW)
概念定义: 动态时间规整 (DTW) 是一种用于测量两个时间序列之间相似性的算法,即使它们在时间轴上存在不对齐或速度差异。它通过“弯曲”时间轴来寻找两个序列之间最佳的对齐路径,从而计算出最小的距离。DTW 在语音识别、手势识别等领域表现优于欧几里得距离。 与 ED 比较: 论文指出,在小型数据集上,DTW 通常比 ED 更准确。然而,随着数据集规模的增大,更有可能找到无需规整(warp)的紧密匹配,此时 DTW 的优势减弱,甚至与 ED 表现相当。
3.1.4. 维度归约 (Dimensionality Reduction)
概念定义: 维度归约是指将高维数据转换成低维表示的过程,同时尽可能保留数据的关键信息。在时间序列分析中,高维时间序列通常难以直接处理和索引,因此需要将其转化为更紧凑、更易处理的低维形式。
3.1.5. 下界 (Lower Bounding)
概念定义: 在时间序列索引中,下界是一个非常重要的概念。它指的是在时间序列的降维表示上计算出的距离,该距离保证小于或等于原始高维数据上的真实距离。如果降维表示的距离大于某个阈值,那么原始数据的真实距离也一定大于该阈值。这种性质允许在索引结构中进行剪枝(pruning),即快速排除那些不可能成为最近邻的候选对象,从而提高搜索效率,同时保证不出现假性漏报(false dismissals)。 假性漏报 (False Dismissals): 指的是在搜索过程中,由于降维表示的距离计算不准确,导致某个真实的最近邻被错误地排除在候选集之外的情况。一个好的索引方法必须保证零假性漏报。
3.1.6. 符号化表示 (Symbolic Representation)
概念定义: 符号化表示是将数值型时间序列转换为由离散符号(如字母或数字)组成的字符串的过程。这种转换有助于应用文本处理、字符串匹配等技术来分析时间序列,也更容易构建索引。
3.2. 前人工作
论文在 2.2 Time series representations 部分回顾了多种时间序列表示方法,并将其分为几大类:
- 模型基础 (Model based): 如马尔可夫模型(Markov Models)、统计模型(Statistical Models)。
- 数据自适应 (Data adaptive): 如分段多项式(Piecewise Polynomials)、插值(Interpolation)、回归(Regression)、自适应分段常数近似(Adaptive Piecewise Constant Approximation,
APCA)、奇异值分解(Singular Value Decomposition,SVD)。 - 符号化 (Symbolic): 如自然语言(Natural Language)、字符串(Strings)、
SAX和iSAX。 - 树 (Trees): 未具体展开,但提及了
TS-tree和R-tree。 - 非数据自适应 (Non-data adaptive): 如小波(Wavelets)、随机映射(Random Mappings)。
- 谱域 (Spectral): 如离散傅里叶变换(Discrete Fourier Transform,
DFT)、离散余弦变换(Discrete Cosine Transform,DCT)、切比雪夫多项式(Chebyshev Polynomials,CHEB)。 - 分段聚合近似 (Piecewise Aggregate Approximation, PAA)
- 可索引分段线性近似 (Indexable Piecewise Linear Approximation, IPLA)
- 数据指示 (Data dictated): 如裁剪数据(Clipped Data)。
3.2.1. SAX (Symbolic Aggregate approXimation)
SAX 是本文 iSAX 的前身,由 Keogh 等人于 2003 年提出。
核心思想:
- PAA (Piecewise Aggregate Approximation): 首先将时间序列通过
PAA降维。PAA将时间序列分割成等长的段,并用每个段的平均值来表示该段,从而减少维度。 数学公式: 给定一个长度为 的时间序列 ,其PAA表示 (长度为 )的第 个元素 计算如下: 符号解释:- :原始时间序列。
- :原始时间序列的长度。
- :
PAA表示后的时间序列。 - :
PAA表示的维度(或段数)。 - :
PAA表示中第 个段的平均值。 - :原始时间序列 中第 个数据点的值。
- 注:如果 不能被 整除,求和范围会有适当调整以处理分数段。
- 分段与符号化: 对
PAA后的序列进行标准化(使其均值为 0,标准差为 1),然后根据预定义的断点(breakpoints)将每个PAA值离散化为特定字母表(cardinality )中的一个符号。这些断点通常选择使得每个符号出现的概率近似相等(例如,对于正态分布数据)。 断点与正态分布: 为了保证符号的近似等概率分布,SAX使用标准正态分布 的断点。这些断点 将 曲线下的面积等分为 份,每份面积为 。 - SAX 词语 (SAX Word): 最终,一个时间序列被表示为一个由 个符号组成的
SAX词语。 数学公式: 符号解释:- :原始时间序列。
- :
PAA段数/SAX词语长度。 - :符号字母表的基数(cardinality)。
- :
SAX词语,由 个符号组成,每个符号来自基数 的字母表。 - :
SAX词语中第 个符号。
- MINDIST (Minimum Distance):
SAX引入了一个下界距离函数MINDIST,用于衡量两个SAX词语之间的距离,并保证该距离小于或等于原始时间序列的欧几里得距离。 数学公式: 给定两个SAX词语 和 ,它们的MINDIST定义为: 符号解释:- :两个
SAX词语。 - :原始时间序列的长度。
- :
SAX词语的长度。 - :通过查找表(如 Table 4)得到的两个
SAX符号之间的距离。 - 这个距离函数依赖于一个预先计算好的符号距离查找表,该表定义了不同符号对之间距离。
- :两个
3.2.2. 其他下界表示法
论文强调,许多表示法具有“下界”特性,这意味着在缩减维度后的表示上计算出的距离,保证小于或等于原始数据上的真实距离,这对于实现零假性漏报的索引至关重要。这些表示法包括:
-
离散傅里叶变换 (DFT)
-
离散余弦变换 (DCT)
-
离散小波变换 (DWT)
-
分段聚合近似 (PAA)
-
自适应分段常数近似 (APCA)
-
切比雪夫多项式 (CHEB)
-
可索引分段线性近似 (IPLA)
论文指出,
SVD和PCA等特征值分析技术虽然能实现最优线性降维,但对于海量数据集而言计算成本过高(需要将所有数据载入内存或耗费数月时间处理磁盘数据),因此不适用于本文所关注的“海量”场景。
3.3. 技术演进
时间序列表示法和索引技术经历了从基于原始数据(如 R-树)到降维表示(如 DFT、DWT、PAA),再到符号化表示(如 SAX)的演进。
- 早期方法主要关注如何直接在高维空间中进行相似性搜索或通过简单的降维技术来加速。
SAX的出现是一个重要的里程碑,它将时间序列转换为符号串,使得可以利用字符串处理的强大工具,并提供了一个简单有效的下界距离。iSAX的贡献在于解决了SAX在面对大规模数据集时,索引结构可能出现的数据倾斜问题,并引入了多分辨率的概念,这使得索引能够动态地适应数据分布,实现更精细的控制和更高的扩展性。它在SAX的基础上,增加了可索引性和多粒度特性,使其能够真正地处理磁盘上的海量数据。
3.4. 差异化分析
iSAX 与其他现有时间序列表示法和索引方法的主要区别和创新点在于:
-
多分辨率与比特感知: 这是
iSAX最核心的创新。与传统的SAX只能使用固定基数不同,iSAX允许动态改变符号的基数,甚至在同一个iSAX词语中每个符号可以有不同的基数。这种多分辨率特性使得索引可以根据数据密度进行自适应分裂,从而避免了数据倾斜问题。 -
可扩展性(Scalability):
iSAX专门设计用于处理“海量”数据集(数千万到数亿时间序列),这是现有方法(如R-tree、TS-tree等)通常无法有效处理的规模。其磁盘感知(disk-aware)的设计理念,通过简单的文件系统操作而非复杂的数据库管理系统(DBMS),实现了卓越的扩展性。 -
零假性漏报的保证: 尽管
iSAX是一个近似表示,但其基于下界距离函数的设计保证了在精确搜索时不会出现假性漏报,能够找到真正的最近邻。 -
近似搜索与精确搜索的结合:
iSAX索引提供了一个独特的组合能力:超快速的近似搜索(单次磁盘访问)和在此基础上优化的高效精确搜索。这种组合可以作为子程序集成到更复杂的数据挖掘算法中,从而实现对海量数据的精确分析。 -
与
SVD/PCA的对比: 尽管SVD/PCA在线性降维方面最优,但iSAX强调其在处理大规模离核(out-of-core)数据集上的实用性,避免了SVD/PCA需要将所有数据加载到内存的限制。 -
与现有符号化方法的对比: 许多符号化方法定义了符号间的距离度量,可能导致相对于原始数据的假性漏报。而
iSAX使用符号词语进行内部组织和索引,但在检索时仍然基于原始数据的欧几里得距离,并利用下界函数保证零假性漏报。
4. 方法论
本文的核心是引入 iSAX 表示法及其构建的索引结构,以实现对海量时间序列数据的磁盘感知挖掘和索引。
4.1. iSAX 表示法
iSAX 表示法是 SAX 的一个扩展,其核心改进在于引入了多分辨率和比特感知的特性,解决了 SAX 在处理大规模数据集时可能出现的索引倾斜问题,并支持不同基数 iSAX 词语之间的比较。
4.1.1. 从 SAX 到 iSAX:多分辨率的引入
经典的 SAX 将每个符号表示为字母或整数。例如, 可以是 {6, 6, 3, 0}。然而,这种表示方式有一个问题:如果只看到 {6, 6, 3, 0},我们无法确定其基数(cardinality),虽然知道它至少是 7。在 SAX 的先前应用中,由于总是使用单一的“硬编码”基数,这并不是问题。但为了实现多分辨率,iSAX 解决了这种模糊性。
iSAX 通过在每个符号上添加一个上标来明确表示其基数。例如:
其中,上标 表示该符号是基于基数 8 的字母表进行编码的。由于单个符号是序数(ordinal),而不是数值,所以这种上标表示不会与数学上的指数运算混淆。
这种明确的基数表示是实现多分辨率的关键,因为它允许在运行时动态地改变符号的粒度。
4.1.2. 比较不同基数的 iSAX 词语
iSAX 的一个新颖思想是能够比较不同基数的 iSAX 词语。这对于索引的动态分裂和合并至关重要。
核心思想: 当比较两个不同基数的 iSAX 词语时,将基数较低的表示“提升”到与基数较高的表示相同的粒度,然后使用 MINDIST 函数进行计算。
提升过程:
-
比特位关系:
iSAX的设计基于比特位。如果一个iSAX符号的基数是 ,另一个是2X,那么基数 的断点集合是基数2X的断点集合的真子集。这意味着通过增加额外的比特位,可以从低基数符号派生出高基数符号。 例如,Table 3 展示了这种关系:
Table 3 It is possible to obtain a reduced (by half) cardinality SAX word simply by ignoring trailing bitsSAX(T , 4, 16) = T16 = {1100, 1101, 0110, 0001} SAX(T , 4, 8) = T8 = {110, 110, 011, 000} SAX(T , 4, 4) = T4 = {11, 11, 01, 00}
从 到 再到 ,只需要忽略每个符号的尾部比特位即可。反过来,从低基数提升到高基数,需要“猜测”缺失的比特位。 -
提升算法: 当需要将一个低基数符号提升到高基数时,算法会检查每个位置,并在高基数中计算出由当前(低)基数已知比特位所包围的比特值。然后,它会选择在
SAX空间中最接近对应的高基数iSAX符号的值。 示例: 假设我们有 和 。 为了比较它们,我们需要将 提升到 。 中的符号 对应二进制0,而 对应二进制1。基数从 2 提升到 8 需要增加两位。对于 (即0),它在高基数 8 的空间中覆盖了000到011。对于 (即1),它覆盖了100到111。 具体的提升过程会根据每个符号在高基数下的“最佳匹配”来确定。例如,论文给出了提升后的结果: 这个提升不是原始时间序列 S 转换为iSAX(S, 4, 8)的结果,因为这是有损压缩。但它提供了一个有效的下界。
4.1.3. 混合基数 iSAX 词语 (Mixed Cardinality iSAX Words)
iSAX 甚至允许同一个词语中包含不同基数的符号,例如 。在比较这样的词语时,只需逐对比较对应符号,将基数较低的符号提升到与基数较高的符号相同的基数即可。这种灵活性是构建自适应索引的基础。
4.2. iSAX 索引
iSAX 索引的核心思想是利用 iSAX 表示法的可变粒度(variable granularity)来解决传统 SAX 索引的数据倾斜问题,从而实现高效的磁盘感知索引。
4.2.1. iSAX 索引的直觉
传统的 SAX 索引可能会导致数据分布严重不均,一些文件(标签)为空,而另一些文件可能包含大部分数据,这两种情况都对索引效率不利。iSAX 通过引入可变粒度来解决这个问题:
- 用户定义阈值 (Threshold,
th): 用户可以设定一个最大文件大小阈值th,表示一个叶节点(文件)中允许存储的最大时间序列数量。 - 动态分裂 (Dynamic Splitting): 当一个文件中的时间序列数量超过
th时,该文件对应的iSAX空间会被“分裂”。分裂的方法是选择iSAX词语中的某个符号,增加其基数(即考虑一个额外的比特位),从而将原文件中的时间序列重新分配到两个新的子文件中。 示例: 原始文件: 如果分裂第一个符号,将其基数从 4 提升到 8(增加一位),那么原文件中的时间序列会根据它们在第一个符号处新增的比特位(0 或 1)被重新映射到两个新的子文件: 子文件 1: (新增比特位为 0) 子文件 2: (新增比特位为 1) 这种分裂方式类似于可扩展哈希(extensible hashing)的思想,确保每个文件中的时间序列数量都在th范围内,从而避免了数据倾斜和过大的文件。
4.2.2. iSAX 索引结构
iSAX 索引是一个分层的树形结构,其节点代表了 SAX 空间的子集。这个结构具有非重叠区域,且扇出率可控。
该图像是 iSAX 索引的示意图,展示了根节点及其内部节点和终端节点间的关系。每个节点包含不同的符号序列,表明多分辨率符号表示法在大型时间序列数据集中的应用。
图 5 展示了一个 `iSAX` 索引的示例。
索引的构建需要指定:
-
基数 (Base cardinality, ): 可选,通常默认为 2,也可以更高。用于计算新的基数值。
-
词长 (Word length, ):
iSAX词语的长度。 -
阈值 (Threshold,
th): 叶节点中允许的最大时间序列数量。索引结构包含三种类型的节点:
4.2.2.1. 终端节点 (Terminal node)
- 功能: 叶节点,包含指向磁盘上实际存储时间序列的索引文件的指针。
- 特性: 文件中的所有时间序列都由该终端节点的代表性
iSAX词语所描述。它代表了SAX空间中包含这组时间序列所需的最粗粒度。 - 分裂条件: 当插入导致终端节点中的时间序列数量超过
th时,该节点(以及其代表的SAX空间)会进行分裂以提供进一步的区分。
4.2.2.2. 内部节点 (Internal node)
- 功能: 表示
SAX空间的一次分裂。当终端节点溢出时,会创建一个内部节点。 - 分裂策略: 内部节点通过沿着一个或多个维度提升基数来分裂
SAX空间,遵循迭代加倍(iterative doubling)的策略(即每次分裂使基数加倍,如从 4 到 8)。 - 哈希表: 内部节点维护一个从
iSAX词语(代表SAX空间的子划分)到子节点的哈希映射,用于区分不同的子区域。 - 分裂机制: 论文为简化,采用沿着单个维度进行二分分裂,并使用轮询(round robin)方式来决定分裂哪个维度。
4.2.2.3. 根节点 (Root node)
- 功能: 代表完整的
SAX空间,功能类似于内部节点。 - 粒度: 根节点在基础基数 下评估时间序列。
- 导向: 遇到的
iSAX词语会对应到某个终端节点或内部节点,并据此引导索引操作。如果插入时遇到未知的iSAX词语,则会创建一个新的终端节点并更新哈希表。
4.2.3. 索引插入 (Index insertion)
插入函数(如 Table 5 所示)描述了构建 iSAX 索引的过程:
Table 5 iSAX index insertion function
| 1 | Function Insert(ts) |
|---|---|
| 2 | iSAX_word = iSAx(ts, this.parameters) |
| 3 | |
| 4 | if Hash.ContainsKey(iSAX_word) |
| 5 | node = Hash.ReturnNode(iSAX_word) |
| 6 | if node is terminal |
| 7 | if SplitNode() == false |
| 8 | node.Insert(ts) |
| 9 | else |
| 10 | newnode = new internal |
| 11 | newnode.Insert(ts) |
| 12 | foreach ts in node |
| 13 | newnode.Insert(ts) |
| 14 | end |
| 15 | Hash.Remove(iSAX_word, node) |
| 16 | Hash.Add(iSAX_word, newnode) |
| 17 | endif elseif node is internal |
| 18 | |
| 19 | node.Insert(ts) |
| 20 | endif |
| 21 | else |
| 22 | newnode = new terminal |
| 23 | newnode.Insert(ts) |
| 24 | Hash.Add(iSAX_word, newnode) |
| 25 | endif |
算法流程:
- 生成 iSAX 词语: 对于要插入的时间序列
ts,首先根据当前节点的参数(如词长、基数)生成其iSAX词语表示 (line 2)。 - 查找节点: 检查当前节点的哈希表是否已包含该
iSAX词语 (line 4)。- 如果存在: 获取对应的节点 (line 5)。
- 如果节点是终端节点:
- 检查插入
ts是否会导致溢出(超过th)。SplitNode()函数会决定是否需要分裂 (line 7)。 - 如果没有溢出: 直接将
ts插入到该终端节点中 (line 8)。 - 如果溢出:
- 创建一个新的内部节点
newnode(line 10)。 - 将
ts插入到newnode(line 11)。 - 将原终端节点中的所有时间序列(它们现在需要被重新分配)也插入到
newnode(lines 12-14)。 - 从哈希表中移除旧的终端节点,并添加新的内部节点 (lines 15-16)。
- 创建一个新的内部节点
- 检查插入
- 如果节点是内部节点: 递归调用该内部节点的插入函数 (line 19),继续向下遍历树。
- 如果节点是终端节点:
- 如果不存在:
- 创建一个新的终端节点
newnode(line 22)。 - 将
ts插入到newnode(line 23)。 - 将新的终端节点及其
iSAX词语添加到哈希表中 (line 24)。
- 创建一个新的终端节点
- 如果存在: 获取对应的节点 (line 5)。
4.2.4. 近似搜索 (Approximate search)
近似搜索旨在快速找到查询的近似最近邻,通常只需要单次磁盘访问。 算法流程:
- 查询
iSAX词语转换: 将查询时间序列转换为iSAX词语。 - 树遍历: 根据查询的
iSAX词语,遍历iSAX索引树。在每个内部节点,根据分裂策略和匹配的iSAX表示向下选择路径。 - 识别终端节点: 由于索引是分层且非重叠的,如果存在一个匹配的终端节点,它会被迅速识别。
- 检索文件: 一旦到达匹配的终端节点,就从磁盘中获取该节点指向的索引文件。这个文件包含至少 1 个且最多
th个时间序列。 - 内存扫描: 对该文件中的时间序列进行内存中的顺序扫描,以找到最佳的近似最近邻。
- 非匹配处理: 在极少数情况下,如果遍历在内部节点失败(没有完全匹配的路径),算法会选择沿着最后一个分裂维度与查询时间序列
iSAX值匹配的节点继续下降。如果没有此类节点,则选择第一个子节点继续下降。
4.2.5. 精确搜索 (Exact search)
精确搜索旨在找到查询的真正最近邻,同时最小化计算和 I/O 开销。它结合了近似搜索和下界距离函数来剪枝搜索空间。
Table 6 Expediting exact search using approximate search and lower bounding distance functions
| 1 | Function [IndexFile] = ExactSearch(ts) |
|---|---|
| 2 | BSF.IndexFile = ApproximateSearch(ts) |
| 3 | BSF.dist = IndexFileDist(ts, BSF.IndexFile) |
| 4 | |
| 5 | PriorityQueue pq |
| 6 | pq.Add(root) |
| 7 | |
| 8 | while !pq.IsEmpty |
| 9 | min = pq.ExtractMin() |
| 10 | if min.dist >= BSF.dist |
| 11 | break |
| 12 | endif |
| 13 | if min is terminal |
| 14 | tmp = IndexFileDist(ts, min.IndexFile) |
| 15 | if BSF.dist > tmp |
| 16 | BSF.dist = tmp |
| 17 | BSF.IndexFile = min.IndexFile |
| 18 | endif elseif min is internal or root |
| 19 | foreach node in min.children |
| 20 | node.dist = MINDIST_PAA_iSAX(ts,node.iSAX) |
| 21 | |
| 22 | pq.Add (node) |
| 23 | end |
| 24 | endif |
| 25 | end |
| 26 | return BSF.IndexFile |
算法流程:
- 获取近似最优解 (BSF): 首先,通过近似搜索(Sect. 4.3 中描述的方法)快速获得一个“目前为止最佳” (Best-So-Far,
BSF) 的答案 (line 2)。计算查询时间序列ts与BSF.IndexFile中时间序列的距离,得到初始的BSF.dist(line 3)。这个初始的BSF值非常重要,它为后续的剪枝提供了基准。 - 初始化优先队列: 创建一个优先队列
pq,并用根节点初始化 (line 5-6)。优先队列用于存储待访问的节点,并根据它们与查询的下界距离进行排序,距离最小的节点优先被处理。 - 迭代搜索: 只要优先队列不为空,就重复以下步骤 (line 8):
- 提取最小距离节点: 从优先队列中取出距离最小的节点
min(line 9)。 - 剪枝条件: 如果
min的下界距离已经大于或等于当前的BSF.dist,则可以提前终止搜索 (lines 10-12)。因为队列中所有剩余节点的下界距离都更大,它们不可能包含比当前BSF更好的最近邻。 - 节点评估:
- 如果
min是终端节点: 从磁盘中获取该节点指向的索引文件 (line 14)。计算查询ts与该索引文件中所有时间序列的真实距离,并更新BSF.dist和BSF.IndexFile(lines 15-17)。 - 如果
min是内部节点或根节点:- 对于
min的每个子节点node(line 19),计算查询ts与该子节点所代表SAX空间的下界距离node.dist(line 20)。这里使用的是MINDIST_PAA_iSAX函数。 - 将
node及其计算出的node.dist插入到优先队列pq中 (line 22)。
- 对于
- 如果
- 提取最小距离节点: 从优先队列中取出距离最小的节点
- 返回结果: 循环结束后,返回最终的
BSF.IndexFile(line 26),其中包含查询的精确最近邻。
下界距离函数 MINDIST_PAA_iSAX:
用于优先队列排序的距离计算是 MINDIST_PAA_iSAX,它衡量查询时间序列的 PAA 表示与节点所占据的 iSAX 空间之间的距离。
数学公式(原文):
符号解释:
- :查询的
PAA表示 与节点iSAX空间 之间的下界距离。 - :查询时间序列 的
PAA表示。 - :节点所代表的
iSAX空间(实际上是该空间对应的iSAX词语,或其所定义的符号区间)。 - :原始时间序列的长度。
- :
PAA表示的维度/iSAX词语的长度。 - :
iSAX符号 的第 个维度所定义的上下断点(即该符号值对应的区间边界)。 - :查询
PAA表示的第 个元素。 - 和 :原文公式的数学符号表达有误,这部分通常表示一个分段函数。其可能意图是计算 到其所属
iSAX符号区间边界的距离。- 如果 落在 和 之间,则距离为 0。
- 如果 ,则距离为 。
- 如果 ,则距离为 。
原文公式中的 这部分从语义上说,应该是 。考虑到 落在 和 之间时距离为0,那么只有当 落在 定义的
SAX区间之外时,才会有非零距离。原文的写法可能是一个排版错误,但严格按照指令,此处需忠实呈现原文公式。
4.2.6. 时间序列楔 (Time series wedges) 扩展
为了进一步加速精确搜索,特别是减少磁盘访问,作者对索引的终端节点进行了扩展。
核心思想: 在终端节点中存储元数据,这些元数据能够为其中包含的时间序列集合提供一个更紧密的下界距离,比 MINDIST_PAA_iSAX 更紧密。
实现方式:
-
存储元数据: 每个终端节点维护其所包含的所有时间序列在每个维度上的最小值(min)和最大值(max)。这些 min/max 值构成了该时间序列集合的“上/下楔”(upper/lower wedge)。
-
LB_Keogh应用: 当精确搜索遇到终端节点且未达到提前终止条件时,使用LB_Keogh函数(一个著名的下界函数)计算查询与这些上/下楔之间的距离。
该图像是图表,展示了一组时间序列数据。左侧显示了一系列映射到 iSAX 字中的时间序列;中间图中标记了上界 U 和下界 L;右侧展示了查询 Q 及其与其他序列的关系,虚线表示一种欧几里得距离的下界。
图 6 展示了时间序列楔的概念。左图显示了一组映射到同一 `iSAX` 词语的时间序列,并标记了它们的上/下楔。右图展示了查询 与楔之间的距离计算,其中阴影线长度的平方和的平方根是 与集合中任何时间序列的欧几里得距离的下界。 -
优势: 由于楔信息作为元数据存储在终端节点中,计算
LB_Keogh无需额外的磁盘访问。如果计算出的LB_Keogh距离大于或等于当前的BSF距离,则可以安全地剪枝该终端节点,避免获取其索引文件,从而显著减少昂贵的磁盘 I/O。
5. 实验设置
5.1. 数据集
为了验证 iSAX 的性能,实验使用了多种数据集,包括合成的随机游走数据和真实的生物医学数据。
5.1.1. 随机游走数据集 (Random Walk Datasets)
- 来源与特点: 随机游走是一种广泛用于模拟股票市场数据的数据类型。其优点是易于生成任意规模的数据集,并且可以通过指定随机种子值来精确重现。这使得实验结果具有良好的可复现性。
- 实验规模:
- 下界紧密度实验:长度为 256 的随机游走时间序列。
- 参数敏感性实验:100 万个长度为 256 的随机游走时间序列。
- 大规模索引实验:1 百万、2 百万、4 百万、8 百万个长度为 256 的随机游走时间序列。以及最终的 1 亿个长度为 256 的随机游走时间序列。
- 样本示例: 随机游走时间序列通常表现出某种随机波动性,没有明显的周期性或特定形状。
5.1.2. Koski ECG 数据集 (Koski ECG Dataset)
- 来源与特点: 这是来自生物医学领域的心电图(ECG)数据集,用于下界紧密度比较。ECG 数据通常具有重复的模式(心跳周期),但可能因个体生理状态而异。
- 样本示例: 图像 7 和 8 提到了 ECG 数据集,但没有提供具体的时间序列样本图。在
5.5 Time series set difference中展示了实际的 ECG 时间序列(图 19),具有明显的周期性心跳波形。
5.1.3. 昆虫行为数据集 (Insect Data Archive)
-
来源与特点: 来自昆虫学家的真实世界数据集,记录了甜菜叶蝉(Circulifer tenellus)在植物上取食时的电穿刺图(Electrical Penetration Graph,
EPG),本质上是电压水平波动的时间序列。昆虫学家通过分析这些波形来理解昆虫行为。 -
规模: 4,232,591 个长度为 150 的子序列。
-
样本示例: 图 16 展示了一个查询的理想化“波形 A”以及近似搜索结果,该波形特征是电压水平急剧上升后逐渐下降的平滑曲线。
该图像是图表,展示了在昆虫数据集上的近似搜索结果。蓝色曲线表示近似搜索结果,绿色曲线为查询数据。结果显示,近似搜索可以有效捕捉到查询的特征,提供快速检索能力。
5.1.4. DNA 序列数据集 (DNA Sequence Data)
-
来源与特点: 用于批量最近邻搜索,将 DNA 序列转换为时间序列。这是生物信息学中的真实世界数据。
-
转换方法:
Table 8详细描述了 DNA 碱基到时间序列数值的转换规则。
Table 8 An algorithm for converting DNA to time seriesT1 = 0; For i = 1 to length(DNAstring) If DNAstringi = A, then Ti+1= T + 2 If DNAstringi = G, then T+1= T + 1 If DNAstringi = C, then Ti+1= T − 1 If DNAstringi = T, then T+1= T −2 End
**规则:** * 对应 +2 * 对应 +1 * 对应 -1 * 对应 -2 每个时间点的值是前一个时间点的值加上当前碱基对应的值。起始值 。 -
实验对象:
- 人类染色体 2: ,总计 11,246,491 个碱基对,生成 5,622,734 个长度为 1024 的时间序列子序列。
- 黑猩猩 DNA: 43 个随机选择的长度为 1024 的子序列。
- 恒河猕猴染色体: 人类染色体 2 的同源染色体。猕猴染色体 19(非相关基线)和猕猴染色体 12、13(潜在同源)。总计 242,951,149 个碱基对,生成 59,444,792 个时间序列子序列。
-
样本示例: 图 20 展示了人类和黑猩猩 DNA 对应部分的转换时间序列图。
该图像是一个比较人类与黑猩猩DNA相应部分的示意图。上方曲线展示了两个物种在DNA序列中的变化,蓝色和红色分别代表人类与黑猩猩的基因差异。下方是710到890区间的放大视图,进一步显示了两者在该范围内的相似性与差异性。
5.1.5. 数据集选择理由
选择这些数据集进行实验是为了:
- 多样性: 覆盖合成数据和多种真实世界数据(心电图、生物行为、基因组),验证
iSAX在不同数据特性下的通用性。 - 可扩展性验证: 尤其是随机游走数据集,能够轻松生成亿级规模,直接验证
iSAX处理海量数据的能力。 - 实际应用: 昆虫行为和 DNA 序列数据集展示了
iSAX在解决实际科学问题中的潜力。
5.2. 评估指标
5.2.1. 下界紧密度 (Tightness of Lower Bounds, TLB)
- 概念定义:
TLB用于衡量降维表示(如iSAX、PAA、DWT等)在计算下界距离时,其结果与原始数据真实距离的接近程度。TLB值越大,表示下界越紧密,索引的剪枝能力越强,搜索效率越高。 - 数学公式:
- 符号解释:
- :在时间序列 和 的降维表示上计算出的下界距离。
- :在原始时间序列 和 上计算出的真实欧几里得距离。
- 意义:
TLB值介于 0 到 1 之间。如果TLB为 0,则下界完全无效,索引技术将不得不检索所有对象。如果TLB为 1,则下界与真实距离完全相等,意味着可以仅检索一个对象就能保证找到真正的最近邻,实现理想的搜索效率。
5.2.2. 近似搜索排名 (Approximate Search Rankings)
- 概念定义: 衡量近似搜索结果的质量。它通过比较近似搜索返回的最近邻在真实最近邻列表中的排名来评估。
- 具体指标:
- 返回结果是真实最近邻的百分比。
- 返回结果在真实最近邻列表的前 10 名中的百分比。
- 返回结果在真实最近邻列表的前 100 名中的百分比。
- 返回结果在真实最近邻列表的前 1000 名之外的百分比。
- 意义: 这些百分比越高(或最后一项越低),表示近似搜索的质量越好。
5.2.3. 索引文件数量 (Number of Index Files Created)
- 概念定义: 衡量索引结构在磁盘上的物理组织情况。它直接反映了索引的分裂效率和存储开销。
- 意义: 过多的索引文件可能增加文件系统的管理开销,过少的文件则可能意味着较大的文件,降低近似搜索效率。理想情况下,索引文件数量应适中,且能够保持每个文件的大小在
th阈值附近。
5.2.4. 查询响应时间 (Query Response Time) / 墙钟时间 (Wall Clock Time)
- 概念定义: 衡量执行一次查询(近似或精确)所需的实际时间,包括 CPU 计算和磁盘 I/O 时间。
- 意义: 这是用户感知到的性能指标,越短的响应时间表示越高效的搜索。
5.2.5. 平均磁盘 I/O (Average Disk I/O)
- 概念定义: 衡量每次查询平均所需的磁盘读写操作次数。
- 意义: 磁盘 I/O 是处理海量离核数据时的主要瓶颈。减少磁盘 I/O 是提高大规模时间序列索引性能的关键目标。
5.2.6. 距离比率 (Distance Ratio)
- 概念定义: 用于定量评估近似搜索结果与真实最近邻之间的相似性。
- 数学公式: 给定查询 ,近似搜索结果 ,和真实最近邻 ,距离比率定义为:
- 符号解释:
- :查询 与真实最近邻 之间的欧几里得距离。
- :查询 与近似搜索结果 之间的欧几里得距离。
- 意义: 距离比率越接近 1,表明近似搜索结果 与真实最近邻 越相似(即 与 的距离越接近 与 的距离)。如果 就是 ,则比率为 1。比率高于 0.69(如文中所示)通常被认为是高质量的近似结果。
5.3. 对比基线
论文将 iSAX 的性能与以下基线进行了比较:
-
其他时间序列表示法:
- DFT (Discrete Fourier Transform)
- DWT (Discrete Wavelet Transform)
- DCT (Discrete Cosine Transform)
- PAA (Piecewise Aggregate Approximation)
- CHEB (Chebyshev Polynomials)
- APCA (Adaptive Piecewise Constant Approximation)
- IPLA (Indexable Piecewise Linear Approximation)
- 这些表示法都具有下界特性,但
iSAX在比特受限环境中显示出更紧密的下界。
-
顺序扫描 (Sequential Scan):
-
概念: 顺序扫描是最基本的搜索方法,它不使用任何索引,而是逐个遍历数据库中的所有时间序列,计算它们与查询的距离,从而找到最近邻。
-
代表性: 顺序扫描代表了没有索引时的“暴力”搜索性能下限。在处理海量数据集时,它的计算成本和磁盘 I/O 成本都非常高。
-
比较: 论文使用顺序扫描作为
iSAX索引搜索速度的基线,尤其是在大规模数据集上,以突出iSAX带来的巨大性能提升。
-
6. 实验结果与分析
6.1. 下界紧密度分析
- 实验目的: 比较
iSAX与其他下界时间序列表示法在不同比特预算下的下界紧密度(TLB)。 - 设置:
- 时间序列长度:[480, 960, 1440, 1920]。
- 每个时间序列可用于降维的字节数:[16, 24, 32, 40]。
- 实数值表示(如
DFT、PAA等)假定每个系数占用 4 字节,因此对应 [4, 6, 8, 10] 个系数。 iSAX固定基数 ,因此对应 [16, 24, 32, 40] 个符号(每个符号 8 比特,即 1 字节)。- 数据集:Koski ECG 数据集。
- 随机采样:1000 次查询。
- 核心结果分析:
-
图 7 展示了在 Koski ECG 数据集上各种时间序列表示法的下界紧密度。
该图像是一个三维柱状图,展示了不同时间序列表示方法(如iSAX、DCT等)在Koski ECG数据集上的下界紧密度。图中显示了不同参数下各表示方法的性能比较,蓝色柱子代表iSAX,覆盖40、32、24、16字节的数据大小。
该图显示,在给定相同字节数预算下,`iSAX` (蓝色条) 在所有时间序列长度和字节数配置下,其 `TLB` 值都显著高于 `DFT`、`DWT`、`DCT`、`PAA`、`CHEB`、`APCA` 和 `IPLA`。例如,在 40 字节预算下,`iSAX` 的 `TLB` 接近 0.95,而其他方法普遍在 0.5 到 0.7 之间。这表明 `iSAX` 能够更有效地利用每个比特位来减少重建误差,从而提供更紧密的下界,带来更强的剪枝能力和更高的索引效率。 -
图 8 再次进行了实验,但将
iSAX词长与实数值表示的维度设为相等(例如,如果实数值表示使用 4 个系数,iSAX也使用词长为 4)。这样虽然iSAX浪费了内存空间(因为它每个符号只用 1 字节,而实数值表示每个系数用 4 字节),但其TLB仍然具有竞争力。
该图像是一个三维柱状图,展示了不同时间序列长度下,iSAX、DCT 和 TLB 的性能比较。图中蓝色柱子代表 iSAX 的性能,灰色柱子代表 DCT 和 TLB。数据表明,iSAX 在处理长时间序列时仍保持较高的性能。
从图 8(仅显示 `DCT` 以放大细节)可以看出,即使在这种“不公平”的比较下(`iSAX` 实际占用的比特数远少于其他方法),`iSAX` 的 `TLB` 仍然与 `DCT` 相当或略优。这进一步强调了 `iSAX` 在比特利用率上的优势。
-
6.2. 参数敏感性分析
- 实验目的: 评估
iSAX索引性能对两个关键参数(阈值th和词长 )的敏感性。 - 设置:
- 数据集:100 万个长度为 256 的随机游走时间序列。
- 基数 固定为 4。
- 查询:1000 次近似查询。
6.2.1. 阈值 (th) 敏感性
- 设置:
th值在 [25, 50, 100, 200, 400, 800, 1600] 之间变化, 固定为 8。 - 核心结果分析:
-
图 9 展示了随着
th值增加,近似搜索排名的变化。
该图像是图表,展示了不同阈值下查询结果的百分比。随着阈值的增加,来自前 10、前 100 和真邻居的查询比例均有所变化,而在前 1000 之外的查询比例相对较低。这说明了在不同的阈值条件下,查询排名的变化趋势。
图中曲线平缓,表明索引性能对 `th` 值不敏感。无论是作为真实最近邻、前 10 还是前 100 的查询返回百分比,在 `th` 变化时都保持相对稳定。 -
图 10 展示了随着
th值增加,创建的索引文件数量的变化。
该图像是一个图表,展示了不同阈值下生成的索引文件数量。随着阈值的增加,索引文件数从近90000逐渐下降至30000,表明更高的阈值能有效减少索引文件数量。
随着 `th` 的增加,索引文件数量显著减少,但减少的趋势逐渐变缓。在 附近,文件数量曲线趋于平缓,表明此时文件数量已经接近底部。
-
- 结论:
th值选择的关键在于平衡检索的条目数(th本身)和创建的索引文件数量。作者选择 是一个合适的选择,因为它既能保证被检查的条目数较少,又能使索引文件数量接近最小值。
6.2.2. 词长 (w) 敏感性
- 设置: 值在 [3, 12] 之间变化,
th固定为 100, 固定为 4。 - 核心结果分析:
-
图 11 展示了随着 值增加,近似搜索排名的变化。
该图像是图表,展示了随着字长度增加,查询结果中各种近邻的百分比。横轴为字长度,纵轴为查询百分比,曲线分别表示在前1000之外的查询、真实最近邻、前10和前100的近邻比率。
图中显示,在 值为 [6, 9] 的范围内,近似搜索排名保持在较高水平。随着 进一步增加,性能略有下降,这可能是因为段越小对噪声越敏感。 -
图 12 展示了随着 值增加,创建的索引文件数量的变化。
该图像是一个折线图,展示了不同词长下创建的索引文件数量。横轴表示词长,范围从3到12,纵轴表示索引文件数量,显示了一种随着词长增加而逐渐增长的趋势。
随着 的增加,索引文件数量也随之增加,因为更大的词长意味着更多可能的 `iSAX` 词语(用作文件名)。
-
- 结论: 索引性能对 的精确选择也不是高度依赖。作者选择 也是合适的,它位于性能较好的范围内,且索引文件数量相对较少。
6.3. 索引海量数据集
- 实验目的: 验证
iSAX在处理数百万乃至一亿时间序列的超大规模数据集时的性能。 - 设置:
- 数据集:长度为 256 的随机游走时间序列,规模从 100 万扩展到 800 万。
- 参数:。
- 索引文件数量:1M -> 39,255;2M -> 57,365;4M -> 92,209;8M -> 162,340。
- 查询:1000 次近似查询。
6.3.1. 近似搜索在大规模数据集上的表现
- 核心结果分析:
-
图 13 展示了在不断增大的数据库上,近似搜索结果在真实最近邻列表中的排名百分比。
该图像是图表,展示了随机游走数据库大小与各种排名的截止百分比之间的关系。随着数据库大小的增加,能够从前100名、前10名和真实最近邻中检索到的比例变化明显,有助于理解近似搜索的效果。
结果非常出色: * 在 100 万时间序列中,91.5% 的近似搜索结果在真实最近邻列表的前 100 名内。 * 在 100 万时间序列中,超过一半的近似搜索返回结果在真实最近邻列表的前 10 名内。 * 在 100 万时间序列中,14% 的近似搜索结果是真正的最近邻。 * 当数据集规模扩展到 800 万时间序列时,这些百分比仅略微下降,显示出 `iSAX` 的强大可扩展性。 -
速度: 这些近似搜索仅需单次磁盘访问和最多 100 次欧几里得距离计算,平均查询时间不到一秒。
-
6.3.2. 精确搜索在大规模数据集上的表现
- 设置: 对 10% 的查询进行精确搜索。
- 核心结果分析:
-
图 14 展示了精确搜索的估计墙钟时间。
该图像是一个柱状图,展示了针对不同规模的时间序列(百万)进行精确搜索的估计墙钟时间。图中显示,iSAX索引所需时间显著低于顺序扫描,尤其在数据量增大时,差异更加明显。
`iSAX` 索引的精确搜索时间远低于顺序扫描。例如,在 800 万时间序列上,`iSAX` 约 1000 秒,而顺序扫描需要约 10000 秒。 -
图 15 展示了精确搜索的平均磁盘 I/O。
该图像是一个柱状图,展示了在进行确切搜索时,iSAX索引与顺序扫描的不同行数据集(百万时间序列)下的平均磁盘I/O。随着数据集规模的增加,顺序扫描的磁盘I/O显著高于iSAX索引。
`iSAX` 索引的磁盘 I/O 显著低于顺序扫描。在 800 万时间序列上,`iSAX` 约 100 次 I/O,而顺序扫描则达 1000 次以上。这表明 `iSAX` 索引有效地减少了磁盘访问。
-
6.3.3. 索引一亿时间序列
- 设置:
- 数据集:1 亿个长度为 256 的随机游走时间序列。
- 参数: (为了适应更大规模,调整了参数)。
- 结果:创建了 151,902 个文件,占用半个 TB 的磁盘空间。平均每个索引文件包含约 658 个时间序列。
- 核心结果分析:
- 近似搜索: 10 次近似查询的平均响应时间为 1.15 秒。其中 3 次查询找到了真正的最近邻,平均排名为 8,最差的查询也找到了第 25 近的邻居。
- 精确搜索: 平均每次精确搜索需要 90 分钟完成,而顺序扫描则需要 1800 分钟。
- 结论: 面对一亿个对象,
iSAX的近似搜索能够以极高的速度和惊人的精度(检索 0.0013895% 的数据,找到排名在前 0.0001% 的对象)返回高质量结果。这证明了iSAX在处理史无前例规模数据集上的卓越能力。
6.4. 近似搜索评估
- 实验目的: 进一步量化近似搜索结果的质量和有效性。
- 数据集: 昆虫行为数据集(4,232,591 个长度为 150 的子序列)。
- 参数: 。
- 核心结果分析:
-
图 16 展示了在昆虫数据集上的近似搜索结果。
该图像是图表,展示了在昆虫数据集上的近似搜索结果。蓝色曲线表示近似搜索结果,绿色曲线为查询数据。结果显示,近似搜索可以有效捕捉到查询的特征,提供快速检索能力。
昆虫学家提供的查询模式“波形 A”得到了很好的匹配。尽管数据库包含四百多万时间序列,结果在不到一秒内返回,极大地加速了科学家的交互和假设测试。 -
距离比率评估: 在 9,999,745 个随机游走时间序列子序列上,使用 进行索引,并对 100 个随机查询计算距离比率。
-
图 17 展示了 100 个查询的排序距离比率。
该图像是图表,展示了100个随机游走查询的归一化距离比率 随查询次数的变化趋势。可以看出,随着查询数量的增加,距离比率逐渐上升,趋近于1。
所有比率都高于 0.69,表明近似结果与实际最近邻之间的偏差不显著。 -
图 18 展示了距离比率中位数(0.907)对应的查询、近似结果和真实最近邻的图示。
该图像是图表,展示了随机游走查询、近似结果和真实最近邻的比较。图中蓝色虚线表示查询,绿色实线表示近似结果,红色实线表示真实最近邻。三者对应的距离比率的下中位数。
从视觉上看,近似结果与真实最近邻几乎无法区分,进一步验证了近似搜索的高质量。
-
-
6.5. 时间序列集合差异 (Time Series Set Difference, TSSD)
-
实验目的: 展示
iSAX如何结合近似搜索和精确搜索来解决数据挖掘问题。 -
定义 TSSD: 给定两个时间序列集合 A 和 B,TSSD 是 A 中与其在 B 中最近邻的距离最大的时间序列。
-
数据集: 心电图(ECG)数据集。
- B 集合(参考集):7.2 小时的多导睡眠图数据。
- A 集合(“新颖”集):接下来的 8 分 39 秒数据(患者醒来期间)。
-
索引设置: 索引 B 集合,
iSAX词长为 9,最大阈值 。结果:1,000,000 个时间序列子序列,分布在 31,196 个文件,占用 4.91 GB 磁盘空间。 -
算法: 论文提出了一个利用
iSAX近似搜索和修改后的精确搜索的算法(Table 7)。
Table 7 An outline of an algorithm to find the TSSD1 Function [IndexFile] = TimeSeriesSetDifference(A,B) 2 // sort priority queue by entry dist 3 PriorityQueue pq 4 foreach ts in A 5 IndexFile = B.ApproximateSearch(ts) 6 entry.dist = IndexFileDist(ts,IndexFile) 7 entry.ts = ts; 8 pq.Add(entry) 9 end 10 11 while !pq.IsEmpty 12 entry = pq.ExtractMax() 13 nextDist= pq.FindMax().dist 14 15 // exact search is suspended if the best-so-far 16 // becomes greater than nextDist 17 IndexFile = B.ExactSearch(entry,nextDist) 18 19 // IndexFile returns null when search is suspended 20 if IndexFile == null 21 pq.Add(entry) 22 else 23 return Indexfile 24 endif 25 end
-
核心结果分析:
-
图 19 展示了 TSSD 发现的不一致心跳。
该图像是图表,展示了在一个清醒周期中记录的心电图(ECG)与之前 7.2 小时的 ECG 数据之间的差异。图中标注了特定时间点,包含 90和109的间隔,表明心跳活动的变化。
结果显示,两个完整心跳的 P 波形态相同,但第二个心跳的持续时间增加了 21.1%。心脏病专家将其解释为窦性心律失常,与患者呼吸模式变化相关。 -
性能对比:
- 朴素算法 (Naive Algorithm): 对 A 中每个对象进行 20,000 次精确搜索。需要 325,604,200 次欧几里得距离计算和 5,676,400 次磁盘访问,估计需要 1.04 天。
iSAX算法: 仅需 43,779 次磁盘访问(20,000 次在第一阶段近似搜索,其余在细化搜索阶段)和 2,365,553 次欧几里得距离计算。总共耗时 34 分钟。
-
效率原因:
iSAX算法通过快速近似搜索有效地剪枝了大部分候选,在 A 集合的 20,000 个对象中,只有两个对象(包括最终答案)进行了完整的最近邻计算。17,772 个对象仅通过一次磁盘访问就被淘汰,2,226 个对象需要多次磁盘访问但未完成整个搜索。
-
6.6. 批量最近邻搜索 (Batch Nearest Neighbor Search)
-
实验目的: 解决在集合 A 中找到与集合 B 中任何对象距离最小的对象的问题。
-
数据集: DNA 序列数据(人类染色体 2 和黑猩猩 DNA)。
-
算法: 论文提出了一个利用
iSAX近似搜索和精确搜索的算法(Table 9)。
Table 9 Batch nearest neighbor algorithm1 Function [IndexFile] = BatchNearestNeighbor(A, B) 2 3 PriorityQueue pq 4 min.dist = inf 5 foreach ts in A 6 IndexFile = B.ApproximateSearch(ts) 7 dist = IndexFileDist(ts,IndexFile) 8 if min.dist > dist 9 min.dist = dist 10 endif 11 min.ts = ts 12 13 entry.dist = dist 14 entry.ts = ts; 15 pq.Add(entry) 16 end 17 pq.Remove(min.ts) 18 19 IndexFile = B.ExactSearch(min.ts) 20 min.dist = IndexFileDist(IndexFile) 21 22 min.IndexFile = IndexFile; 23 while !pq.IsEmpty 24 IndexFile = B.ExactSearch(pq.ExtractMin(), min.dist) 25 if IndexFile != null 26 min.dist = IndexFileDist(IndexFile) 27 min.IndexFile = IndexFile; 28 endif 29 30 end 31 return min.IndexFile;
-
核心结果分析:
-
图 20 展示了人类和黑猩猩 DNA 相应部分的匹配。
该图像是一个比较人类与黑猩猩DNA相应部分的示意图。上方曲线展示了两个物种在DNA序列中的变化,蓝色和红色分别代表人类与黑猩猩的基因差异。下方是710到890区间的放大视图,进一步显示了两者在该范围内的相似性与差异性。
该图直观展示了尽管 DNA 字符串不完全相同,但在时间序列表示上高度相似,证明了匹配的准确性。 -
性能对比:
iSAX算法: 第一阶段(近似搜索)在 12.8 秒内返回了一个近似答案(后被证实是精确解)。完整算法在 21.8 分钟内终止。- 朴素顺序扫描: 需要 13.54 小时。
-
效率原因: 算法利用了近似搜索快速确定一个初始的“目前为止最佳”结果,然后利用这个距离作为精确搜索的剪枝阈值,极大地加速了后续精确搜索的效率。
-
6.7. 绘制恒河猕猴染色体图谱 (Mapping the Rhesus Monkey Chromosomes)
-
实验目的: 利用
iSAX超快速近似搜索能力,进行大规模真实世界数据集的同源区域发现和比对。 -
背景: 人类和猕猴在 2500 万年前分化,寻找同源染色体比黑猩猩更具挑战性。人类染色体 2 被怀疑是两个祖先灵长类染色体融合的结果。
-
设置:
- 人类染色体 2(目标):下采样 4 倍后,59,444,792 个长度为 1024 的时间序列子序列被索引。
- 猕猴染色体 19(非相关基线):所有子序列(及其镜像)作为查询。
- 猕猴染色体 12 和 13(潜在同源):所有子序列作为查询。
-
核心结果分析:
-
图 21 展示了猕猴染色体 19(非相关)与人类染色体 2 之间近似最近邻的欧几里得距离分布。
该图像是图表,展示了来自恒河猕猴19号染色体的子序列到其人类2号染色体的近似最近邻的欧几里得距离分布。图中显示该分布已经归一化,使曲线下的面积为1。
该分布呈现为近似正态,平均距离约 1,774,标准差 301。这建立了一个“不相关”染色体对的距离基线。 -
图 22 比较了猕猴染色体 19 和 12 与人类染色体 2 的距离分布。
该图像是图表,展示了Rhesus Monkey染色体12和19的子序列到其在Human染色体2的近似最近邻的欧几里得距离分布。图中曲线表明随着距离的增加,分布的变化趋势。
猕猴染色体 12 的距离分布明显向左偏移,表明其与人类染色体 2 的相似性显著高于非相关染色体 19。猕猴染色体 13 也表现出类似的不同分布。 -
图 23 展示了人类染色体 2 与猕猴染色体 12 和 13 的点图比对。
该图像是一个点图,展示了人类染色体2与猕猴染色体12和13的比对情况。每个点代表猕猴序列(行)与人类序列(列)之间在1,250个碱基对内的相似位置。
图中使用 1,250 作为距离截止值(因为两条分布曲线在此处开始分歧)。点图清晰显示,人类染色体 2 大部分可以由猕猴染色体 12 和 13 的融合来解释。这与已知的生物学事实(人类染色体 2 是两个祖先灵长类染色体融合的结果)相符。 -
性能: 总共执行了 119,400 次近似查询,耗时略超过 4 小时。而朴素的序列扫描方法(119,400 * 59,444,792 次距离计算)将需要一年多的时间。
-
-
结论:
iSAX的超快速近似搜索使得在大规模基因组比对这种计算密集型任务中,能够以可接受的时间发现生物学上的重要模式。
7. 总结与思考
7.1. 结论总结
本文成功引入了一种新颖的多分辨率符号表示法 iSAX,它极大地提升了时间序列数据索引和挖掘的规模。iSAX 解决了传统 SAX 在大规模数据集上面临的数据倾斜问题,并通过其比特感知和可变粒度特性,实现了高效的磁盘感知索引。作者构建了一个基于 iSAX 的树形索引结构,该结构能够提供超快速的近似搜索(在亿级数据集上数秒内完成)和在此基础上显著加速的精确搜索。实验结果表明,iSAX 在比特受限环境中提供了更紧密的下界,并且其性能对关键参数不敏感。通过将近似搜索和精确搜索结合作为子程序,iSAX 能够有效地应用于复杂的数据挖掘任务,如时间序列集合差异和批量最近邻搜索,从而实现了对包含数千万时间序列的真正海量真实世界数据集的精确挖掘,其性能比朴素方法快了几个数量级。
7.2. 局限性与未来工作
7.2.1. 论文作者指出的局限性
MINDIST_PAA_iSAX公式: 虽然论文中给出了MINDIST_PAA_iSAX的公式,但其形式在数学符号上并不标准,可能需要更清晰的定义来避免混淆。DTW支持: 尽管论文通过实验表明在大型数据集上DTW与ED的性能差异减小,并声称iSAX稍作修改即可支持DTW,但并未在本文中详细展示或验证其在DTW距离下的性能。- 简单树结构: 论文强调其简单树结构的优势(易于采用、复制和扩展),但这也意味着它可能没有利用更复杂的
DBMS或文件管理器的优化。 - 具体数据挖掘算法的扩展: 论文仅展示了
TSSD和批量最近邻搜索两个示例,但并未涵盖所有潜在的时间序列数据挖掘算法。
7.2.2. 提出的未来研究方向
- 将近似搜索和精确搜索的组合应用于其他时间序列数据挖掘算法,例如:
- 基序发现 (motif discovery)
- 密度估计 (density estimation)
- 异常发现 (anomaly discovery)
- 连接 (joins)
- 聚类 (clustering) 特别是在数据常驻磁盘的场景下,这些算法的优化潜力巨大。
- 进一步探索
iSAX在DTW距离度量下的性能和适用性。
7.3. 个人启发与批判
7.3.1. 个人启发
- 大道至简,解决痛点:
iSAX的设计并未引入过于复杂的数学模型,而是在SAX的基础上,通过多分辨率和比特感知的巧妙改进,直接且有效地解决了海量时间序列数据索引的实际痛点——磁盘 I/O 和数据倾斜。这种“小而美”的创新思路非常值得学习。 - 近似与精确的协同: 论文强调了近似搜索与精确搜索的结合是一种强大的模式。近似搜索提供速度和初步结果,精确搜索在此基础上进行精炼,最终保证准确性。这对于处理大规模数据、在时间和准确性之间权衡的许多机器学习和数据挖掘任务都具有普遍的指导意义。
- 磁盘感知的重要性: 在大数据时代,许多算法设计者往往倾向于假设数据能够完全加载到内存中。本文提醒我们,对于真正“海量”的数据集,磁盘 I/O 才是核心瓶颈。设计“磁盘感知”的算法和数据结构是提升性能的关键。
- 可复现性和开放科学: 作者提供了所有数据集、原始数据和补充实验的网页链接,这种开放和透明的实验哲学对于学术研究的健康发展至关重要。
7.3.2. 批判与潜在改进
-
MINDIST_PAA_iSAX公式的清晰度: 正如前面提到的,论文中给出的MINDIST_PAA_iSAX公式在数学符号上存在一些非标准之处,可能导致初学者困惑。在后续工作中,应提供更严谨、更标准的公式表达,并明确其分段函数的逻辑。 -
DTW 的集成细节: 论文提到
iSAX可以“通过微不足道的修改”支持DTW,但并未详细展开。考虑到DTW在许多应用中的重要性,一个详细的iSAX-DTW方案(包括下界函数和索引策略)及其性能评估会更有价值。 -
复杂数据模式的适应性: 随机游走是一种相对简单的时间序列模式。尽管论文也使用了 ECG、昆虫行为和 DNA 数据,但
iSAX在处理具有复杂季节性、趋势、或多模式结构的时间序列(例如,多种形状模式在不同时间尺度上叠加)时,其多分辨率分裂策略是否总是最优?例如,目前的轮询分裂维度可能不是最优的,是否可以根据数据分布动态选择分裂维度和分裂点? -
动态调整基数的成本:
iSAX的核心优势在于其可变粒度。然而,在索引分裂过程中,提升基数意味着需要重新评估和存储更精细的符号。这种动态调整的计算和存储开销在极端情况下(例如,数据分布非常不均匀,需要频繁分裂和提升基数)是否会成为瓶颈,以及如何优化,可以进一步探讨。 -
与其他先进索引结构的对比: 论文主要与旧的
R-tree和通用TS-tree进行了定性比较,但在大规模数据集上,如果能与当时更先进的或专门为时间序列设计的其他索引结构(如TS-tree、VA-file等的离核版本,如果存在)进行更直接的定量性能对比,将更有说服力。 -
内存管理与缓存效应: 论文虽然是磁盘感知,但其性能也必然受到操作系统文件缓存、磁盘硬件特性等因素的影响。对这些因素的更深入分析,以及
iSAX如何与现代存储技术(如 SSD、NVMe)结合,可以进一步优化性能。总而言之,
iSAX为海量时间序列数据的索引和挖掘提供了一个实用且高效的解决方案,其核心思想对未来处理大数据的方法设计具有重要的借鉴意义。
相似论文推荐
基于向量语义检索推荐的相关论文。