標(biāo)題：對(duì)大量數(shù)據(jù)序列的交互式探索索引
本文于2016年VLDB Journal的ADS: the adaptive data series index屬于同一篇，期刊版本的更為詳細(xì)馏锡，這里二合一做講解救军。

編者的總結(jié)

1. ADS整體體現(xiàn)的就是一個(gè)非物化(non-materialized)的思想在塔，這個(gè)思想在之后也是被廣泛使用的砂碉。
2. ADS-Full實(shí)際上相當(dāng)于提前把SAX表算出來(lái)（速度很快），然后用SAX建樹糠睡，最后統(tǒng)一寫數(shù)據(jù)漓踢。理論上牵署，應(yīng)當(dāng)比isax2.0+要更快一些。

編者的思考

1. ADS+的小葉子threshold竟然在實(shí)驗(yàn)中被設(shè)置為10彭雾，對(duì)于單葉子節(jié)點(diǎn)的近似查詢來(lái)說(shuō)碟刺，會(huì)大大影響召回率、準(zhǔn)確率等薯酝，因此查詢效果是一個(gè)額外需要考慮的點(diǎn)半沽。

ABSTRACT

核心思路就是先把用戶需要query那部分?jǐn)?shù)據(jù)進(jìn)行索引，用不到的先不索引吴菠。

1. INTRODUCTION

image.png

image.png

3. THE ADAPTIVE DATA SERIES INDEX

3.1 The ADS Index

盡量減少索引構(gòu)建過(guò)程的I/O者填，在ADS中，iSAX-Tree中只保留iSAX表示做葵，不會(huì)在葉子節(jié)點(diǎn)保存源數(shù)據(jù)占哟。I/O過(guò)程只在必要的時(shí)候(query中用到了)，才會(huì)真正執(zhí)行酿矢。

3.1.1 Index Creation

image.png

索引構(gòu)建過(guò)程榨乎，只會(huì)順序掃描源數(shù)據(jù)，用以生成iSAX表示瘫筐，把這些iSAX表示和源數(shù)據(jù)指針置于buffer（FBL, First Buffer Layer）蜜暑，直到內(nèi)存滿，然后開始處理策肝，把buffer里的iSAX逐個(gè)插入索引樹肛捍，葉子節(jié)點(diǎn)的iSAX表示各自存入一個(gè)buffer(LBL, Leaf Buffer Layer)隐绵，然后刷入磁盤。之后重復(fù)這個(gè)過(guò)程拙毫。

• 實(shí)際上就是非物化的iSAX索引構(gòu)建依许。

3.1.2 Querying and Re?ning ADS

Query首先要定位到具體的葉子節(jié)點(diǎn)，如果葉子節(jié)點(diǎn)是PARTIAL的缀蹄，那就取出所有的文件指針峭跳，進(jìn)行排序，然后到磁盤里讀出來(lái)袍患，讀到LBL中坦康，如果內(nèi)存滿了竣付，就把LBL中的源數(shù)據(jù)序列诡延，寫到磁盤里，此時(shí)葉子節(jié)點(diǎn)就是FULL狀態(tài)的了古胆。

• 查詢的過(guò)程肆良，實(shí)際上也是逐漸物化的過(guò)程。
  精確查找逸绎，首先是以近似查找來(lái)確定BSF惹恃，然后掃描全部進(jìn)行剪枝。

3.2 The ADS+ Index (Adaptive Leaf Size)

ADS+是ADS的一個(gè)進(jìn)階版本棺牧，正如Intruduction中的第二張圖巫糙，Leaf Size對(duì)構(gòu)建和Query的影響是一個(gè)trade-off，難以兼顧颊乘。因此本文的方案是参淹，提供兩種leaf size，一種大leaf乏悄，用于構(gòu)建浙值；一種小leaf用于query。
query的時(shí)候如果到了一個(gè)大leaf檩小，則要讀出iSAX表示开呐，然后繼續(xù)分裂，直到找到target leaf(小leaf sieze)规求，對(duì)其中的序列讀出筐付，并寫入磁盤，變成FULL狀態(tài)阻肿。同時(shí)瓦戚，對(duì)于非target route上的新生成的leaf node，仍維持其PARTITAL的狀態(tài)冕茅，不必讀取伤极。
以此通過(guò)逐層延緩具體I/O蛹找，提升效率。

image.png

3.3 Partial ADS+ (PADS+)

PADS+進(jìn)一步縮短了DATA-TO-QUERY的時(shí)間哨坪，它只順序讀一遍源數(shù)據(jù)庸疾，計(jì)算iSAX，直接放到第一層的iSAX当编，作為一層FBL届慈，如果內(nèi)存不夠存，就都刷到磁盤上忿偷。qurey的時(shí)候基于這個(gè)很大的FBL進(jìn)行分裂金顿，查詢，target leaf node將最終把數(shù)據(jù)序列讀出鲤桥，計(jì)算距離揍拆，并寫入磁盤。
這種方式尤其適合于只需要少量的近似查詢茶凳，或者workload非常偏斜的情況嫂拴。

3.4 Updates

