巨大データベースの検索を高速化する新手法――機械学習を用いてハッシュ関数を設計

Credits:Image: Christine Daniloff, MIT

機械学習を用いて、巨大データベースのデータ検索に重要なハッシュ関数をより高速かつ効率的に構築する新しい方法が開発された。この研究は米マサチューセッツ工科大学（MIT）を中心にした研究チームによるもので、その詳細はカナダで2023年8月28日〜9月1日に行われるデータベース工学分野の国際会議「International Conference on Very Large Databases（VLDB） 2023」で発表される予定だ。

ハッシュ法（ハッシュ探索）は、データベースのインデックス作成からデータ圧縮、暗号化まで、非常に多くの用途で使用されている。また、蔵書目録や電子商取引サイトなど、ほとんどのオンラインデータベースで中核となる操作となっている。そのため、高速で効率的なハッシュ関数は非常に重要だ。

ハッシュ関数は、データが保存される場所を直接決定するコードを生成することで、データ検索を容易にする。しかし、従来のハッシュ関数はコードをランダムに生成するため、異なる2つのデータが同じ値でハッシュ化されることがある。その結果、ある項目を検索すると、同じハッシュ値を持つ複数のデータが該当するという衝突が起こる。正しいデータを見つけるためにより長い時間がかかるため、検索が遅くなりパフォーマンスが低下してしまう。

一方、完全ハッシュ関数と呼ばれるタイプのハッシュ関数は、衝突が発生しないようにデータを配置するよう設計されている。しかし、データセットごとに構築するには時間がかかり、従来のハッシュ関数よりも計算時間が長くなってしまう。

そこで、研究チームは、機械学習を用いてより優れたハッシュ関数を構築できるかを調べた。研究チームは、もしデータが特定の分布から来るものだと分かっていれば、学習済みモデルを使って衝突が少ないハッシュ関数を作ることができるのではないかと考えた。データ分布は、データセットに含まれるすべての可能な値と、各値の出現頻度を示す。

研究チームは、データセットから小さなサンプルを取り出し、機械学習を用いてデータがどのように広がっているか、そのデータ分布の形を近似した。学習したモデルは、その近似値を用いてデータセット内のキーの位置を予測する。

その結果、データが予測可能な形で分布している場合は、学習済みモデルは従来のハッシュ関数よりも衝突を少なくすることができた。具体的には、データセット内で衝突するキーの割合を30％から半分の15％に減らすことができた。また、完全ハッシュ関数よりも構築しやすく実行も速いことが分かった。最良のケースでは、学習済みモデルは実行時間を30％近く短縮した。

ただし、データ点間のギャップがあまりにも大きく変化するため、データが予測可能な形で分布していない場合は、学習済みモデルを使用すると衝突が多くなる可能性がある。

この技術は、例えば科学者がDNAやアミノ酸配列、その他の生物学的情報の保存と分析に使用する計算システムを加速させる可能性があるという。

巨大データベースの検索を高速化する新手法――機械学習を用いてハッシュ関数を設計