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

• Item type: SIG Technical Reports(1)
• 公開日: 2009-07-21
• タイトル: Resizable-LSH：可変領域型の近似的類似検索
• タイトル / 言語: en
• タイトル: Resizable-LSH: An Approximate Similarity Search Algorithm for Resizable Range-Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学大学院基幹理工学研究科修士課程
• 著者所属: 早稲田大学大学院基幹理工学研究科修士課程
• 著者所属: 早稲田大学大学院基幹理工学研究科修士課程
• 著者所属: 早稲田大学理工学術院／国立情報学研究所
• 著者所属(英): en
• 著者所属(英): Master's Course of Graduate School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Master's Course of Graduate School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Master's Course of Graduate School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Waseda University / National Institute of Informatics
• 著者名: 山﨑, 邦弘; 中村, 智浩; 舟橋, 卓也; 山名, 早人
• 著者名(英): Kunihiro, Yamazaki; Tomohiro, Nakamura; Takuya, Funahashi; Hayato, Yamana
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では閾値を可変にした近似的な類似検索手法を提案する．近年，距離を用いた類似検索手法の 1 つとして，Locality-Sensitive Hashing （局所性鋭敏型ハッシング，LSH） による近似的な類似検索が注目されている．LSHは，「距離が近い入力同士は高い確率で衝突する」 特徴を持つハッシュ関数を用いたデータマッピング手法であり，高次元なデータに対しても高速に近傍検索を行うことができる．しかし LSH では，事前計算によって距離が近いデータ同士を同じハッシュ値にマッピングするため，検索時に類似度の閾値を変更することができない．閾値を変更するにはハッシュテーブルの再構築が必要になるため，ユーザが閾値を指定できるような類似検索は実現困難である．そこで本研究では，類似検索時に，クエリとハッシュ値が一致するデータに加え，ハッシュ値が近いデータも取得することで，ハッシュテーブルの再構築を行うことなく，閾値を指定できる類似検索を実現した．提案手法は，閾値に合わせてハッシュテーブルを逐次再構築する LSH と比較して，同程度の精度で，かつ 1,000 倍程度の高速化を達成できることを実験により確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We introduce an efficient algorithm named “Resizable-LSH” for approximate similarity search, which enables resizing the search range flexibly. Nowadays, Locality-Sensitive Hashing (LSH) is drawing attention as an efficient algorithm for approximate nearest neighbor search. LSH adopts hash functions that collide with high probability if two vectors are close, so that LSH finds approximate nearest neighbors quickly even if the dataset is high-dimensional. However, LSH should generate hash tables preliminarily, that results in resizing the search range costs expensive because hash table regeneration is required whenever we face the needs to resize search range. To solve the problem, our proposed Resizable-LSH retrieves not only the same hash value of query, but also near hash values. Then Resizable-LSH achieves resizable range-search. As it turns out, the result of the experiments shows Resizable-LSH works about 1,000 times faster than LSH with almost the same quality in comparison with LSH.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10114171
• 書誌情報: 研究報告情報学基礎（FI）; 巻 2009-FI-95, 号 22, p. 1-8, 発行日 2009-07-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会