@phdthesis{oai:kyutech.repo.nii.ac.jp:00006569,
 author = {樋口,  直哉},
 month = {2020-06-02},
 note = {第1章 はじめに||第2章 準備||第3章 スケッチの最適化||第4章 次元縮小の量子化像としてのスケッチ||第5章 ビット幅の狭いスケッチを用いる高速検索||第6章 実験||第7章 結論と今後の課題, スケッチは，データをコンパクトなビット列で表現したもので，局所性鋭敏ハッシュ（Locality Sensitive Hashing, LSH）の一種である．本論文では，スケッチを用いた多次元データの類似検索について議論する．多次元データは距離空間に配置されていると仮定し，類似検索としては，k近傍検索を用いる．ここで，k近傍検索とは，k ? 1 に対し，与えられた質問データqに対して，検索対象のデータベースからqに近い上位k個のデータを求めることである．　本論文では，球面分割（BP）に基づくスケッチを用いる．BPは，空間内のデータに対して，中心点がp，半径rの球の内外に対応して，ビット“0”または“1”を割り当てる．この中心点と半径の対（p, r）をピボットという．ピボットをw個用いて，長さwビットのスケッチを作成する．スケッチの長さを幅という．スケッチは，距離情報を部分的にしか保持できないので，スケッチを用いるk近傍検索は2段階で行う．第1段階では，スケッチによるフィルタリングを行い，質問とのスケッチ間の距離が近い順にK個の解候補を選択する．ただし，K ? k である．第2 段階では，K個の解候補に対してデータ間の実際の距離計算を行うことでk近傍解を選択する．一般に，Kを大きくすると正しい解が得られる確率である検索精度は高くなるが，検索速度は遅くなる．また，スケッチの幅wを大きくすると，フィルタリング性能は向上するが，フィルタリングのコストは大きくなる．　従来，第1段階検索での解候補選択のための優先順位付けとしては，スケッチ間の不一致ビット数を表すハミング距離が用いられており，高い検索精度を保証するためには，スケッチ幅は32ビット以上が必要であると考えられていた．そのため，第1段階検索は，あらかじめ用意したすべてのデータのスケッチを格納したデータベースに対する全探索によって実現されてきた．第1段階で全探索を用いたとしても，スケッチが元のデータに比べるとコンパクトになっているので，元のデータを直接検索するよりも高速に実行できる．　本研究では，まず，ビット幅を固定した場合のフィルタリング性能が高くなるようにスケッチを設計する最適化手法について議論する．スケッチのフィルタリング性能を直接測定するとコストが大きいので，その代わりに，最適化の目的関数としてスケッチの衝突確率を用いて，その最小化を行う．衝突とは，異なるデータに対して同じスケッチが割り当てられることをいう．データベース内のデータ分布を考慮する発見的手法として，2値量子化法を提案し，有効であることを示す．また，焼きなまし法の効率的実現法であるAIR（Annealing by Increasing Resampling）による最適化も有効であることを示す．衝突確率を下げていくと，フィルタリング性能が向上する傾向は確認できるが，衝突確率を下げ過ぎると，必ずしもフィルタリング性能が最大となるとは限らないことも確認できる．　つぎに，スケッチを次元縮小射影とみなすことにより，質問とスケッチ間の距離下限を求めることができることを示し，距離下限の集計で定義される新しい優先順位付けscore1; score1; score2を提案し，第1段階の解候補の選択基準としてハミング距離よりも高性能である，つまり，高精度のフィルタリングが可能となることを示す．　さらに，従来よりも幅が狭い16ビット前後のスケッチを用いることにより，バケット法を用いたデータ管理による高速化を可能とし，質問との優先順位順にスケッチを列挙することにより第1段階の検索コストをほとんど無視できる手法を提案する．16ビット前後の幅のスケッチを用いる検索は，精度を維持するためには，32ビットスケッチを用いる場合より大きな候補数Kを必要とする．しかし，バケット法ではデータオブジェクトをスケッチの値によってソートして，第2段階の検索におけるメモリ局所性を向上することにより，候補数Kの増加による速度低下を低減できる．提案手法を用いると，約700万件の画像特徴データ（64次元）や音特徴データ（96次元）を用いた最近傍検索実験により，16ビットスケッチとscore1による優先順の列挙を用いる提案手法では，32ビットスケッチとハミング距離を用いる従来手法より，90%以上の検索精度が要求される場合でも20倍以上の高速化が実現できることがわかる．なお，この検索速度は，スケッチを用いない全探索と比べると50～100倍程度高速である．　また，データベースのデータ件数やデータの次元数と最適なスケッチ幅の関係について調査し，データ件数が大きくなるとスケッチ幅を広くする方がよく，データの次元数が高くなるとスケッチ幅は狭くした方がよいという傾向があることを示す．, 九州工業大学博士学位論文 学位記番号: 情工博甲第345号 学位授与年月日:令和2年3月25日, 令和元年度},
 school = {九州工業大学},
 title = {スケッチを用いた多次元データの高速類似検索に関する研究},
 year = {}
}