2015SIGKDD-（时序数据的Benchmark）Query

2021-08-17 本文已影响0人 Caucher

标题：时间序列数据索引的查询负载
本文和2018年VLDB期刊Generating data series query workloads属于同一篇文章，按照惯例，本文还是融合了二者的内容。
是做时间序列benchmark的一篇文章。

编者的思考

本文生成benchmark主要是靠改变原始数据集，这一点其实有些反直觉，也不够通用，希望能够给定数据集，算法生成一组query做benchmark，不改变原始数据集就好了。
本文只对归纳技术的TLB做比较考虑。可是效率和效果一般是有trade-off的，只考虑效果有失偏颇。对于一般意义上的benchmark，我们希望既能合理检验索引的剪枝效果，也对整体查询效率给出客观考量。换句话说，索引技术的TLB，不能完全决定该索引的性质。

编者的总结

论文设计的思路是去比较不同归纳技术的TLB，即下界的紧密程度，尤其是要比较那些下界都很紧的归纳技术。对于这些归纳技术，过于“简单”的query，大家都可以轻松剪枝掉大部分，计算一小部分数据集的真实距离。但为了能够比较优劣，本文构造出一些比较难的query，使得在这些query的1NN序列周围，均匀地向外层分布着很多干扰序列。这样即使是TLB很大的一组归纳技术，也都可以根据真实距离计算次数，进行排名。
读者可能有疑惑，既然是比较不同归纳技术的TLB，搞一组query直接算TLB求均值不就好了，为什么要这么麻烦？因为随机生成的，或者是数据集里的，主要都是些简单的query，得不到一个准确的评判，尤其是对于那些下界已经很紧的归纳技术，更是无法比较，因此要构造更难的query。

ABSTRACT

时间序列的索引已经提出很多，目前无法公平评估这些索引的效果。
本文阐明随机选取序列的方法不可取，定义了如何度量query的特征，因此可以有效比较归纳方法和索引技术。

1. INTRODUCTION

之前用于实验的query主要都是简单Query，因此对索引的测试也只能局限于有限的部分测试。本文提供对query难度的度量方法，表示一个索引为了处理这个Query所要承担的工作量。这种难度的定义也是基于下界函数。

2. PRELIMINARIES

本文主要关注最近邻（1-NN），欧氏距离。

2.2 Data Series Indexing

索引技术主要包含以下三种：

Summarization & spatial access method：先用DFT，DHWT，PLA等降维，之后利用空间R-Tree对高维向量做索引。
Data series speciﬁc summarization & index：比如iSAX(SAX表示)，DS-Tree（EAPCA），SFA（频域SAX）
Summary reorganization & multi-level scan：并不构建索引，只对磁盘的时序数据做一个有效存储组织。

3. CHARACTERIZING WORKLOADS

3.1 Requirements for meaningful and effective workloads

一个好的workload，其中的query要对summarization的质量有很好的度量；而每个query的难度应该精准地刻画这种summarization应答查询时需要的工作量。
因此我们要准确定义难度，还要筛选query，这种难度度量应该满足以下条件：

索引内部的准确性：对于给定一种summarization，不同的query在其上搜索有不同的工作量，这个工作量之比，应该就是难度之比。而且，应该在任意给定的summarization之上，都有这个性质。

image.png
索引间的准确性：给定一个query，在不同的summarization上有不同的工作量，工作量之比，应该正好是偏差之比。工作量越大，证明索引的剪枝能力越弱，偏差也就会越大。

image.png
- 这一条是query的性质，与难度定义无关。

3.2 Index-dependent query answering effort

3.2.1 Lower bounds, ATLB, and TLB

首先给出下界紧密程度的定义：
ATLB是指一条query和一个数据序列的估计距离和真实距离的比值，由于有下界性质，所以这个比值总是大于0小于1的，越接近1性质越好。

image.png

TLB是ATLB在一个数据集和一组Query之间的均值。

image.png

考虑在一次查询中，要找1NN，哪些点是必须计算真实距离的呢？
设真实距离是MINDIST，那么距离query真实距离比MINDIST/ATLB(x,q)要小的序列x是必须要计算距离的。因为即使索引第一次直接找到了true answer，那么这个BSF值也就是MINDIST，下界值ATLB(x,q)比MINDIST小的不能被剪枝，那么真实距离也就要小于MINDIST/ATLB(x,q)。

image.png

3.2.2 Index-dependent measure of minimum effort

给一个定义ME(Minimum Effort，最小工作量)：在一次查询中，至少要计算真实距离的序列个数占数据集总量的比例就是ME。也就是那些满足下界值ATLB(x,q)比MINDIST小的序列数占比。

image.png
- 注意到这个最小工作量的说法，因为事实上的工作量要比这个大，不可能每次查询都直接从距离最小的开始查起。
- 同时，由于定义中有下界函数，所以ME也是和特定归纳方式所绑定的。

