標(biāo)題：時(shí)間序列挖掘到的并行化和分布式的未來
本文是時(shí)間序列大佬Themis Palpanas在2017年HPCS上做的一篇tech report。2017年發(fā)布了DPiSAX，之后2018-2020三年，涌現(xiàn)了近十篇time series similarity search的分布式并行算法。除了Palpanas的實(shí)驗(yàn)室以外，還有伍斯特理工學(xué)院的課題組提供的TARDIS方案2019、Chainlink方案2020等。
ABSTARCT
時(shí)間序列大數(shù)據(jù)集兩個(gè)瓶頸，一個(gè)是索引構(gòu)建time，另一個(gè)是query answer time。我們的方案是邊建索引邊查詢（correct answer），證明了不這樣做在大數(shù)據(jù)集上是不可行的。實(shí)驗(yàn)中首次（？）用了1G個(gè)序列。同時(shí)闡明未來應(yīng)該聚焦于分布式環(huán)境和并行算法。
I. INTRODUCTION
數(shù)據(jù)序列：一個(gè)數(shù)據(jù)向量，每個(gè)元素由一個(gè)時(shí)間點(diǎn)+一個(gè)值來構(gòu)成。如果某個(gè)維度可以證實(shí)序列是以時(shí)間為排序手段的話，這就是時(shí)間序列。類似的，角度、質(zhì)量、位置都可以成為那個(gè)特定的維度。
數(shù)據(jù)序列通常被作為一個(gè)個(gè)體進(jìn)行分析，而不是一組點(diǎn)。然而傳統(tǒng)高維處理手段不太可用，原因主要是維度太高和嚴(yán)格的順序性。
數(shù)據(jù)序列的query分成兩種類型，一種是SPT(selection-projection-trasformation)，select一些序列出來，做簡單列選擇（比如前10個(gè)，或者某些屬性，點(diǎn)位置等），最后做一些數(shù)學(xué)變換（平均值等）。
另一種是DM（data-mining），會(huì)將整個(gè)序列當(dāng)做一個(gè)單一的對象。會(huì)根據(jù)內(nèi)容查詢（范圍搜索，相似性搜索，KNN），聚類，分類，異常模式，頻繁子序列。這些是現(xiàn)有的DBMS無法滿足的。
這其中最重要的就是similarity search，現(xiàn)有的技術(shù)就是summarization和index。
作者認(rèn)為，目前的技術(shù)對于單機(jī)節(jié)點(diǎn)的計(jì)算能力已接近極限，而數(shù)據(jù)量和需求還在不斷加大，所以應(yīng)轉(zhuǎn)向研究分布式和并行算法，以實(shí)現(xiàn)擴(kuò)展能力。SIMD，多核，多線程，GPU也為數(shù)據(jù)序列的某些操作提供并行化的機(jī)會(huì)。
II. THE STATE OF THE ART
Using Existing Data Management Systems.
關(guān)系型，列式，數(shù)組數(shù)據(jù)庫，都不可以滿足ds的分析需求，它們對于ds的描述能力太弱，基于這些DB的解決方案最終可用性和性能不會(huì)太好。Scaling Up.
UCR Suite只能支持單個(gè)長序列時(shí)效果最好。
目前仍存在的一些問題：
- ADS+如何支持精確查詢？
- 精確查找的時(shí)延動(dòng)蕩太大了
-
isax2+ ads+ 如何并行化？
作者對精確查找做了個(gè)對比，效果顯示，ADS+效果是最好的。
image.png
- Scaling Out.
用map reduce的研究很少，gorilla是最近的一個(gè)不錯(cuò)的分布式時(shí)序數(shù)據(jù)庫，有各種優(yōu)良的性質(zhì)，但是尚不支持DM查詢。
III. RESEARCH DIRECTIONS
時(shí)序數(shù)據(jù)的訪問方法無非是scan or index。
壓縮，多核，SIMD，GPU，都可以成為二者的優(yōu)化手段。
壓縮：數(shù)據(jù)可以被精巧的壓縮成輕量級(jí)的，而且距離計(jì)算可以直接在壓縮后的數(shù)據(jù)上進(jìn)行，這樣就節(jié)省了大量的IO傳輸開銷，或許還會(huì)有壓縮-解壓縮的計(jì)算開銷。
目前scan方向的并行化只考慮并行掃描，index方向的只考慮只讀操作。
一個(gè)顯著的問題就是多個(gè)計(jì)算節(jié)點(diǎn)如何能夠及時(shí)通信以達(dá)到剪枝的效果。
最后還有一個(gè)問題，假設(shè)我們有了并行化scan,index,SIMD等等手段，如何根據(jù)查詢和當(dāng)下機(jī)器的配置，進(jìn)行選擇，以達(dá)到最佳效果，也是一個(gè)問題。
除此之外，benchmark也是急需的，壓力測試,query難度分級(jí)。
