抄録
Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業 基盤研究(C), Category: 基盤研究(C), Fund Type: -, Overall Grant Amount: - (direct: 2700000, indirect: 810000)
本研究課題はデータストリームを対象とする類似検索を取り扱う。その具体的な応用としては、嗜好性が似たユーザの発見が挙げられる。例えば、閲覧したウェブニュース記事の集合が互いに似た2ユーザは、興味がある事柄が似ており、嗜好性が似ていると言える。このようにして、類似ユーザ検索を集合間類似検索に帰着できる。
要素が固定した通常の集合に対しては、Min Hashというハッシュ関数を利用して集合の要約(スケッチ）を事前生成し、スケッチ間で軽量に類似度計算することで、類似検索を高速化できる。しかし、ストリーム環境では新しい要素の追加と古い要素の消滅が起きるため、スケッチを高速更新する必要がある。そこで本研究では、ストリーム環境で集合の要素が入れ替わる状況で、Min Hashを高速計算するアルゴリズムの開発に取り組んだ。
そして2021年度は、多重集合を取り扱えなかったDatarらの既存手法を、多重集合が取り扱えるよう拡張することに成功した。ここで、多重集合とは同じラベルの要素を複数持てる集合のことである。Min Hashは集合の各要素に確率的に値を割り当て、その最小値をハッシュ値とする。既存手法では将来的に最小値になりえない要素を削除して、ハッシュ値再計算のオーバーヘッドを削減している。しかし、多重集合の場合、要素への割り当て値が多重度に依存して動的に変わるため将来的に最小値になりえるかの判定が困難になる。我々の提案手法は、この厳しい条件下で、将来的に最小値にならない要素を判別する。さらに同一ラベルの要素を、提案手法が高々１つだけ保持すればよいことも示せた。集合の要素数をWとすると、提案手法の計算時間は実験的にlog Wに比例し、O(W)かかるベースライン手法より圧倒的に高速に動作することを確認できた。