2014SIGMOD-(ADS索引算法)Indexing for
标题：对大量数据序列的交互式探索索引
本文于2016年VLDB Journal的ADS: the adaptive data series index属于同一篇，期刊版本的更为详细，这里二合一做讲解。
编者的总结
- ADS整体体现的就是一个非物化(non-materialized)的思想，这个思想在之后也是被广泛使用的。
- ADS-Full实际上相当于提前把SAX表算出来（速度很快），然后用SAX建树，最后统一写数据。理论上，应当比isax2.0+要更快一些。
编者的思考
- ADS+的小叶子threshold竟然在实验中被设置为10，我预估这将大大影响召回率、准确率等，查询效果在全文被严重忽略。
- 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+
精确查询分两步走：
- 多线程并行扫内存SAX表，算出一个MINDIST表；
-
由于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
