講演・口頭発表等

1997年1月24日

単純化アンカーポイント法による最近傍探索アルゴリズム

電子情報通信学会技術研究報告. CAS, 回路とシステム
  • 山田 芳郎
  • ,
  • 石田 光伸
  • ,
  • 都築 伸二
  • ,
  • 田崎 三郎

記述言語
日本語
会議種別

予め計算しておいた符号語間の距離の表を用いて, 三角不等式にもとずく候補符号語のしほりこみを行う最近傍探索の高速計算手法がHuangらによって提案されている. 同手法では, 符号帳のサイズをNとすると, 符号語間距離表の大きさがO(N^2)のオーダーで大きくなる. そこで, アンカー点と呼ばれる少数の点と符号語との距離の表を用いるアンカーポイント法がRamasubramanianらによって提案されている. しかし, 高速化のために導入される演算のオーバヘッドが大きくなり, 候補の数を大幅に削減できる割には総演算量がそれほど減少しない. そこで, 本稿ではオーバヘッドの小さい単純化アンカーポイント法を提案している.