2018ICDE-ULISSE:ULtra compact In

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

2018PVLDB-Scalable, Variable-Length Similarity Search in Data Series:
The ULISSE Approach
这两篇文章是同作者产出的，一个是会议，一个是期刊，前者只有4页，讲的实在是过于模糊了，建议看后者期刊的论文，讲的比较清楚（仍有一些小笔误）。

编者的总结

这篇论文的核心是将一组overlapping, continuous的，或者是仅在长度上有区别的subsequences进行归纳，基于iSAX提出了个uENV的表示法，用于表示其上下界限，进而提出了下界距离定义公式，以支持KNN-similarty search。
一个比较重要的参数 $\gamma$ 表示一个uENV的接管范围，能让这个方法更为灵活。
基于uENV的表示，能够造出类似iSAX的索引，使得一定长度范围内的query series，都可以和一组data series C进行KNN-similarty search，其结果将在C的所有等长子序列中进行选择。
这个可变长度的搜索较好地扩展了iSAX-similarty search的实用性，虽然在性能上有所牺牲，但这也主要源于搜索空间上变大了几个数量级。

编者的思考

这篇论文是基于iSAX做的一个可变长度的扩展，所以iSAX的问题，这里也都存在，这个作者在Conclusion也提到，future work会研究少量长序列的索引。
uENV这种表示方法感觉信息缺失比较多，其只保留了PAA极值，但对于KNN-similarty search来说确实足够了。但是如果能更好(信息更丰富)的归纳这样一组subsequences，也许会对其它类型的索引、算法也有更好的帮助。

标题：时序数据中，对于可变长度的相似性搜索，构造了高压缩的索引

Abstract

目前的时序数据索引可以进行相似性查找，但是长度是固定的，在索引创建时固定下来。本文设计的ULISSE可以实现可变长度的查找。
本文的贡献是两方面：

设计了一种representation，可以高效归纳多个不等长序列
基于ULISSE索引，设计了结合磁盘索引查找和内存顺序搜索的相似性查找算法。

1. Introduction

问题主要是针对变长相似性搜索来说的，已有的文献里有定长的搜索，通过对定长搜索的简单重复，可以搞出变长相似性搜索，但是时间空间都是爆炸增长。也有文献对这种重复进行优化，但是只是缓解了问题，没有彻底解决爆炸增长的问题，还没有进行Z-normalize。
本文提出的是第一个single index。就是不再对可能查询的每一个长度建index再考虑优化，而是只建立一个。基于的思想就是一个序列的索引里包含的信息肯定包含它的子序列索引里的信息。那么问题就在于如何重新组织索引里的信息，ULISSE的主要贡献，就是做了这样的一个summerization. 是否进行Z-normalization都可以算。

2. Related Work

定长索引
基于定长的思路，做的不定长索引，还是前面的两个问题
单个长序列中多个子序列之间的matching场景中，序列化的scan非常高效（本文的场景时大量短序列，以此说明仍需索引）

3. Preliminaries

subsequence子序列定义为连续的
Z-normalize
欧氏距离
Piecewise Aggregate Approximation（PAA），分段聚合，将序列D，每长度s分割成一个segment，取个均值，构成一个长度为w的向量，即将D在w维空间中进行表示，记做PAA(D)
iSAX
问题:VARIABLE-LENGTH SUBSEQUENCES INDEXING：给定一个data series集合C，和一个长度范围，建立一个索引要能支持在这个长度范围内的任意query series进行similarty search
similarty search：作者在这里将其定义为KNN问题，对于一个data series集合C，一个query series Q，其长度在一定范围内，任意C中长度等于Q的子序列都可以成为备选，选出其中距离最小的K个，就是KNN问题。

4. Proposed Approach

在说明方法之前，还是重申一下，这个论文方法的目的是为了能够高效归纳出一组连续的，overlapping的子序列，而不是对每个长度范围内的子序列都视为一个独立的序列。接下来以一个Data Series D为例，说明如何做这种summerization.

