标题：半径梗概：时间序列数据的大规模分布式索引
本文和2018CIKM短文：Spark-parSketch: A Massively Distributed Indexing of Time Series Datasets几乎一样，合并在一起讲。

（billion）G级别的时间序列索引，支持近似similarity search，可以在精度和速度上做trade-off。本文第一次在并行架构上做出尝试。类似的工作可以见2020ChainLink。

编者的总结

1. 本文做的是分布式近似whole-matching，利用的是分布式LSH的方案，和2020ChainLink是类似的。本文讲ts与一组随机向量做内积，得到一个sketch向量，进行random分组，得到不同的几个grid structure，分布着所有的time series point。查询时以出现的百分比进行衡量。
2. 本文最突出的亮点在于召回率做的非常高，基本都达到了50%以上。
3. 本文的query performance/construction time都较低，而且query performance还是主要衡量吞吐量平均时间。
4. 这应该是第一篇分布式similarity search，实现也比较简单，但是没有做精确的可能。

编者的思考

1. 索引大小没有实验验证。
2. 用户的参数比较多，有使用不便的问题。
3. 实验只用了两个数据集，略显单薄。

II. RELATED WORK

B. Sketches

sketches是把一个时间序列和一组随机向量做内积，得到一组sketch，两个time series之间的距离，可以由两组sketches的距离进行近似估计。

image.png
公式中可以看到，sketches之间的距离是把真实距离的倍。
本文的方法是LSH的一种，即相似的time series有更大的概率发生哈希碰撞。

III. PARALLEL SKETCH APPROACH

A. The Sketch Approach

对于一个m维时间点（长度为m的时间序列），让它和N个m维的±1随机向量做内积，得到N个值，构成一个N维向量，就是这个时间序列的sketch。
作者对于sketch的距离做了一个实验，和SAX距离（较高精度）进行比较，发现sketch距离和真实距离更近，但是没有下界性质。

image.png

作者再做一些网格，假设有|g|个，每个网格负责一些随机向量，也就是负责sketch的几个维度。两个序列在不同的网格中距离不同，可能远也可能近，但是两个相似的序列，会有更大的概率在更多的网格中有更近的距离。

分成几个网格（一般不超过4），网格中的距离如何算近，有多少相似的格子满足算相似，都属于用户参数。
以下是两个网格的例子。

image.png

D. Massively Distributed Index construction

索引构建分成两个阶段，第一阶段首先由master生成随机向量，广播给各个worker，mapper读time series，与随机向量做内积，生成sketch，map成(group_id, (group_data, time_series_id))的形式进行emit；
其中group_id就是如果sketch被分成N个group，那么group_id就会是[1,N]。
如果是每个group可能包含overlap的维度的话，为了避免数据重复，也可以map成(dimension_id, (dimention_data, time_series_id))

第二阶段，reducer接收了各个mapper发来的group_id和对应的值，group一下，进行存储，存储在内存和HDFS中都可以。

CIKM版本中的增强版会把grid存储到RDB里面去，其实是RDB的不同实例，文中用了PostgreSQL。

image.png

E. F-RadiusSketch

从概率上讲，给定grid的维数，使用的grid越多，那么计算两个序列之间相似度的标准差就越小。因此经常会选择和处理器个数同样多的grids。
另一方面，可以想象，random vectors越多，精度也会越高（随机映射的越多），作者做了个实验，发现256个是一个转折点，数量再多之后精度趋于平稳收敛了。

F. Query processing

整体的思路也比较明晰。输入是一组queries series，mapper读取这些queries series，与同一组Random vectors做内积，得到每一个query的sketch，然后按照group策略，对这些sketch切割重组形成若干sketch，flatmap成(group_id, (group_data, query_id))的形式，进行emit.

第二阶段，每个worker收到一个或几个grid index结构，同时接收对应group_id的pair，对于每一个pair，在grid index中对应的cell要进行查找，把那些相似的序列找出来，形成(query_id,[time_series_ids])的pair，进行emit.

CIKM中这个查找有增强版，就是从DB中读取grid，进行grid分发。

image.png

第三阶段，reducer对于每一个query_id，对其中每个time_series_id进行计数，去计数最高的就可以了。

如果要做KNN的话，就取前K个。有的时候甚至不到K个，那就要在第二步的位置，对应的Cell周围一圈8个cell也要取到了，不过精度就会下降，无法得到准确排名。

image.png

IV. EXPERIMENTS

作者提供了两个版本的实现，一个是RadiusSketch，另一个是F-RadiusSketch。F那个版本，主要是random vectors到达256，另一方面，group选取的策略是随机的，overlap的。
对于每个版本，也实现了一个集中式，一个分布式的。
环境是32台机器，每台8核64GB内存。

一个真实数据集，491GB；一个random walk，1TB。

image.png

B. Grid Construction Time

1TB要构建一个小时，增长基本是线性的。

image.png
image.png

并行度上来看，是不错的。

image.png

C. Query Performance

这里的query性能又是以吞吐量为衡量指标，而对比方法iSAX2+，是单机运行的。是iSAX2+的13倍，1TB数据，即使平均下来，也有200s。

image.png

第二，召回率随groups数目增长近似亚线性单调增长。

image.png
第三，召回率是比现有近似方法要好，基本可以稳定在50%以上。
image.png