論文原文: The Case for Learned Index Structures

Morning Paper Reading: part1, par2

緣起:

剛好最近有幾次機會可以去工研院開會的路上,在高鐵的路途上可以好好的來欣賞這篇文章. 這篇文章是由 Google Brain 的大神 Jeff Dean 連署的論文之一.講的是透過 NN 的方式來讓大家熟知的 B-Tree, Hashing table 甚至是 Bloom Filter 更有效率…

2018 年第一篇好好閱讀的論文,當然要獻給有深度而且相當有趣的這篇文章.The Case for Learned Index Structures .主要的原因有以下:

Jeff Dean 是誰? 快來看他的 Quorahttps://www.quora.com/What-are-all-the-Jeff-Dean-facts

- 他看得懂, 也寫 Binary code - 他的 PIN code 是 Pi 末四碼

先講講 B-Tree

B-Tree 是大家相當熟知的資料結構,在此僅列出幾個需要知道的.

  • 時間複雜度 \(O(log n)\) (Balanced B-Tree)
  • 需要空間(cache) 代表存多少資訊在 B-Tree .當資料不在 cache 中,代表需要重新跑一次 re-balanced
  • B-Tree traversal 無法分散式處理 (透過 GPU 來加速)

再來談 Learning Index Tree

回過來講 B-Tree Index 你可以把一個數值輸入 B-Tree ,透過搜尋過後可以傳回一個 Index (可能有 re-balanced).

換個角度,如過透過 NN (Neural Networking) model 的學習將一個數值輸入後,來預測 (predict) 它可能的索引位置 (index) .那麼我們就稱這個為 Learned Index

這邊有一些你需要知道關於 Learned Index 的部分:

  • 由於直接運算,所以時間複雜度相當的低: \(O(1)\)
  • 由於透過 NN 來運算,可以很輕易透過 GPU 來加速運算
  • 空間要求相當的少
    • 不像 B-Tree Index 需要一定的空間來儲存目前已知的數值來加速. (根據文章: cache size 128 是最快的)

關於 CDF (Cumulative Distribution Function)

B-Tree 就可以當成是一個透過 Key 值來轉換到 Index (Pos)的方式. 那麼也可以當成是透過 Key 的分佈來預測 (predict) 位置. \(p = F(Key) ∗ N\)

Tensorflow 來做 CDF 與傳統 B-Tree Index 的效能比對

  • 來源資料: 200M 筆的 Web Log
  • Activation fnction: ReLu
  • 32 個 Neural per layer

透過 Tensorflow 來實作為 Naive Learning Index 與 B-Tree 的效能比對. B-Tree 快上 2~3 倍,論文提出以下理由:

  • Tensorflow 設計是為了處理大量的數據,對於 200M (相對小) 他本身的處理效率有相對的消耗
  • B-Tree 的結果會 overfit 也就是說完全以輸入的資料來作為 B-Tree 的計算與樹狀的建置. 但是相反的 CDF 是透過 NN 來計算”可能性”的位置.
  • B-Tree 需要比較大的 Cache (比較表內使用 128 的 cache 效能最佳) ,而 CDF 透過 NN 來學習不需要儲存之前的資料.(不過兩者都需要 re-train (CDF) 與 re-balanced(B-Tree) )

參考文章:


Buy Me A Coffee

Evan

Attitude is everything