A. Representing Multiple Subsequences

首先给出一个master series的定义，对于D，和一个长度范围 $[l_{min},l_{max}]$ ，master series是D的一个subsequence，长度尽可能为 $l_{max}$ ，如果到了序列终点了，长度可以不足 $l_{max}$ ，但是最短不能短于 $l_{min}$ 。
如果只关心前k个PAA值，那么master series足以代表相同起点的所有长度范围内的subsequence。所以之后我们只研究master series。
假设D的起始位点为 $\alpha$ ，我们首先找出起始位点在 $[\alpha,\alpha+\gamma]$ 范围内的所有master series（一共 $\gamma+1$ 个）；将这些master series进行zero align平移，如下图，然后取PAA，通过在每个segment范围内找极值，我们在每个segment范围内，构成了一个containment area和一对envelope extremes。

image.png

B. PAA Envelope

这里对PAA envelope给了一个形式化定义，如下图：

image.png

这个L,U其实是一个向量，表示每个segment对应的PAA 最大值和最小值。

C. PAA Envelope for Z-Normalized subsequence

先略过，之后更新

4. Indexing the Envelopes

$uENV_{paaENV_{[D,l_{min},l_{max},\alpha,\gamma,s]}} =[iSAX(L), iSAX(U)]$
首先是这样一个uENV的定义，对刚才的paaENV取个iSAX，就是uENV了。后面我们会讲到，通过uENV，query和一个uENV里的所有子序列（长度范围在 $[l_{min},l_{max}]之间$ ）的距离可以估算出一个下界距离来。

5. INDEXING ALGORITHM

5.1 Non Z-Normalized Subsequences

这里作者提供了一个算法，用了一个滑动窗口的算法，还比较巧妙，可以完成uENV的计算。时间复杂度为 $O(w(l_{max} + \gamma))$ 。
注意到其中 $l_{max} + \gamma$ 是为了能计算第 $\gamma$ 个子序列的最后一段PAA值。另外， $\gamma$ 这个参数也比较有趣，它其实决定了这样计算出来的uENV最远能覆盖到多大的x坐标，这样意味着，如果 $\gamma<l_{max}$ 上图的containment area会在x轴方向重叠。

5.2 Z-Normalized Subsequences

先略过，之后更新。

5.3 Building the index

首先上一个索引的构建图。

image.png

索引是一个树形结构，每个节点都包含一个iSAX(L)和一个iSAX(U)，就是一个抽象的uENV，代表这个节点在各个segment的上下界。其中叶子节点包括一系列具体的uENV，每个uENV能够指向一组subsequence(起始位点连续在 $\gamma$ 范围内，长度在 $[l_{min},l_{max}]$ 范围内，这一组subsequence只需要指定 $\alpha$ 和序列id即可确定)。
索引可以按照iSAX(L)进行组织，也可以按照iSAX(U)进行组织，这里选择的是iSAX(L)。每个叶子节点都有一组相同的iSAX(L)的具体uENV。

现在的一个问题就是给定一个data series collection C，什么样的uENV可以插入到索引里？对于C中的每一个data series D， $\alpha$ 从0开始，以 $\gamma+1$ 为步长，分别构建uENV，插入到索引中。正如我们刚才所说， $\gamma$ 决定了一个uENV能辐射多长的x轴。

最后插入uENV到叶子节点之后，要更新这条更新路径上所有节点的iSAX(U)。
除了索引以外，算法还将所有的uENV以最高位的基数存在内存中。

5.3.1 Space complexity analysis

索引的空间复杂度占用为 $O((2w)bN)$ ，N是uENV个数，即需要索引的subsequence个数，极大程度取决于 $\gamma$

6. SIMILARITY SEARCH WITH ULISSE

6.1 Lower Bounding Euclidean Distance

iSAX支持定义MINDIST距离公式，使得MINDIST是ED的一个下界。作者给了一个MINDIST的定义公式，这个距离代表一个query series Q，和一组subsequence的距离。

