標(biāo)題：大時(shí)間序列數(shù)據(jù)的分布式索引框架

編者的總結(jié)

1. 本文針對(duì)分布式環(huán)境，做time series的whole-matching，基本上只做了近似情況下，是對(duì)2017DPiSAX，幾乎做了全面的優(yōu)化，無論從分析上還是從結(jié)果上來看，幾乎都是完全的outperform的。
2. 本文最突出的亮點(diǎn)是一顆compact的iSAX樹，這顆樹深度很小，足夠緊湊，最重要的是，葉子節(jié)點(diǎn)中的序列之間的proximity，得到了很好的維護(hù)，因此，顯著提升了approximate KNN的結(jié)果質(zhì)量，實(shí)驗(yàn)中召回率在30%-60%之間，也證實(shí)了這一點(diǎn)。

編者的思考

1. 本文對(duì)Exact query的定義過于另類（距離為0），實(shí)際價(jià)值也不大，對(duì)于exact knn的搜索，還是一個(gè)問題。
2. 本文核心思路和DPiSAX還是很像的，通過sample分割dataset去幾個(gè)disjoint的partition，建立global index和local index兩級(jí)threshold。這種思路的一個(gè)問題就是單查詢幾乎毫無裨益，對(duì)吞吐量的幫助倒是很大。
3. 還有一個(gè)問題就是近似準(zhǔn)確度的問題，召回率不太穩(wěn)定，也沒有保證。

ABSTRACT

首先提到iSAX的擴(kuò)展性一般，扇出太小，通常是二叉的，導(dǎo)致樹很深，不利于延展。
另外一點(diǎn)是這個(gè)character-level的分割會(huì)導(dǎo)致葉子節(jié)點(diǎn)里的series之間的proximity很差，極大的影響了KNN的質(zhì)量。
本文提出的TARDIS也是iSAX-based index tree，但是解決了上述問題，可以做精確和近似的KNN。TARDIS是word-level進(jìn)行分層的，支持壓縮的結(jié)構(gòu)，高效搜索和比較，相似關(guān)系也得到了很好的保留。
本文的索引可以支持G級(jí)別的time series個(gè)數(shù)。實(shí)驗(yàn)中，在速度、空間和質(zhì)量上都得到了較大提升。

I. INTRODUCTION

首先說SOTA的方法，既沒有準(zhǔn)確性，也沒有擴(kuò)展性。
iSAX系列的都是中心化方法；一些TSDBMS主要用的是數(shù)學(xué)模型；DPiSAX和本文最為類似，但是中間節(jié)點(diǎn)太多了，樹太深了，另一方面bit太多，比較太耗時(shí)。
本文提出的就是變長(zhǎng)的word-level的基數(shù)，word-level更適合并行處理

II. PRELIMINARIES

exact query定義的比較奇怪，要求找到與query time series ED距離為0的所有序列。

近似是用error rate來定義的

image.png

iSAX的缺陷：

1. 樹的層數(shù)太深，查詢的時(shí)候每層至少查一個(gè)；
2. 初始為每個(gè)時(shí)間序列留出了足夠大的基數(shù)，這造成了冗余計(jì)算；

3. 基數(shù)不同進(jìn)行歸檔(character-level)，導(dǎo)致了同一leaf node里面的ts，相似性沒那么好，假陽性和假陰性都大量存在，導(dǎo)致了近似結(jié)果較差，如下圖。

   
   
   image.png

DPiSAX的缺陷：

1. 繼承了iSAX的所有缺陷；
2. 缺失了refine的階段導(dǎo)致了精度退化（？）。

III. TARDIS BUILDING-BLOCK STRUCTURES

A. iSAX-Transposition Signature (iSAX-T)

首先是word-level，表示樹的每一層，每個(gè)word的基數(shù)都是一樣的；另外是transpositition，如下圖，先轉(zhuǎn)置然后取16進(jìn)制。這樣表示之后，對(duì)基數(shù)進(jìn)行降級(jí)就可以很方便的刪去右面的幾位。

image.png

image.png

其實(shí)從數(shù)字上來看，就是把每個(gè)word的頭一位拿出來拼起來做十六進(jìn)制第一位，其他位也是一樣。

B. iSAX-T K-ary Tree (sigTree)

image.png

sigTree的好處有幾個(gè)：

