iSAX 2.0: Indexing and Mining One Billion Time Series

在不同领域的几个应用程序日益迫切地需要开发能够索引和挖掘非常大的时间序列集合的技术。这类应用的例子来自天文学、生物学、网络和其他领域。这些应用程序涉及数亿到数十亿的时间序列并不罕见。然而，到目前为止，文献中提出的所有相关技术都没有考虑任何远远大于100万时间序列的数据收集。在本文中，我们描述了iSAX 2.0，一个为索引和挖掘真正的海量时间序列集合而设计的数据结构。我们证明了挖掘如此庞大的数据集的主要瓶颈是建立索引所需的时间，因此我们引入了一种新的批量加载机制，这是第一个专门针对时间序列索引定制的机制 。我们展示了我们的方法如何允许对数据集进行挖掘，否则这些数据集是完全站不住脚的，包括首次发表的索引10亿个时间序列的实验，以及从昆虫学、DNA和网络规模的图像收集等不同领域挖掘海量数据的实验。

背景：现在迫切需要减少检索时间，尤其是这些数据驻留在磁盘上。一旦一种降维表示被确定
已经确定了，比如（DFT、DWT、SAX等)，**提高检索时间的唯一方法是优化基于树的索引的拆分算法，**糟糕的拆分策略会导致过多且无用的细分，从而创建不必要的深度子树，并导致更长的遍历。

方案：

正如我们将展示的最大的(到目前为止)时间序列索引实验集，用一个新的散装加载方案，我们可以减少72%的索引构建时间 。此外，我们新的分拆策略使索引的规模减少了27%。磁盘页面访问的数量减少了50%，而其中超过99.5%的访问是连续的。

PRELIMINARIES

1)The SAX Representation

SAX表示将PAA表示作为输入，并将其离散化为一个具有基数a的小符号字母表。离散化是通过创建一系列与x轴并行的断点并用离散标签标记每个区域来实现的。任何属于该区域的PAA段都可以映射到适当的标签。

SAX表示支持任意断点，然而，它已经表明，一个有效的选择是一个排序的数字列表Βreakpoints = β1，， βa-1，这样的面积下N(0,1)高斯曲线从βi到βi+1 = 1/a产生近似等概率的符号

2）The iSAX Representation

iSAX表示的关键属性之一是能够比较两个不同基数的iSAX单词。 我们可以找到T和S之间的下界，尽管iSAX中表示它们的词具有不同的基数。诀窍是将较低的基数表示提升为较大的基数表示，然后再将其交给MINDIST函数

iSAX表示的使用导致了分层但不平衡的索引结构的创建，该索引结构包含不重叠的区域，并具有受控的扇出率。

THE ISAX 2.0 INDEX
iSAX是一种不平衡的树结构。此外，也没有专门的机制来促进将大量时间序列集合纳入索引。请注意，上面对iSAX的批评主要是指索引的构造，而不是索引的效用。在创建索引期间，主要的瓶颈是硬盘驱动器性能和相关的I/O成本。随着索引数据量的增加，这个瓶颈成为一个硬约束，限制了索引的整体可伸缩性

为了克服上述问题，我们提出了以下两种互补的技术来提高iSAX的可扩展性。

1.一种用于时间序列批量加载的新算法，它大大减少了磁盘页面总访问次数，同时也最小化了随机磁盘页面访问次数

2. 对索引的内部节点采用新的拆分策略，导致索引结构更加紧凑，从而进一步降低了I/O成本。

A. Bulk Loading

我们现在描述了一种批量加载的算法 ，它可以有效地减少磁盘I/O操作的数量 。该算法的主要思想是，我们不是一次开发整个索引，而是专注于一次构建索引的不同子树 。这是有益的，因为通过增长索引的特定子树，我们可以有效地减少节点分割操作的数量，并简化所有磁盘访问。使用本文提出的算法，我们可以实现以下目标。

1）最小化所需的磁盘I/O，因为我们避免为了拆分叶子节点而重新访问它们(这将意味着从磁盘读取它们的内容，然后写回新叶子节点的内容的额外磁盘访问)。我们确保每次为了写入叶节点的内容访问磁盘，都会一次性地将其所有内容写入磁盘。

2）最大化连续磁盘页面访问的次数，这样叶子节点的内容不能放入单个磁盘页面。

Phase 1：

算法读取时间序列并将其插入到FBL中相应的缓冲区中(图3中的4-16行)。这个阶段一直持续到主存几乎满。(在阶段2中，我们需要少量的额外内存来分配新节点。然而，这只在第12- 16行循环的第一次迭代开始时需要，因为每次迭代都会释放内存)

Phase 2: 该算法将每个FBL缓冲区中包含的时间序列移动到适当的LBL缓冲区 。在此阶段，算法对FBL中的缓冲区进行顺序处理 。对于每个FBL缓冲区，算法读取时间序列并创建所有必要的内部(第25-33行)和叶(第36-39行)iSAX 2.0节点 ，以索引这些时间序列。它基本上在FBL缓冲区对应的节点上创建了整个子树(或任何缺失的节点，如果子树已经被构建)。

B. Node Splitting Policy

很明显，索引结构的大小会影响索引的创建时间:更紧凑的结构意味着更少的磁盘访问次数。

与其他索引结构不同，iSAX索引是不平衡的 。这种设计决策导致了一个简单的节点拆分策略，该策略不考虑待拆分节点中包含的数据。在某些情况下，分裂一个节点仍然可能导致所有的时间序列都结束于两个新节点中的一个，因此，需要进行额外的分裂。这种设计决策可能会导致叶节点利用率较差，导致索引结构更大、更深

我们提出了一种节点拆分策略，该策略基于存储在每个节点中的数据分布的知识做出明智的决策 。这个算法背后的直觉是这样的。我们的算法是检查每个片段的最高基数符号在相关时间序列中的分布。然后，在符号分布表明时间序列有较大概率被分割成两个新节点的线段上对节点进行分割，从而避免了无用的节点分割问题。

考虑图4中描述的示例 ，其中我们假设iSAX字的长度(即段的数量)为4，我们想要分割一个基数为2(对于所有段)的节点。对于每一段，我们计算了相应符号的μ±3σ范围。我们观察到段1的这个范围完全低于最低断点4的基数(即，分裂后的两个新节点的基数)。只有段2和段3的范围跨越了基数4的断点。在这两者之间，算法将选择在段3上分割，因为它的μ值比段2更接近断点。这表明，极有可能要拆分的节点中的一些时间序列会在新节点中结束，表示断点上方的区域，而其余的将移动到第二个新节点，从而实现平衡的拆分

• 对每一个分段的PAA求均值和方差，看是否cross下一位的split line，不过分割线那么大概率分割没意义，是不均衡的。
• 算法应尽量选择分割过线的段，如果都跨线了，就比较谁的均值离线更近一些。

EXPERIMENTAL EVALUATION

1. 测量下界的紧密度，它被定义为下界距离除以真实距离。

A. Scalability of iSAX 2.0

我们生成了1亿时间序列的数据集，其中每个时间序列的长度为256，

Bulk Loading Evaluation

我们索引了一组从1亿到10亿时间序列的数据集，由长度为256的随机游走序列组成

iSAX 2.0必须执行的磁盘页面访问中，超过99.5%是顺序访问，这意味着随机访问的数量始终比顺序访问的数量少两个数量级。