标题：Coconut：静态和流式time series数据上可扩展索引的有序总结

本文还是关于similarity search，不过streaming data series上的，应该是第一次被提出来。

Abstract

作者认为当前similarity search在性能/存储开销上无法做到较高的可扩展性，其主要问题是summarization(iSAX等)无法排序。
因此作者提出了Coconut，基于一种可排序summarization的索引，可以用于streaming series。
作者说目前的这些summarization最大的问题就是无法排序，比如说iSAX，按第一个segment排序了，后面的就是乱掉的了。作者打了个比方，类似对于一个多维的点，你只按照第一个维度排序，那肯定无法保证相邻顺序点之间的距离最小。
这也导致了两个问题：

1. 传统DB里面索引bulk loading的方法用不了了，因为值没法排序。因此目前的索引技术都是自上而下的寻找插入位置，当节点满载时分裂，这会产生大量的小的随机I/O。
   另外，最后iSAX树成型之后，叶子节点也不是存储在一起的，还是会导致大量的随机I/O。
   还有，这种自顶向下的插入使得没有办法从时间上切分数据以支持变长窗口上的高效查询，因为总会有updates来分割节点更新这棵树。
   尽管这种index可以接触到完整的数据历史，但是如果只想接触最近的数据，就不大行了。
   总的来说，作者对这种自顶向下的插入意见非常大。
2. 因为没法排序，所以没法把数据均匀的进行分割。现有的技术是利用在所有segments上的一个共同前缀，没有共同前缀的，没资格在一个节点上。这使得（几乎）空节点率很高。

我们的解决方案：有序summarization，核心思想是让不同的bits表示不同的Segments，把更重要的bits放在前面。这些序列被排列在一个z-order曲线上，更相似的时间序列会被挤在一起。
有序索引的好处不仅有剪枝，而且有：

1. 支持高效的bulk loading和索引更新；
2. 节点内部序列更密集；
3. 可以高效的对不同时间分区进行merge，以支持变长查询。

作者设计了Compact and Contiguous Sequence Infrastructure (Coconut)解决方案，就基于上述的有序summarization进行索引。支持bulk-loading，支持日志结构式的更新，这样就可以维护一个连续的索引。大量削减了各阶段的随机I/O，还可以通过排序来分割各个节点的data series，用中值来作为一个分割点，使得每个叶子节点至少半满。

2. Preliminaries and related work

3 Problem: unsortable summarizations

unsortable的问题在所有的分段summarization上都有，本文用SAX作例子，实际上所有类似地summarization都可以用

3.1 Index Construction

批量装载索引，通常（比如B树）都用外排的方式来实现。

image.png

• 自顶向下的插入法：目前iSAX类似的插入方法，即使有内存buffer，最差情况下也是。如果插入是均匀分布的，由于cache miss的概率是，所以期望最差时间复杂度是，最后一项是最后把缓存写回。综合来看，缓存对于大批量bulk-loading来说是不够用的。
• 自底向上利用外排Bulk-Loading：首先读所有的序列，分chunk进行局部排序，写回；然后将partition再读上来做外排，一个input buffer，一个output buffer，排好序写回。最终在这个排好序的数据上，建索引。两读两写，折腾了4次，时间复杂度次IO。

数量级上的差异是显而易见的，除此之外，外排带来的query process收益也非常大。首先，当查询沿叶子遍历时，更多是连续I/O。其次，叶子节点中序列可以被压缩，不必给未来插入的序列留空间，这样I/O效率就更高了。

3.2 Splitting Nodes

也是有两种分割方式。

• 基于前缀的分割。就像iSAX这样，问题就是分割不均匀，最差情况下大多数叶子节点只有一个entry，空间占用是块。
• 中值分割。类似B+树。可以保证每个节点至少半满，空间占用时块。

4. COCONUT

4.1 Sortable Summarizations

将SAX words前面的几位拿出来单独放在前面，后面的位置则按同样顺序放在后面，这样就让Sax words前后位之间有顺序关系。

image.png

4.2 Coconut-Trie

基于上面的这种bits interleave，可以实现key有序。本节提出的Trie树，是自底向上去构建一颗iSAX树，构建出来的结果和iSAX是完全一致的，分割也是基于前缀的。因此Query的时候完全采用iSAX一致的方案。
基本思路是，在内存缓存中计算出所有的invSAX,SAX,record position，然后按照invSAX分别排序，数据量大的话用外排统一排序。排好序之后，依次读取，每种sax表示作为一个叶子节点，如果是新的叶子节点，要考虑和现有的树的前缀进行对照统一（通过mark掉后面不重要的位），然后插入到现有的树的某个位置。一轮插入之后，就要进行压缩，将每两个相邻的兄弟叶子节点尝试合并（有共同前缀+不超过叶子容量），压缩之后，将叶子节点的内容flush到磁盘，腾出内存。

