以下是论文iSAX: disk-aware mining and indexing of massive time series datasets的笔记。

已有方法及改进

[1] 已有方法通过首先对原数据进行符号化来促进时间序列搜索，但是都会引入新的衍生符号定义的距离测量

[2] multi-resolution symbolic representation - indexable Symbolic Aggregate approXimation (iSAX)
用于大数量级数据集的索引，使用符号词对数据进行内部组织和索引，但根据原始数据上的ED检索对象

[3] 证明: 构建基于树的索引结构 - 有助于快速精确搜索和更快速的近似搜索
利用两种搜索类型的组合作为数据挖掘算法中的子例程，允许精确挖掘真正庞大的数据集，具有数千万个时间序列，占用多达一兆字节的磁盘空间

[4] 分析了位约束环境(bit constrained environment)下时间序列表示的参数敏感性(parameter sensitivity)、近似搜索效率(approximate search effectiveness)和下界比较(lower bound comparisons)

iSAX的优点

[1] 可以动态更改用于评估表示的位数(the number of bits used for evaluation of representation)，与desired resolution对应
这种特性允许叶节点上索引零重叠的时间序列(index time series with zero overlap at leaf nodes)，同TS树，不同于R树

[2] 不需要使用专门的数据库或文件管理器 - 让索引技术可以轻松采用、复制和扩展
使用标准Windows XP NTFS文件系统磁盘访问
对比：使用复杂的DBMS可能可以达到更快的时间

[3] 具有符号性 - 允许使用对实际值数据没有很好定义的数据结构和算法
包括后缀树、散列、Markov模型

基础: SAX

[1] SAX + 允许扩展散列 => multi-resolution representation

PAA是一种理想的中间表示，因为可以快速降维，提供下边界的距离度量。例子中PAA表示将时间序列的维数从16减少到4。

如果n不能被w整除，求和可以修改为采用分数值。

[2] SAX将PAA作为输入，并将其离散化为一个小的符号字母表。
离散化：通过想象一系列与X轴平行的断点，用离散标签标记断点之间的每个区域。任何落在区域的PAA值都可以映射到适当的离散值。

[3] 如果我们使用有序的数字列表Breakpoints = β1 , … , βa−1，我们可以确保SAX词中几乎等概率的符号，使标准正态分布 N(0,1) 曲线下从 βi 到 βi+1 的面积 = 1/a。β0 和 βa 分别被定义为 −∞ 和 ∞。
基数a = 2 ~ 8时的断点：

[4] SAX(T, w, a) = Ta = {t1, t2, …, tw−1, tw}

时间序列T和S的ED推导：(dist(ti, si)通过查表获得，例如 dist(00, 01) = 0，dist(00, 10) = 0.67)

[5] 通过更多的SAX符号或者更高的基数a可以获得更紧的下界。

iSAX

[1] 使用上标表示基数，从而防止模棱两可：

[2] 比较不同基数的iSAX，需要将较低的基数表示提升为较大的基数表示
思想：基数为X的iSAX的断点是基数为2X的iSAX断点的子集（可以参见表2）
S2 = {0, 0, 1, 1} => S8 = {011, 011, 100, 100}

转化为有损压缩，无法撤回

iSAX的索引

未完待续