插入會(huì)在源數(shù)據(jù)上append一條，計(jì)算iSAX贮喧，插入到iSAX-Tree中筒狠，對(duì)于FULL leaf node，要做好標(biāo)記箱沦，方便下次query的時(shí)候做整合辩恼。
刪除只要做出標(biāo)記就可以，之后的insertion會(huì)復(fù)用那些空間谓形。

3.5 Full index construction: ADS-Full

如果一定要一個(gè)物化版本的isax（查詢快）灶伊，ADS-Full就是一個(gè)方法。
方法也很簡(jiǎn)單套耕，首先掃數(shù)據(jù)集生成iSAX表示谁帕，利用這些iSAX表示建成整棵樹，最后將源數(shù)據(jù)插入iSAX樹對(duì)應(yīng)的葉子節(jié)點(diǎn)冯袍，這一步利用LBL匈挖。

4 Exact query answering for ADS+

精確查詢分兩步走：

1. 多線程并行掃內(nèi)存SAX表，算出一個(gè)MINDIST表康愤；

2. 由于SAX/MINDIST表在偏移量上和數(shù)據(jù)表是對(duì)齊的儡循，因此從前到后順序掃一遍源數(shù)據(jù)表，MINDIST滿足條件的就讀出來(lái)計(jì)算真實(shí)距離征冷。

   
   
   image.png

作者在文中稱這種磁盤讀的方式為skip sequential read/ sequential reads择膝。
然而實(shí)際上，這種方式相比于隨機(jī)讀取检激，是否真的有速度提升肴捉？或者說(shuō)在物理磁盤上腹侣，這種方式真的是順序的么？編者對(duì)此持懷疑態(tài)度齿穗。

6. EXPERIMENTAL EVALUATION

比較對(duì)象主要是iSAX2.0傲隶，而且為其補(bǔ)充了查詢時(shí)的LRU buffer。
Interl Xeon machine with 64 GB內(nèi)存窃页， 4x 2TB, SATA, 7.2K RPM Hard Drives in RAID0.
算法都是C語(yǔ)言寫的跺株。

6.1 Reducing the data to query time

6.1.1 構(gòu)建時(shí)間

500GB數(shù)據(jù)集Randomwalk。

• 由于IO次數(shù)大幅度減少脖卖，構(gòu)建效率提升了很多倍乒省。

  • 文中一個(gè)例子，20K葉子大小時(shí)畦木，iSAX2.0是8h袖扛，ADS是半小時(shí)，主要就是IO時(shí)間大幅縮減馋劈。

    
    
    image.png

6.1.2 data-to-query time

• 構(gòu)建時(shí)間的縮短是以查詢時(shí)間變慢為代價(jià)的攻锰，因?yàn)樾枰诓樵儠r(shí)不斷物化晾嘶，因此ADS的查詢時(shí)間是比較夸張的妓雾，相比于已經(jīng)物化過(guò)的iSAX2.0.

• 好在構(gòu)建時(shí)間是很短的，可以很快開始查詢來(lái)彌補(bǔ)這一不足垒迂。

  
  
  image.png

• 相比于ADS,ADS+的查詢效率有大幅度提升械姻，甚至超過(guò)了物化的iSAX2.0。其原因在于每次取的只是一個(gè)小葉子机断，IO方面要?jiǎng)龠^(guò)iSAX2.0楷拳，但是查詢精確程度方面就要降低一個(gè)檔次，因?yàn)楫吘箼z索的序列數(shù)少了很多吏奸。

  
  
  image.png

6.1.3 Choosing the query-time leaf size

作者實(shí)際去做了各種query欢揖，根據(jù)磁盤頁(yè)利用率最終選擇了10，這樣一個(gè)超小的leaf size奋蔚。雖然磁盤利用率和查詢時(shí)間都很不錯(cuò)她混，但是最重要的查詢精確度將會(huì)大打折扣，這是作者沒(méi)有考慮的問(wèn)題泊碑。

image.png

6.1.4 Data Touched

這張圖從本質(zhì)上揭示出坤按，ADS+查詢速度快，主要是由于其小葉子節(jié)點(diǎn)太小馒过，load的數(shù)據(jù)非常少臭脓。

image.png

6.6 Fast full index construction

• 這里的iSAX2.0實(shí)驗(yàn)比原版實(shí)驗(yàn)快了非常多（500M，100h）腹忽，有可能是機(jī)器的性能不同来累，這里持懷疑態(tài)度砚作。

• 因此這也無(wú)法與iSAX2+進(jìn)行比較。

  
  
  image.png

6.7 Efficient exact query answering using SIMS

在這里嘹锁，作者說(shuō)ADS+（SIMS精確查詢算法）在大數(shù)據(jù)集上偎巢，剪枝主要發(fā)生在磁盤頁(yè)的層面上。而一頁(yè)又不止一個(gè)序列兼耀，因此浪費(fèi)了大量的時(shí)間在讀取無(wú)用的序列上压昼。

• 左圖是構(gòu)建時(shí)長(zhǎng)，右圖是精確查詢時(shí)長(zhǎng)瘤运。

  
  
  image.png