image.png
作者随后即证明了对于任意的

\alpha=<i<=\alpha + \gamma + 1

，

D_{i,|Q|}

和Q之间的ED距离都比MINDIST要大。

编者注：其实也可以推论，如果这个uENV越松，就是范围越大，那么MINDIST这个下界也会越松。

6.2 Approximate search

近似搜索算法还是遵循了iSAX的思想，采用一个优先级队列，按照和Q的MINDIST进行排序，internal node直接入队两个孩子，叶子节点则要对涵盖的每一个真实uENV(subsequence)进行读取，然后计算ED，更新KNN。注意这一步，一个uENV会涵盖至少 $\gamma$ 个备选子序列，也会计算 $\gamma$ 次ED。
从上面的来看，其实算的是精确结果，为什么说是近似呢，源于它的终止条件。这个算法并不会遍历所有的叶子节点，当从队列中出队一个叶子节点，经计算后，knn没有任何更新时，便认为没有继续的必要，提前终止了，这就造成了不准确。

6.3 Exact search

上述的近似算法如果通过修改终止条件来变成精确算法，但是会造成大量的随机IO读，性能会很差。
这时候就用到了之前说的在内存中存储的所有uENV。精确算法首先用近似算法给出一组KNN，这个KNN已经是一个很紧的上界了，之后遍历这个内存中的uENV list，同样的上界剪枝法，对于没有被prun掉的，还是和近似算法一样，磁盘读出序列，分别计算ED。由于内存中的uENV list其实也是排序过的，所以IO代价有所缓解。

7. EXPERIMENTAL EVALUATION

作者用到的真实数据集有两个，都是100M个series，每个长度256。
合成数据集用的高斯分布。

7.1 Envelope Building

首先就是索引建立的时间。一个重要的参数还是 $\gamma$ ，它决定了有多少个uENV产生（反比），也决定了每个uENV产生的时候的时间代价（正比）。

image.png

从实验结果一来看，索引真正建立，执行的时间占比非常低，而且主要与 $\gamma$ ，或者说生成的uENV个数成正比；主要占用时长比较高的是计算uENV的时间。从图一能看出来，稍稍提升下 $\gamma$ 占据query range的比例，时间就会收敛下来。

从实验结果二来看，不断提升的query range对uENV的计算影响很大，文中说是线性影响，但是从图中来看，至少是平方级别的上升，range超过300的时候，构建实现超过5000s（1.5h）左右，比较缓慢了。

7.2 Exact Search Similarity Queries

改变 $\gamma$

可以非常明显看出 $\gamma$ 增大非常有利于查询速度，有些反直觉的是 $\gamma$ 增大导致uENV包含的范围更宽会导致剪枝率降低，然而具体实验中发现，如果 $\gamma$ 太小，那么index中的uENV太多了，基数要比 $\gamma$ 大的时候多很多，又拖慢了查询速度。所以 $\gamma$ 要设置偏大些，而且大的 $\gamma$ 还会使得索引大小明显变小。
ps：作者这里还对Cmri对每种查询长度都建立索引的方法Diss了一下，认为它没有扩展性。

image.png

2018ICDE-ULISSE:ULtra compact In

编者的总结

编者的思考

Abstract

1. Introduction

2. Related Work

3. Preliminaries

4. Proposed Approach

A. Representing Multiple Subsequences

B. PAA Envelope

C. PAA Envelope for Z-Normalized subsequence

4. Indexing the Envelopes

5. INDEXING ALGORITHM

5.1 Non Z-Normalized Subsequences

5.2 Z-Normalized Subsequences

5.3 Building the index

5.3.1 Space complexity analysis

6. SIMILARITY SEARCH WITH ULISSE

6.1 Lower Bounding Euclidean Distance

6.2 Approximate search

6.3 Exact search

7. EXPERIMENTAL EVALUATION

7.1 Envelope Building

7.2 Exact Search Similarity Queries

改变 $\gamma$

改变序列长度

猜你喜欢

热点阅读