标题：SING: 用GPU对序列进行索引

本文实际上只用GPU加速了内存数据集上的精确查询，索引构建沿用了MESSI，无GPU参与。

III. THE SING DATA SERIES INDEX

首先讲一个基本的方法M+G，然后在其上优化得到SING。

A. The M+G Solution

1. 首先在CPU上用做一次近似搜索拿到BSF。
2. CPU-GPU同时计算：
   1. 然后将query PAA和iSAX 表传到GPU上去算下界距离，算完返回下界距离表，和数据集一一对齐。
   2. 与上一步同时，CPU遍历这棵树，把下界距离小于BSF的叶子节点以round rubin方式扔到一组优先级队列中。
3. 等到上一步完成后，每个线程分配一个队列，依次处理，下界距离条件满足的就算真实距离。

B. The SING Solution

• SING的SAX表不是按照源数据集大小的，而是按照索引的中序遍历，这样拿到下界距离表之后，再次处理时局部性更好；
  【编者注：如果是动态数据集，有额外插入，这里会怎么办，移动后面全部序列吗？】
• SING在发送SAX表给GPU之前首先对第一层节点剪枝，剪掉的整颗子树，由于在SAX表上是连续的，这一部分则不发送给GPU。
• 实际上，GPU算下界距离速度比CPU相应部分要慢很多，针对此设计两个策略
  1. 把SAX表分成若干细粒度的chunk，GPU算完一个返回一个；
  2. CPU不等GPU运算，直接开始处理优先级队列，如果节点所在的chunk下界距离算完了就用，没算完就直接CPU来算。

IV. EXPERIMENTAL EVALUATION

• M+G优化效果不佳，SING的效果却很好。但作者没有提到底是哪个策略起到了这个作用，局部性，预剪枝，还是分chunk？

  
  
  

  image.png