Read NEW ELITE

ニューエリート グーグル流・新しい価値を生み出し世界を変える人たちという本を読んでみました。結論から言うと、ちょっと微妙かな...という感想です。色んな会社や起業家の例を出し過ぎて、話が発散しているように思います。読み終わって結局この本が1番伝えたかったのかは何だったんだろうと、若干もやもやっとしてしまいました。要所要所でこれは参考になりそうという部分はもちろんあります。
 個人的にはターゲットとなる読者の層はマネージャー以上やHRの方々な印象を受けたので、そういった方々が読んでみると全く違う感想を持たれるんだろうなぁと。

Read Learned Indexes Paper

今更ながらA Machine Learning Approach to Databases Indexesを読んでみました。論文の中身はデータベースのインデックス(索引)に機械学習を適用してみようというものです。
インデックスの種類は大きく3つに分けて説明されています。

#1 Range Index
多くのDBで使われているB木との比較がされています。B木がf(key) ➝ posとピンポイントでキーが存在するページの開始位置を表すのに対して、データがあらかじめソートされている前提としてLearned Ranged Indexでは[ˆy − ∆, yˆ + ∆] （∆はmaximum error）の範囲を探しに行くようです。

#2 Point Index

Hash Mapのような1対1のデータ取得についてです。O(1)は改善の余地がないように見えますが、ハッシュが衝突する場合Linked Listを走査するのに時間がかかるので、それを改善するというのが主な狙いのようです。#1で紹介したfをCDF (Cumulative Distribution Function)として、h(x) = mCDF(x)でハッシュを計算します。こうすることで衝突のないハッシュ値を算出しているとのことです。

#3 Existence Index

特定のキーがデータに存在しているかを判断するIndexについてです。Binary Classificationを想定し、1/0のラベルを持ったデータに対してRNN/CNN & Sigmoidで分類し、結果がYesならそのまま、NoならBloom Filterを通してYesへという流れのようです。Bloom FilterがFalse Negativeを起こさないことを活用してるようです。

より詳しい論文がThe Case for Learned Index Structuresで、グラフとコードが少し増えているので、こちらも読むと理解しやすいかもしれません。