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で、グラフとコードが少し増えているので、こちらも読むと理解しやすいかもしれません。