• 深度肯定降下來了；
• word-level相似性肯定強(qiáng)了；
• word轉(zhuǎn)換很快（transposition）。

IV. TARDIS INDEXINGSTRUCTURE

A. TARDIS Overview

主要流程就是下圖，一個(gè)TARDIS-G，一個(gè)TARDIS-L，在TARDIS-G查好partition，再去TARDIS-L具體找序列。

image.png

給一個(gè)初始基數(shù)，兩種index的分裂threshold，一個(gè)word-length，就可以開始構(gòu)造索引了。

B. TARDIS Global Index (Tardis-G)

數(shù)據(jù)集以block-level進(jìn)行采樣，以一個(gè)初始基數(shù)得到一個(gè)(isaxt(b), freq:1)，然后按照isaxt(b)進(jìn)行reduce，得到(isaxt(b), freq(b)).

接下來，算法會(huì)依次對(duì)每個(gè)layer進(jìn)行迭代，注意layer就等于iSAX word的基數(shù)，迭代過程，就是逐漸將基數(shù)+1.

不失一般性，我們以第一層為例，把isaxt(b) map成isaxt(1)，對(duì)于isaxt(1)再Reduce sum一次，我們就得到了TARDIS-G第一層各個(gè)節(jié)點(diǎn)，以及每個(gè)節(jié)點(diǎn)的頻數(shù)；之后我們篩出來頻數(shù)超過th的，它們是需要繼續(xù)分裂的節(jié)點(diǎn)，不需要分裂的，自動(dòng)成為葉子節(jié)點(diǎn)。
接下來就是第二層，把之前需要分裂的節(jié)點(diǎn)中的序列的isaxt(b),freq(b)拿出來，再map 成isaxt(2)，再Reduce成freq(2)，得到TARDIS-G第二層節(jié)點(diǎn)，后續(xù)依次類推。

構(gòu)建好樹之后的問題就是給他們分配partition，規(guī)定只有兄弟葉子節(jié)點(diǎn)才能在一個(gè)partition，一個(gè)葉子節(jié)點(diǎn)只能在一個(gè)partition。那么問題就可以抽象成，給定一組兄弟葉子節(jié)點(diǎn)，和一個(gè)partition的capacity C，如何分配盡量少的partition，裝載這些葉子節(jié)點(diǎn)。類似變形的背包問題。
采用的方法是個(gè)貪心，F(xiàn)irst-fit策略。
葉子節(jié)點(diǎn)的partition也要向上讓它的祖先知道，得到歸納。

C. TARDIS Local Index (Tardis-L)

首先是廣播TARDIS-G，按照這個(gè)索引進(jìn)行分partition。然后是對(duì)partition內(nèi)部的構(gòu)建，內(nèi)部主要用插入的方法來構(gòu)建，滿了就分裂出來至多個(gè)孩子，然后重新平衡。

為了支持快速的精確查找，使用了bloom filter布隆過濾器，以確定某個(gè)元素是否在某個(gè)集合內(nèi)，可能出現(xiàn)假陽性，但不會(huì)出現(xiàn)假陰性。bloom filter在插入索引的時(shí)候把isaxt(b)插進(jìn)去就行。

V. TARDIS QUERYPROCESSING

A. Exact Match Query

由于本文exact query的特殊定義，只需要通過TARDIS-G找到對(duì)應(yīng)的partition，再查下bloom filter，如果陽性，就去走下TARDIS-L，以判斷是否存在即可。

B. kNN Approximate Query

樸素的方法是通過TARDIS-G定位到partition，沿著根節(jié)點(diǎn)往下找，知道找到一個(gè)最低的且freq大于k的節(jié)點(diǎn)，把它里面的全都load出來，計(jì)算KNN。

精確度再高點(diǎn)，把整個(gè)節(jié)點(diǎn)的load出來，利用上一個(gè)方法的KNN做lower bound剪枝。

精確度再高點(diǎn)，把該partition的兄弟節(jié)點(diǎn)的partition都如此并行處理，最后按照距離歸并排序就可以了。為了避免選出來太多partition，用一個(gè)pth作為threshold，超過了的話，就隨機(jī)抽。

VI. EXPERIMENT

召回率和error rate提升比較明顯，average query time基本持平

image.png

local index size有一定壓縮。

image.png

image.png