2024-03-29T16:43:10Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002043152020-10-27T05:02:56Z00934:00989:10088:10089
狭い16ビットのスケッチを用いた高速最近傍検索Fast Nearest Neighbor Search with Narrow 16-bit Sketchjpn[オリジナル論文] スケッチ,局所鋭敏性ハッシュ,バケット法,k近傍検索http://id.nii.ac.jp/1001/00204220/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=204315&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Information Processing Society of Japan九州工業大学株式会社THIRD学習院大学九州工業大学九州工業大学樋口, 直哉今村, 安伸久保山, 哲二平田, 耕一篠原, 武局所性鋭敏ハッシュ(LSH)の一種であるスケッチを用いたk近傍検索について議論する.スケッチを用いるk近傍検索は2段階で行う.第1段階では,質問とのスケッチ間の距離が近いK個の解候補を選択する.ただし,K ≥ kである.第2段階では,K個の解候補に対して実距離計算を行うことでk近傍解を選択する.従来,高い検索精度を保証するためには32ビット以上のスケッチを用いていた.本研究では,スケッチのビット数を16に減らすことにより,バケット法を用いたデータ管理による高速化を可能とし,第1段階の検索コストをほとんど無視できる手法を提案する.16ビットスケッチを用いる検索は,精度を維持するためには,32ビットスケッチを用いる場合より大きな候補数Kを必要とする.データオブジェクトをスケッチの値によってソートしておくことで,第2段階の検索におけるメモリ局所性を向上することで候補数Kの増加による速度低下を低減できる.提案手法を用いると,検索精度を維持しつつ10倍程度の高速化が実現できる.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.AA11464803情報処理学会論文誌数理モデル化と応用(TOM)13113222020-03-251882-77802020-03-18