文献

J-GLOBAL ID：201002255899261497   整理番号：10A1156383

Resizable-LSHによる閾値可変の近似的類似検索手法の高速化

Speed-Up of Resizable-LSH for Similarity-Based Range Query

著者 (3件)： 山崎邦弘 (早稲田大 大学院基幹理工学研究科) ,  山名早人 (早稲田大 理工学術院) ,  山名早人 (国立情報学研)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2010  号： 3  ページ： ROMBUNNO.AL-131,NO.5  発行年： 2010年10月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,筆者らがこれまでに提案しているResizable-LSHを改善し,広域な閾値に対しても類似検索を可能にする手法を提案する。近年,類似度の尺度として距離を用いた高速な類似検索手法の1つとして,Locality-Sensitive Hashing(局所性鋭敏型ハッシング,以下LSH)による近似的な類似検索が注目されている。LSHとは「距離が近い入力同士は高い確率で衝突する」特徴を持つハッシュ関数を用いたデータマッピング手法である。しかし事前計算の際に類似度の閾値を固定とすることで高速化しているため,エンドユーザが閾値を変更しながら類似検索をすることはできない。そこでResizable-LSHではハッシュ値が近いデータも検索することで,閾値を可変とした類似検索を実現しているが,閾値が大きくなると検索量も膨大になるため,速度低下を招いていた。本稿ではResizable-LSHのハッシュ値検索方式を変更してハッシュ値探索とデータ探索を同時に行う手法を提案する。本手法により,従来のResizable-LSHと比較して800倍以上の速度向上を達成し,広域な閾値を設定した場合でも高速な類似検索を実現する。(著者抄録)

シソーラス用語： *情報検索 ,  閾値 ,  可変性 ,  度 ,  類似性 ,  高速アルゴリズム ,  *ハッシング ,  *確率モデル ,  ハッシュ関数 ,  葛藤 ,  *探索問題
準シソーラス用語： *LSH ,  コンフリクト ,  *類似検索 ,  類似度

分類 (4件)： 検索技術  (AC06020S) ,  システムプログラミング一般  (JD03010Y) ,  システム・制御理論一般  (IA02010H) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (6件)： 閾値 ,  可変 ,  近似 ,  類似検索 ,  手法 ,  高速化