3.3 Intrinsic query hardness

3.3.1 $\epsilon$ -dependent Hardness

接下来给出一个和归纳方式无关的定义。

-最近邻：指和query序列距离(1+)MINDIST的序列们。
image.png
- 这个 $\epsilon$ 本质上刻画了一个以query序列为球心的超球，我们称为 $\epsilon$ 区域。
Query难度：-最近邻个数占数据集总量比例。
- 注意到，一般我们会让 $\epsilon$ 区域的序列都是ME中的序列，那此时要满足 $\epsilon >= (1/ATLB(x,q)) -1$ 。
- 虽然可以用ATLB来定义困难程度中的 $\epsilon$ ，但本质上困难度和TLB是两种定义。困难度是在描述数据集中query 1NN序列周围（同等或稍大距离）的序列的密集程度，大家越是和1NN序列距离差不多，这个query就越难，和1NN真实距离的绝对值反而没多大关系。
- 像下面这张图，q2就要比q1难，因为有很多序列都和1NN的距离差不多，形式化的说，给定 $\epsilon$ ，q2 $\epsilon$ 区域里的序列个数总是比q1要多。
  image.png

3.3.2 $\epsilon$ -independent hardness

3.3 Discussion

像上图的两个query，q2要比q1更难（区域内的点更多）。本文认为，q2比q1更适合作为benchmark。原因是随着的增长，数据点的数量也是近似线性增长的。
- 索引技术中的下界距离，可以理解为一个切割点，估计距离低于这个切割点的要计算真实距离，高于这个切割点的则不必计算。也就是说切割点下方的才是ME。
- 对于q2，我们更容易分辨出来这个切割点位于哪个位置，只要看归纳算法真实计算距离的次数就可以在图中定位到具体的 $\epsilon$ 。而q1，可能很多归纳技术计算距离的次数都一样，但是实际上它们的TLB并不相同，此时便难以区分。

4. EVALUATION OF PREVIOUS WORK

4.1 Datasets and Workloads

三个数据集，randomwalk, DNA, EEG，长度有三种，64,256,1024。
如何使用数据集，以前的研究有两种方式：

用一部分数据集做索引，另一部分做query workload
全用做索引，一部分拿出来加点噪声做query workload.

本文用第一种，用之前首先乱序数据集。

4.2 Hardness Evaluation

这三个数据集的query普遍比较简单。

image.png

5. QUERY WORKLOAD GENERATION

因为目前的query大多是简单的，为了更困难一些，我们在原有的query集上加一些 $\epsilon$ 区域内的点。
整体的算法思路是，我们先随机生成一些简单的query，称为集合Q（数量大于n），然后定义一组n个困难度值，从低到高，总和不超过1（覆盖的总 $\epsilon$ 区域不会超过数据集的范围）。然后我们要寻找n个query，使得它们的困难度分别为我们定义的这组困难度值。

5.1 Finding Non-intersecting Queries

