| 摘要 |
<p>最近傍候補の数を適切に絞り込むことにより、高い探索精度と高速性を兼ね備えた近似最近傍探索を実現する。ベクトルデータで表現される複数の点が入力されたとき、各点にハッシュ関数をそれぞれ適用してハッシュのインデックスを算出し、前記多次元ハッシュテーブルのビンによって複数の領域に分割された多次元空間内に各点を射影することにより各点を多次元ハッシュテーブルに格納してなるデータベース格納部と、クエリが入力されたとき、そのクエリに前記ハッシュ関数を適用して前記空間内でのクエリの位置を決定し、クエリと前記空間内の各領域との距離の推定値を決定し、その推定値に基づいて探索すべき領域を決定する探索範囲決定部と、前記探索領域内の各点とクエリとの距離を計算し、クエリに最も近い点をクエリの最近傍点として算出する最近傍点決定部とを備え、前記探索範囲決定部は、各領域のインデックスを参照してその領域の代表点を求め、前記クエリと各代表点との距離に基づいて前記推定値を決定し、分枝限定法を適用して前記探索すべき領域になり得ない領域を除外して前記探索すべき領域を決定する近似最近傍探索装置を適用する。</p> |
