文献

J-GLOBAL ID：200902270003926949   整理番号：09A1037902

Resizable-LSH:可変領域型の近似的類似検索

Resizable-LSH: An Approximate Similarity Search Algorithm for Resizable Range-Search

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

抄録/ポイント： 本稿では閾値を可変にした近似的な類似検索手法を提案する。近年,距離を用いた類似検索手法の1つとして,Locality-Sensitive Hashing(局所性鋭敏型ハッシング,LSH)による近似的な類似検索が注目されている。LSHは,「距離が近い入力同士は高い確率で衝突する」特徴を持つハッシュ関数を用いたデータマッピング手法であり,高次元なデータに対しても高速に近傍検索を行うことができる。しかしLSHでは,事前計算によって距離が近いデータ同士を同じハッシュ値にマッピングするため,検索時に類似度の閾値を変更することができない。閾値を変更するにはハッシュテーブルの再構築が必要になるため,ユーザが閾値を指定できるような類似検索は実現困難である。そこで本研究では,類似検索時に,クエリとハッシュ値が一致するデータに加え,ハッシュ値が近いデータも取得することで,ハッシュテーブルの再構築を行うことなく,閾値を指定できる類似検索を実現した。提案手法は,閾値に合わせてハッシュテーブルを逐次再構築するLSHと比較して,同程度の精度で,かつ1,000倍程度の高速化を達成できることを実験により確認した。(著者抄録)

シソーラス用語： *情報検索 ,  *ハッシング ,  距離 ,  確率モデル ,  ハッシュ関数 ,  高次元 ,  閾値 ,  データ更新 ,  質問 ,  表 ,  精度 ,  効率化 ,  性能評価
準シソーラス用語： *類似検索 ,  クエリー ,  ハッシュテーブル

分類 (2件)： 検索技術  (AC06020S) ,  システムプログラミング一般  (JD03010Y)

タイトルに関連する用語 (3件)： 可変領域 ,  近似 ,  類似検索