Min-hash法の拡張を用いたストリームモデルにおけるベクトルのL0ノルム計算

豊岡 祥

(指導教員:定兼 邦彦 教授/数理情報第2研究室

資料PDF(toyooka.pdf
研究概要

本研究の位置づけ
大規模かつ高速に生じるデータを扱うストリームモデルという計算モデルにおいてベクトルのL0ノルム(非零成分の数)を求めるアルゴリズムを提案した。アルゴリズムはハッシュ関数を用いる乱択近似アルゴリズムであり、ストリーム中の異なるアイテム数を求める、既存手法を拡張することで得られる。
修論の感想

限られた計算領域でも確率的な挙動を許せばアルゴリズムが動作する、という乱択アルゴリズムの面白さに惹かれて初めた研究だったが、実際やってみると既存研究のように綺麗なアルゴリズムを提案するのは難しかった。なんとか形にまとめることができてよかった。


>
ISTyくん