狭い16ビットのスケッチを用いた高速最近傍検索

• Item type: Trans(1)
• 公開日: 2020-03-25
• タイトル: 狭い16ビットのスケッチを用いた高速最近傍検索
• タイトル / 言語: en
• タイトル: Fast Nearest Neighbor Search with Narrow 16-bit Sketch
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] スケッチ，局所鋭敏性ハッシュ，バケット法，k近傍検索
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州工業大学
• 著者所属: 株式会社THIRD
• 著者所属: 学習院大学
• 著者所属: 九州工業大学
• 著者所属: 九州工業大学
• 著者所属(英): en
• 著者所属(英): Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): THIRD INC.
• 著者所属(英): en
• 著者所属(英): Gakushuin University
• 著者所属(英): en
• 著者所属(英): Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Kyushu Institute of Technology
• 著者名: 樋口, 直哉; 今村, 安伸; 久保山, 哲二; 平田, 耕一; 篠原, 武
• 著者名(英): Naoya, Higuchi; Yasunobu, Imamura; Tetsuji, Kuboyama; Kouichi, Hirata; Takeshi, Shinohara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 局所性鋭敏ハッシュ（LSH）の一種であるスケッチを用いたk近傍検索について議論する．スケッチを用いるk近傍検索は2段階で行う．第1段階では，質問とのスケッチ間の距離が近いK個の解候補を選択する．ただし，K ≥ kである．第2段階では，K個の解候補に対して実距離計算を行うことでk近傍解を選択する．従来，高い検索精度を保証するためには32ビット以上のスケッチを用いていた．本研究では，スケッチのビット数を16に減らすことにより，バケット法を用いたデータ管理による高速化を可能とし，第1段階の検索コストをほとんど無視できる手法を提案する．16ビットスケッチを用いる検索は，精度を維持するためには，32ビットスケッチを用いる場合より大きな候補数Kを必要とする．データオブジェクトをスケッチの値によってソートしておくことで，第2段階の検索におけるメモリ局所性を向上することで候補数Kの増加による速度低下を低減できる．提案手法を用いると，検索精度を維持しつつ10倍程度の高速化が実現できる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We discuss k nearest neighbor search using sketches, which is a kind of locality sensitive hash (LSH). Search using sketches is processed in two stages. The first stage is to select K solution candidates close in distance between the question and the sketch, where K ≥ k. In the second stage, k nearest neighbor solutions are selected by performing real distance calculation on K candidates. Conventionally, to ensure high search accuracy, sketches of 32-bit or more have been used. In this paper, we reduce the width of sketches to 16-bit for which efficient data management by bucket is applicable. We propose a search method that enables high speed with the first stage of negligible cost. Searches using 16-bit sketches require a larger number of candidates K to maintain accuracy than using 32-bit sketches. However, by sorting the data objects by their sketch values, memory locality in the second stage search is improved and influence by increasing K is canceled. By using the proposed method, about 10 times speedup can be realized while maintaining search accuracy.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 13, 号 1, p. 13-22, 発行日 2020-03-25
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会