動的に変わる集合に対する類似検索のスケッチを利用した高速化

点击翻译按钮获取中文摘要

昨年度に提案した動的に変化する集合を対象とするスケッチ更新アルゴリズムの空間計算量の削減に取り組んだ。本アルゴリズムでは、Min-Hashというハッシュ関数を利用してスケッチを作成する。ハッシュ値算出には(1)ハッシュ値割り当て表と(2)集合のヒストグラムが必要になるが、前者については表サイズを小さくする既存手法を採り入れて空間計算量の大幅な削減に成功した。一方で、後者についてはヒストグラムの空間計算量を大幅に減らすと集合からどの要素がいつ離脱するかという情報を保持できないため、スケッチの精度が下がるという問題が発生した。このため、後者については空間計算量を30パーセント程度削減するに留まった。動的に変化する集合に対して、省メモリで精度の高いヒストグラムを生成する手法が必要になっており、2023年度はこの条件を満たすヒストグラム生成法についても研究を進める。一方、応用研究としては動的に変化するテキスト集合をクエリとする範囲類似検索 (Range Search)についても研究した。ここで動的に変化するテキスト集合とは、具体的には特定ユーザによるSNSへの投稿を指しており、類似検索により投稿内容が似た類似ユーザを探すことを目指している。本問題に対して転置インデクスを用いた高速解法を考案した。とくに提案手法では転置インデクスをクエリに対してのみ持たせることで、転置インデクスの管理オーバーヘッドを増やさずに高速処理を実現した。この他に、株価時系列を終値の集合と見なして類似検索ベースの株価予測にも取り組んだ。ここでは過去の類似時系列を検索して、過去の事例から株価の上昇/下落を予測する。そして、予測対象銘柄以外の他社データも過去の事例に加えた方が、予測精度が向上するという興味深い結果を得た。