単純化アンカーポイント法による最近傍探索アルゴリズム  [in Japanese] Simplified Anchor Point Method for Fast Nearest Neighbor Search Algorithm  [in Japanese]

Search this Article

Author(s)

Abstract

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

Huang et al. proposed a fast nearest algorithm in which, based on the triangle inequality, candidate codewords are examined using inter-codeword distance table. Their method requires a large distance table propotional to N(N-1)/2, where N denotes codebook size. Ramasubramanian et al. proposed the anchor point method that improves the memory complexity of Huang's method. This paper propose a simplified anchor point method in order to reduce the overhead of candidate selection, thus computational complexity, in Ramasubramanian's anchor point method.

Journal

  • IEICE technical report. Circuits and systems

    IEICE technical report. Circuits and systems 96(476), 71-76, 1997-01-24

    The Institute of Electronics, Information and Communication Engineers

References:  6

Codes

  • NII Article ID (NAID)
    110003197943
  • NII NACSIS-CAT ID (NCID)
    AN10013094
  • Text Lang
    JPN
  • Article Type
    ART
  • Data Source
    CJP  NII-ELS 
Page Top