13(1) 13-22, Mar 25, 2020 Peer-reviewed
局所性鋭敏ハッシュ(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.