大学生が40年間信じられてきたデータサイエンスの定説を覆した (3/3)

専門家向け補遺

この論文の価値は、「少し速いハッシュテーブルを1本出した」ことではありません。

著者らがやっているのは、並べ替えなしの open addressing の理論地図を、上界と下界の両方から描き直したことです。

論文の導入で立てられている問いは二つで、ひとつは「並べ替えなしで、平均的な探索手数を一様探索の達成する対数オーダーより下げられるか」、もうひとつは「並べ替えなしで、最悪ケースの期待探索手数を一様探索の達成する逆数オーダーより下げられるか」です。

著者らはまず、この二つの問いに同時に「できる」と答える非貪欲な構成――elastic hashing――を与えています。

ここで重要なのは、要素をあとで動かさないまま、しかも最初の空きに即決しないことで、挿入時に試した棚の数と、あとでその要素を取り出すときに試される棚の数を切り離している点です。

論文中でも、先の候補をかなり遠くまで見てから、最終的には手前の適切な位置に“戻る”振る舞いが本質だと説明されています。

その結果、表の中にすでに入っている要素に対する amortized expected probe complexity は定数、worst-case expected probe complexity は対数オーダー、worst-case expected insertion time も対数オーダーまで落ちます。

しかも著者らは、この worst-case expected の対数オーダーが、並べ替えなしの任意のスキーム（greedy か否かを問わず）における下界とちょうど一致することを示し、この意味で Theorem 1 が最適であることまで証明しています。

二つ目が funnel hashing です。

こちらはとくに意味が大きい結果です。

というのも、ヤオの未解決予想が刺さっていたのは、まさに greedy open addressing の側だからです。

ここで一点、誤解されやすいので補足しておくと、Yao が1985年の論文『Uniform Hashing is Optimal』で証明したのは、Ullman が1972年に立てた amortized expected に関する予想の方で、Yao 自身が予想として残したのは、それより一段強い worst-case expected についての下界でした。

今回の論文が覆したのは、この後者――Yao が未解決問題として残した方の予想です。

論文は、greedy のままでも worst-case expected probe complexity を対数の二乗オーダーまで落とせると示します。

これは、長く「最悪ケースの期待探索手数についてはほぼ逆数オーダーが限界ではないか」と見られていた世界に対する、はっきりした反例です。要するにこの論文は、「非貪欲なら逃げ道がある」だけでなく、「greedy の土俵の中でも、思っていたほど悪くはならない」と言っているわけです。

ここが、単なる設計改良ではなく、古典予想の否定として重いところです。

さらに大事なのは、この論文が上界だけの論文ではないことです。elastic hashing 側では、先に述べた通り、並べ替えなし一般の worst-case expected probe complexity に対して対数オーダーの下界を与えています。

funnel hashing 側では、greedy に対して対数の二乗オーダーの matching lower bound を与えています。

加えて、高確率の最悪 probe complexity についても、並べ替えなし一般で対数の二乗に log log n が加わる形の下界を示しています。

ここで特筆すべきは、この最後の下界が greedy に限らず、non-greedy な並べ替えなしスキームにまで及ぶという点です。

つまり funnel hashing の達成した対数の二乗オーダーは、greedy の枠を超えた意味でも本質的な限界の一部を成しているということです。

著者らは「ここまで速くできる」を言ったあとで、「しかもそこが本質的な限界だ」と押さえている。

理論論文としての完成度は、むしろここで決まっています。

ただ当然ながら限界もあります。

まず、amortized probe complexity は表の中に存在する要素に対する量であり、存在しないキーへの negative query と同じ意味ではありません。

negative query について論文が直接きれいに触れているのは greedy 側で、greedy アルゴリズム一般では存在しないキーへの問い合わせ時間が挿入時間と等しくなるため、Theorem 2 の挿入時間に関する保証は、そのまま存在しないキーへの問い合わせ時間に対する保証にも延長できます。

一方で、削除を含む無限時間の設定は別問題で、論文自身も、先行研究で示された下界（この設定での amortized expected probe complexity が δ⁻Ω(1) 以上になる）を引いて、Theorem 1 や Theorem 2 の型の結果は原理的に成立しないと述べています。

ここを落とすと、「ハッシュテーブル一般の最終回答が出た」という誤読が起きやすいので注意が必要です。

最後に、論文の本当の見どころを一文で言えば、ボトルネックは“高負荷そのもの”ではなく、“挿入時に見た候補列と、後の検索コストが直結してしまうこと”だったと示した点にあります（少なくともこのモデルでは、ボトルネックを『高負荷そのもの』だけで語るのでは足りず、挿入時の probe と後の search probe complexity の結びつきが重要だったことを示唆しています）。

著者らは導入部で、uniform probing が抱える coupon-collector bottleneck を、non-greedy な設計でどう迂回するかをかなり意識的に説明しています。

だからこの論文は、「古い予想を壊した話」であると同時に、「open addressing における本当の難所は何か」を言い直した論文でもあります。

そのため重要なのは結果そのものに加えて、reordering の必要性と non-greediness の必要性を切り分けたこと、そして greedy と non-greedy の境界を、定量的なかたちで再定義したことにあるはずです。