image.png

注意到本方法除了最开始的读入以外再也没有碰过原始序列，因此构建会非常快，但是数据并不是紧密存储的，如果想要更好的查询效率，可以物化这课树，把序列读进来，分叶子存储，不过构建就要更慢一些了。

4.3 Coconut-Tree

Trie树空间上还是比较浪费的，每个叶子节点可能就是半满的状态。另外树有可能非常倾斜，对于查询来说比较糟糕。
Tree树改进了上述问题，通过中值进行分割。读取，计算，排序，都不变。在完全排序之后，通过B+-Tree bulk-loading算法来构建最终索引,其基本思路就是依次从每页的key值中拿出来放到上层节点，上层节点溢出再分裂来操作的。整体就是一个B+树的思路。当然，也可以物化来顺序存储序列。

image.png

近似Query的时候要访问目标叶子节点周围几个叶子节点即可。
精确查询用的是ADS的思路，把所有invSAX表示放进内存，对每种SAX表示都算下界，然后边剪枝边从Tree中取数据计算距离。
值得注意的是，由于扫描的是invSAX，所以扫内存的同时，也在顺序的扫磁盘，就更加高效。

5. EXPERIMENTAL EVALUATION

whole-matching 100GB 277GB两个真实数据集，加一个合成数据集。
Coconut的实现是C语言，基于BerkelayDB实现算法。
由于精确查询需要内存中的SAX表，构建SAX表在精确查询开始时多线程构建，所需时间算作精确查询时间，经常均摊在多次查询中。

5.0 Number of Segments

首先对分段个数进行实验，用100GB数据集和100个精确查询，内存限制为100MB。

image.png

1. 首先说Space方面，经编者重复实验，CTree的Index Overhead基本准确，但是CTree-Full就比较tricky了。

   • 注意到本文的CTree-Full是要把序列数据写进B+树作value，这就意味着索引大小必然比数据集（100GB）大小要大。那为什么图中显示只有几GB呢？可以理解为索引大小 减去 数据集大小，即额外索引结构的大小。不过由于这两部分在B树中不可以被拆分，源数据我们一般也不删除，总共的磁盘占用为100GB（源数据集）+100GB（B树中的数据）+图中所示灰色条（B树结构） 203GB左右。因此，图中数值意义非常有限。
   • 另外，CTree-Full首先需要进行外部排序，会生成一个和源数据集大小等大的有序数据集（100GB），虽然可以在索引构建后删除，但是构建过程中不能删，因此构建时peak disk space usage将高达303GB。

2. 分段较多时，剪枝效率较强，因此精确查询快一些。

3. 文中最后考虑分段为32时，空间占用翻倍，最后选择用16作分段数。

5.1 Indexing

• Coconut Tree (Full)的索引构建速度非常快，但是Trie-Full会很慢因为最后一阶段把原始无序数据要写到有序叶子节点去。
• DS-Tree的构建速度太慢了，主要是由于动态分割自顶向下逐条插入。
• ADS+在内存较大时很快，由于都在buffer里；但是内存小点就不行了，因为随机读写会很多。

• Coconut Tree排序速度很快，因为基本就是在内存里排序的。

  
  image.png
• 物化方法里面，DS-Tree和CTreeFull额外空间占用较小，空间占用比较紧凑。

• 非物化方法里面，CTree的优势更大，节点数少，叶节点密集。

  
  image.png
• 可以看到ADS当数据量大之后随即读写越来越频繁，并不太适合大数据量的索引构建，而CTree的外部排序代价增长的就没那么快；

• 另外，CTree-Full的时间大部分都花在源数据的外排上，而CTree的排序时间就非常小，因为key小了很多。

  
  image.png

• 序列长度增长到1K左右，性能没有太大退化，幅度和ADS保持一致。

  
  image.png

5.2 Querying

• 精确查询上CTree和CTree Full达到了秒级别（_{100GB），近似查询在毫秒级别（}100GB）
  image.png

• 近似查询的质量上，CTree家族会更好一点（中值分割更紧密合理）

  
  image.png

5.3 Updates & Complete Workloads

• Mixed Workloads是指先bulk-loading一批数据进行索引，然后插入一部分，查两条query，循环这个过程，模拟真实应用场景。这个倒是蛮新颖的一个实验，尤其在时间序列数据分析领域里。似乎在这种场景里，物化方法退化的机器严重，但是作者却没有解释原因，猜想CTree-Full是bulk-loading技术无法使用带来大量随机I/O；ADS-Full的话，缓冲区会经常溢出需要从源数据里随机I/O调入。

  
  image.png

• 真实数据集下的实验结果，有了bulk-loading的机会，CTree-Full就好得多。最后作者发现在真实数据集上，数据非常紧密，设计的剪枝能力变得很弱。

  
  image.png