标题：对大量数据序列的交互式探索索引
本文于2016年VLDB Journal的ADS: the adaptive data series index属于同一篇，期刊版本的更为详细，这里二合一做讲解。

编者的总结

1. ADS整体体现的就是一个非物化(non-materialized)的思想，这个思想在之后也是被广泛使用的。
2. ADS-Full实际上相当于提前把SAX表算出来（速度很快），然后用SAX建树，最后统一写数据。理论上，应当比isax2.0+要更快一些。

编者的思考

1. ADS+的小叶子threshold竟然在实验中被设置为10，我预估这将大大影响召回率、准确率等，查询效果在全文被严重忽略。
2. SIMS精确查询算法中的skip sequential scan在代码中如何体现，最终是否是顺序磁盘读，有没有理论根据，这些还有待考究。

ABSTRACT

核心思路就是先把用户需要query那部分数据进行索引，用不到的先不索引。

1. INTRODUCTION

image.png
image.png

3. THE ADAPTIVE DATA SERIES INDEX

3.1 The ADS Index

尽量减少索引构建过程的I/O，在ADS中，iSAX-Tree中只保留iSAX表示，不会在叶子节点保存源数据。I/O过程只在必要的时候(query中用到了)，才会真正执行。

3.1.1 Index Creation

image.png

索引构建过程，只会顺序扫描源数据，用以生成iSAX表示，把这些iSAX表示和源数据指针置于buffer（FBL, First Buffer Layer），直到内存满，然后开始处理，把buffer里的iSAX逐个插入索引树，叶子节点的iSAX表示各自存入一个buffer(LBL, Leaf Buffer Layer)，然后刷入磁盘。之后重复这个过程。

• 实际上就是非物化的iSAX索引构建。

3.1.2 Querying and Refining ADS

Query首先要定位到具体的叶子节点，如果叶子节点是PARTIAL的，那就取出所有的文件指针，进行排序，然后到磁盘里读出来，读到LBL中，如果内存满了，就把LBL中的源数据序列，写到磁盘里，此时叶子节点就是FULL状态的了。

• 查询的过程，实际上也是逐渐物化的过程。
  精确查找，首先是以近似查找来确定BSF，然后扫描全部进行剪枝。

3.2 The ADS+ Index (Adaptive Leaf Size)

ADS+是ADS的一个进阶版本，正如Intruduction中的第二张图，Leaf Size对构建和Query的影响是一个trade-off，难以兼顾。因此本文的方案是，提供两种leaf size，一种大leaf，用于构建；一种小leaf用于query。
query的时候如果到了一个大leaf，则要读出iSAX表示，然后继续分裂，直到找到target leaf(小leaf sieze)，对其中的序列读出，并写入磁盘，变成FULL状态。同时，对于非target route上的新生成的leaf node，仍维持其PARTITAL的状态，不必读取。
以此通过逐层延缓具体I/O，提升效率。

image.png

3.3 Partial ADS+ (PADS+)

PADS+进一步缩短了DATA-TO-QUERY的时间，它只顺序读一遍源数据，计算iSAX，直接放到第一层的iSAX，作为一层FBL，如果内存不够存，就都刷到磁盘上。qurey的时候基于这个很大的FBL进行分裂，查询，target leaf node将最终把数据序列读出，计算距离，并写入磁盘。
这种方式尤其适合于只需要少量的近似查询，或者workload非常偏斜的情况。

3.4 Updates

插入会在源数据上append一条，计算iSAX，插入到iSAX-Tree中，对于FULL leaf node，要做好标记，方便下次query的时候做整合。
删除只要做出标记就可以，之后的insertion会复用那些空间。

3.5 Full index construction: ADS-Full

如果一定要一个物化版本的isax（查询快），ADS-Full就是一个方法。
方法也很简单，首先扫数据集生成iSAX表示，利用这些iSAX表示建成整棵树，最后将源数据插入iSAX树对应的叶子节点，这一步利用LBL。

4 Exact query answering for ADS+

精确查询分两步走：

1. 多线程并行扫内存SAX表，算出一个MINDIST表；

2. 由于SAX/MINDIST表在偏移量上和数据表是对齐的，因此从前到后顺序扫一遍源数据表，MINDIST满足条件的就读出来计算真实距离。

   
   image.png

作者在文中称这种磁盘读的方式为skip sequential read/ sequential reads。
然而实际上，这种方式相比于随机读取，是否真的有速度提升？或者说在物理磁盘上，这种方式真的是顺序的么？编者对此持怀疑态度。

6. EXPERIMENTAL EVALUATION

比较对象主要是iSAX2.0，而且为其补充了查询时的LRU buffer。
Interl Xeon machine with 64 GB内存， 4x 2TB, SATA, 7.2K RPM Hard Drives in RAID0.
算法都是C语言写的。

6.1 Reducing the data to query time

6.1.1 构建时间

500GB数据集Randomwalk。

• 由于IO次数大幅度减少，构建效率提升了很多倍。

  • 文中一个例子，20K叶子大小时，iSAX2.0是8h，ADS是半小时，主要就是IO时间大幅缩减。

    
    image.png

6.1.2 data-to-query time

• 构建时间的缩短是以查询时间变慢为代价的，因为需要在查询时不断物化，因此ADS的查询时间是比较夸张的，相比于已经物化过的iSAX2.0.

• 好在构建时间是很短的，可以很快开始查询来弥补这一不足。

  
  image.png

• 相比于ADS,ADS+的查询效率有大幅度提升，甚至超过了物化的iSAX2.0。其原因在于每次取的只是一个小叶子，IO方面要胜过iSAX2.0，但是查询精确程度方面就要降低一个档次，因为毕竟检索的序列数少了很多。

  
  image.png

6.1.3 Choosing the query-time leaf size

作者实际去做了各种query，根据磁盘页利用率最终选择了10，这样一个超小的leaf size。虽然磁盘利用率和查询时间都很不错，但是最重要的查询精确度将会大打折扣，这是作者没有考虑的问题。

image.png

6.1.4 Data Touched

这张图从本质上揭示出，ADS+查询速度快，主要是由于其小叶子节点太小，load的数据非常少。

image.png

6.6 Fast full index construction

• 这里的iSAX2.0实验比原版实验快了非常多（500M，100h），有可能是机器的性能不同，这里持怀疑态度。

• 因此这也无法与iSAX2+进行比较。

  
  image.png

6.7 Efficient exact query answering using SIMS

在这里，作者说ADS+（SIMS精确查询算法）在大数据集上，剪枝主要发生在磁盘页的层面上。而一页又不止一个序列，因此浪费了大量的时间在读取无用的序列上。

• 左图是构建时长，右图是精确查询时长。

  
  image.png