标题：大规模分布式分区iSAX
本文是2018TKDE-Massively Distributed Time Series Indexing and Querying的会议版本，更详细的思路在TKDE中有所阐述。

编者的总结

本文是第一次把similarity-search whole-matching用到了分布式的环境里面，基于iSAX索引，比较重要的思想，是先对序列抽样，然后按照各bit进行分partition，这里是需要有先验知识的，要不分不出来。
本文的效率重点是batch query，或者说是并发量，对于单个query的查询帮助作者没有提，但想必不会太大。

编者的思考

单从高并发的角度来讲，master提供了与client的连接，还要包含所有分区的分区表于内存中，提供所有请求的路由，这对于master的压力过重了，并发量太高时master会扛不住；最好看一下query response time中master和worker的占比各是多少。
从索引构建的角度来看，是需要有先验知识的，需要先有数据集，然后取sample；如果没有先验知识，缺少balance手段。
最后是对于单查询来说，帮助太少了，而单查询一般是比较重要的，毕竟时间序列similarity search,不会有M级别的特征序列需要同时查询。

ABSTRACT

提出了一个并行的index解决方案，可达到G级别的时间序列个数，也有一个并行的query策略，可以利用好这个index。1G个时间序列，索引构建只需两个小时。

I. INTRODUCTION

UCR方法只适合于single长序列，query短序列，不适合于若干短序列。
本文的设计思路如下图：

image.png

time series分布式存储，自然就有各个split的分布式index，最糟糕的就是每个query都要过所有index，Ideally是每个query只用找那么一个index。
（作者仿佛额外关注大量的query的统计时长）

II. PROBLEM DEFINITION AND BACKGROUND

本文的问题是近似KNN，怎么定义近似呢，就是第k个结果和Q的距离，相比于真实的第k个结果和Q的距离之间，放大不能超过(1+ $\epsilon$ )

III. DISTRIBUTED PARTITIONED ISAX

本文算法的核心在于如何将众多的ts合理的分割到各个partition去，作者采用的方法是先进行采样把进入各个partition的外层条件先分割好，sample肯定不能保证绝对平均，这主要取决于sample的质量，一般应不会太差。

取到一组sample，先平均分给每个worker，然后每个worker分别计算它们的iSAX words，反馈给master，master要决定如何对他们进行分割。分割的原则肯定是要让新分割成的两个区域等分原来的区域，分割可以依赖iSAX words中的任何一个bit。

作者提供的一个分割策略：首先选择当前分割成的最大的区域(包含sample series最多)，对该区域上每个segment上的所有time series的数据点做均值和方差，得到 $\mu ± \sigma$ 的一个interval，如果试图分割的那个bit落在这个interval，则进入备选。在所有备选中，选择距离 $\mu$ 最短的那个，作为分割点，直到分割出来用户设定的W个partition。