近似最近傍探索のためのハードウェア指向Locality-Sensitive HashingアルゴリズムとそのFPGAアーキテクチャに関する研究
定久 紀基
2015 年度 卒 ／修士（工学）
修士論文の概要
近年、情報爆発という言葉に現れるようにインターネット上のデータが爆発的に増加している。それを処理するデータセンタにはより多くのデータを処理するため分散化を行い処理能力の向上を図っている。しかし、分散処理の弊害として導入コストの増加や消費電力の増加といった問題を抱えてしまった。そのため、データセンタを構成するサーバーのスループット、レイテンシの改善が求められている。
ソフトウェアの領域では、大量のデータから価値を創出するデータマイニングの分野において、データセンタへの負荷の少ないアルゴリズムの創出が進められている。近年では大量のデータを処理するため機械学習を用いた方法や、正確性を犠牲にして高速にデータを処理する近似アルゴリズムの研究が盛んになっている。一方ハードウェアの領域では、従来汎用プロセッサによって行われていた処理をFPGAによる専用ハードウェアで処理を行うことによって、高速化する研究が盛んである。例として、Microsoftによる検索エンジンBingのFPGA実装、XilinxによるデータベースのFPGAアクセラレータなどが挙げられる。
本研究はそうした2つの流れを汲み、データマイニングで用いられるアルゴリズムをFPGAに実装することにより、データセンタで行われる処理を高速化することを主題とした。その対象として情報検索に着目した。情報検索の分野では、使われる殆どのアルゴリズムで演算時間が検索対象の数に比例することがわかっている。そのため、演算時間がデータの数に依存しない仕組みが求められている。その結果創出されたのが、Locality-Sensitive Hashing（LSH）であり、1990年代に発表されてから現在まで研究が進められている。本研究はこれらの背景を元に今後重要になるLSHをFPGAに実装した。