如上所述，我们首先不希望这n个query的 $\epsilon$ 区域是有交集的。因为我们要把找到的query MINDIST周边的点逐渐增多以变得更困难，为了使改变一个query的困难度，不会影响其他query的困难度，所以希望它们是不相交的区域。
image.png
建模：为了从随机生成的集合Q中寻找一些不相交的query，我们将每个query序列做成图中的一个点，如果两个query $\epsilon$ 区域不相交，就在它们之间连一条边。我们希望找到一个最大的簇，这个簇是一个完全图（分量），如图q1,q2,q5那样，代表簇中两两兼容。
算法：精确算法是NPc问题，因此采用贪婪算法，从图中度数最小的开始增序选择，如果和已选集兼容则入选，否则落选换下一个点。直觉是度数越大的，兼容的可能性越高。最终找出n个入选的query，依次分配一个困难度值(比目前的Query更困难）。

5.2 Deciding the Number of Points to Densify

如上所述，目前每个困难值都有一个对应的query，接下来要在每个query的 $\epsilon$ 区域内补充一些点，来达到这个困难值，但注意补充点时，数据集的基数也变了，因此这是一个线性代数的问题。
image.png
解一个矩阵就可以得出x1,...xn，分别对应每个query的 $\epsilon$ 区域应该补充多少点。

5.3 Densiﬁcation Process

为 $\epsilon$ 区域致密不能随机生成一些点，因为z-norm之后这个点有可能跑出去，目前考虑到的致密方案有三种：

在目前的区域中的点随机选择，然后加一点噪声；
- 特征：对原有的 $\epsilon$ 区域内的数据分布影响不大。
- 缺点：对于那些非常紧的归纳技术，加了这些点可能根本不会影响到这个query的难度，因为对于这些归纳的技术，其ME范围可能只是 $\epsilon$ 区域中很小一部分，新加的点在外环和没加其实不会影响查询时的工作量。
向1-NN加一些噪声；
- 特征：大量生成的点都聚集在1NN周围，也就是 $\epsilon$ 较小的区域， $\epsilon$ 较大的区域会非常稀疏。
- 缺点：各种归纳技术的ME都趋于一致，难以进行比较。
在 $\epsilon$ 区域加点使得其中的点更偏向于均匀分布。

哪一种更好呢，作者做了一组实验来说明。

5.3.1 Random densiﬁcation

首先来看第一种方法。下图是将query用此方案致密后的实验结果，每一张图里分三个子图，上方的是随 $\epsilon$ 增加数据点的分布情况，右边图是各种归纳技术的ME，中间的是各段 $\epsilon$ 范围内的数据点对ME的贡献情况，是一个热力图。

结论1：归纳技术用的字节数越少，ME就越大，而此时ME中的点大部分都不在 $\epsilon$ 区域内。
结论2：对于字节数使用较多的归纳技术，大部分ME中的点都在 $\epsilon$ 区域内。
结论3：ME在数据集中的分布，和原始数据集的分布是密不可分的。观察下方两幅图64-bit归纳技术部分，SAX比其他几种技术的ME小不了太多，但是覆盖的 $\epsilon$ 范围要小的多，主要是由于数据集本身的分布（ $\epsilon<=0.5$ ）也是非常少的而且递增幅度不大。
image.png

5.3.2 1NN densiﬁcation

image.png

5.3.3 Equi-densiﬁcation

在3.3节中我们讨论到，在 $\epsilon$ 区域内数据点分布更均匀的query是更好的benchmark，原因在于可以轻松通过计算真实距离的次数推断出 $\epsilon$ 。

但是要注意到，我们实际比较的，不是各个归纳技术对应的哪个更小，我们要比较的是谁的TLB可以更大一些。TLB和是负相关关系，确定更小确实可以推断TLB更大；但是从定量上来看，它们可不是严格的线性反比。
- 举个例子，根据公式 $\epsilon = (1/ATLB) -1$ ，对于 $\epsilon$ 区域中某些数据点ATLB范围在[0.5,0.6]的，对应的 $\epsilon$ 范围是[0.67,1]，宽度0.33；而对于ATLB范围在[0.6,0.7]的，对应的 $\epsilon$ 范围是[0.43,0.67]，宽度0.24，范围宽度并不一致。
- 根据反比函数性质， $\epsilon$ 较小的位置，范围宽度也越小。
因此，我们将 $\epsilon$ 区域内的数据点的ATLB值（范围[0,1]），等分成若干个桶，每一个桶对应一个 $\epsilon$ 范围（宽度并不一致），尽量保证各个每个桶内的点个数是相等的。此时我们可以称之为 $\epsilon$ 区域内的点是近似均匀分布的。
这样在实际测试中，TLB不在一个层次的归纳技术，计算真实距离的次数将会显著不同。因为不同层级对应的序列的个数近似相等，差一个层级就要多算一个层级的距离，差距自然也就拉开了。

image.png

很显然，第三种方案是最适合用来加点的。

6. EXPERIMENTS

实验对前述的三个数据集做实验。100000条序列，长度256。
给定一组query难度值，算法在原有数据集上补充一组点，然后找到一组query，满足给定的难度值。

6.1 Non-interfering Queries

就是贪婪算法去找 $\epsilon$ 区域不想交query点时候，最多能找到多少个点。

从图中来看，并不能找到很多query，前两个数据集， $\epsilon=1$ 时候只能找到几个query。
作者给出的解释是：我们的benchmark并不需要太多query。困难值的设定也是一个大的限制。
对于query太少的解决方案：改变初始值，跑个几百次，总归可以得到较多的query。

image.png

6.2 Densiﬁcation Mode

还是在比较三种致密方法，1NN的方法对所有方案都是差不多的，Random方法过度偏爱紧的下界技术（SAX），对于差一点的有过度惩罚。只有均匀分布的，最贴近真实TLB。

image.png

6.3 Case Study on Actual Indexes

EDQ是通过均匀分布找到的queries，Random是随机生成的。

下图可以标明生成的query难度均衡，比Random要好。

image.png

Random-H是只有难度>0.5的query集合
看来只有简单的和只有难的并不能很好的达成效果，只有均匀分布的才行。

image.png
为什么是上面这个结论呢？本质上还是 $\epsilon$ 区域内的数据分布来决定的，只有在区域内均匀分布，才能对各种归纳技术作出有效区分。
image.png

2015SIGKDD-（时序数据的Benchmark）Query

编者的思考

编者的总结

ABSTRACT

1. INTRODUCTION

2. PRELIMINARIES

2.2 Data Series Indexing

3. CHARACTERIZING WORKLOADS

3.1 Requirements for meaningful and effective workloads