2024-03-29T05:55:38Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001928132023-04-27T10:00:04Z01164:02735:09413:09632
狭い16ビットのスケッチを用いた高速最近傍検索Fast Nearest Neighbor Search with Narrow 16-bit Sketchjpnhttp://id.nii.ac.jp/1001/00192724/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=192813&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of Japan九州工業大学九州工業大学学習院大学九州工業大学九州工業大学樋口, 直哉今村, 安伸久保山, 哲二平田, 耕一篠原, 武局所性鋭敏ハッシュ (LSH) の一種であるスケッチを用いた最近傍検索について議論する.スケッチを用いる最近傍検索は 2 段階で行う.第 1 段階では,質問とのスケッチ間の距離が近いK個の解候補を選択する.ただし,K≥1 である.第 2 段階では,K 個の解候補に対して実距離計算を行うことで最近傍解を選択する.従来,高い検索精度を保証するためには 32 ビット以上のスケッチを用いていた.本研究では,スケッチのビット数を 16 に減らすことにより,バケット法にデータ管理による高速化を可能とし,第 1 段階の検索コストをほとんど無視できる手法を提案する.16 ビットスケッチを用いる検索は,精度を維持するためには,32 ビットスケッチをもちいる場合より大きな候補数 K を必要とする.データオブジェクトをスケッチの値によってソートしておくことで,第 2 段階の検索におけるメモリ局所性を向上することで候補数 K の増加による速度低下を低減できる.提案手法を用いると,検索精度を維持しつつ 10 倍程度の高速化が実現できる.AN10505667研究報告数理モデル化と問題解決(MPS)2018-MPS-1218162018-12-102188-88332018-12-06