B+木を用いた補助記憶装置上での近似最近傍探索(テーマ関連セッション6)
スポンサーリンク
概要
- 論文の詳細を見る
最近傍探索は事例ベース画像処理・解析などに用いられる重要な処理であるが,高次元空間での最近傍探索の高速化は困難である.このため,近年,近似最近傍を求めることによっして探索の高速化を図るという方法が研究されている.従来から,木探索を用いた最近傍探索に許容誤差を導入したApproximate Nearest Neighbor(ANN)や,ハッシユ型のLocality Sensitive Hashing(LSH)がよく知られている.特にLSHは,探索精度と探索時間の関係が明確であり,近年特に注目を集めている.このLSHを,格納するデータの分布を利用したPrincipal Component Hashing(PCH)は,p-stable LSHよりもさらに高速であり,格納されたデータから離れた部分にクエリが与えられても探索に失敗することがないという利点がある.しかし,従来の最近傍探索法はメモリ上にデータを展開してから探索を行うため,1)起動から探索開始までに要する時間が長い,2)扱うデータベースがメモリに乗らないほど大きなサイズになると探索が行えない,等の問題がある.そこで本研究では,PCHで扱うデータのハッシュ値をB+木の構造を持つファイルに格納することにより,主メモリではなく補助記憶装置の上で近似最近傍探索を行う手法を提案する.これにより,メモリに乗らないほど大きなデータベースでも探索が行え,しかもOSのメモリキャッシュ機能により,類似したクエリに対しては探索を繰り返すほど高速になることを確認した.
- 2009-03-06
著者
関連論文
- B+木を用いた補助記憶装置上での近似最近傍探索(テーマ関連セッション6,コンピュータビジョンとパターン認識のための学習理論)
- B+木を用いた補助記憶装置上での近似最近傍探索(テーマ関連セッション6)
- 劣化の影響を受けにくい画像間相違度に関する研究 (情報論的学習理論と機械学習)
- 第10回コンピュータビジョン国際会議ICCV2005報告(会議報告)
- 第10回コンピュータビジョン国際会議ICCV2005報告(会議参加報告,CVのためのパターン認識・学習理論の新展開)
- 一般分布に対するPrincipal Component Hashing(一般セッション11)
- 一般分布に対するPrincipal Component Hashing(一般セッション4,三次元画像,多視点画像)
- 自己参照に基づくパターン欠陥検査法(一般セッション7,コンピュータビジョンとパターン認識のための学習理論)
- 自己参照に基づくパターン欠陥検査法(一般セッション7)
- 誤差による変動幅を考慮した決定木に関する研究(テーマ関連セッション6,コンピュータビジョンとパターン認識のための学習理論)
- 誤差による変動幅を考慮した決定木に関する研究(テーマ関連セッション6)
- 複数カメラを用いたCONDENSATIONのための隠れに対して頑健な重み統合法
- データベースに基づくサーバサイド迷惑メール検出システム(セキュリティ技術, インターネットアーキテクチャ技術論文)
- 飽和画像からの色復元 : 1,2色飽和の場合(一般セッション1,コンピュータビジョンとパターン認識のための学習理論)
- 2次元主成分分析を用いたMahalanobis距離最小化による高次元線形写像計算法:2D-M3(テーマ関連セッション5,コンピュータビジョンとパターン認識のための学習理論)
- 線形弁別特徴変換に関する研究(テーマ関連セッション5,コンピュータビジョンとパターン認識のための学習理論)
- 飽和画像からの色復元 : 1,2色飽和の場合(一般セッション1)
- 2次元主成分分析を用いたMahalanobis距離最小化による高次元線形写像計算法:2D-M3(テーマ関連セッション5)
- 動的色境界の提案と道路標識追跡・認識への応用(一般セッション8)
- 動的色境界の提案と道路標識追跡・認識への応用(一般セッション3,三次元画像,多視点画像)
- 高次元空間における近似最近傍探索技術の進歩とその展望 (特集 大規模画像データ処理)
- 機械学習法のロボット知能化システムへの応用(2)
- 機械学習法のロボット知能化システムへの応用(1)
- 事例を用いた弁別性マップの構築とその応用 : 弁別性マップを用いたステレオトラッキング(一般セッション1)
- 空間分割を用いた識別と非線形写像の学習 : (2)データ空間の再帰的分割に基づく非線形写像学習 : 回帰木の今昔
- 非線形写像学習のための PaLM-Tree の提案
- 情報量基準に基づく区分的関数あてはめによる写像学習(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 識別器選択のための入力空間分割法に関する検討(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 回帰木を用いた非線形写像の学習と識別問題への応用(テーマ関連/オーガナイズドセッション(2))
- 回帰木を用いた非線形写像の学習と識別問題への応用(オーガナイズドセッション(2))(CVのためのパターン認識・学習理論の新展開)
- ステレオカメラによる色ターゲットの3次元位置計測(卒論セッション)
- ロボットの身体と環境との相互作用に基づく地図作成法(卒論セッション)
- 高次元空間における近似最近傍探索技術の進歩とその展望(大規模画像データ処理)
- 特集「大規模画像データ処理」にあたって
- 一般分布に対するPrincipal Component Hashing(一般セッション4,三次元画像,多視点画像)
- Whiteningと線形予測を用いた人為的操作を伴うプラントの異常検出 (ヒューマン情報処理)
- Whiteningと線形予測を用いた人為的操作を伴うプラントの異常検出 (パターン認識・メディア理解)
- 線形弁別特徴変換に関する研究(テーマ関連セッション5)
- 装着型カメラを用いた頭部位置・姿勢の計測法
- 劣化の影響を受けにくい画像間相違度に関する研究
- ユーザの選好を反映した特徴変換(一般,顔・人物・ジェスチャ・行動)
- 文書表裏面スキャン画像の輝度値分布変換による裏写り除去法(一般,顔・人物・ジェスチャ・行動)
- 文書表裏面スキャン画像の輝度値分布変換による裏写り除去法(一般,顔・人物・ジェスチャ・行動)
- 劣化の影響を受けにくい画像間相違度に関する研究(一般,顔・人物・ジェスチャ・行動)
- 劣化の影響を受けにくい画像間相違度に関する研究(一般,顔・人物・ジェスチャ・行動)
- 劣化の影響を受けにくい画像間相違度に関する研究 (パターン認識・メディア理解)
- Mahalanobis距離最小化による高次元線形写像計算法:M3(パターン認識と学習,第12回画像の認識・理解シンポジウム推薦論文,画像の認識・理解論文)
- SIFT特徴量の拡張と対称性平面物体検出への応用(幾何学的解析,第12回画像の認識・理解シンポジウム推薦論文,画像の認識・理解論文)
- 対称SIFT特徴量を用いた対称性平面物体検出(一般セッション4)
- 対称SIFT特徴量を用いた対称性平面物体検出(一般セッション4,CV/PR技術のVRへの応用)
- ユーザの選好を反映した特徴変換(一般,顔・人物・ジェスチャ・行動)
- マスメイルデータベースとそれを用いたマスメイル検出システム
- 動的色境界の提案と道路標識追跡・認識への応用(一般セッション3,三次元画像,多視点画像)
- Chamfer Matchingを利用した有向NFTGとその応用(テーマ関連セッション3)
- Chamfer Matchihgを利用した有向NFTGとその応用(テーマセッション(3),CVのためのパターン認識・学習理論の新展開)
- 離散最適化によるDenoisingのFPGA上での実時間実装法(一般,顔・人物・ジェスチャ・行動)
- 離散最適化によるDenoisingのFPGA上での実時間実装法(一般,顔・人物・ジェスチャ・行動)
- 画像理解-新たな方法論は見つかったか?
- コンテンツに基づくマスメイルフィルタリング(光ネットワーク構成技術,インターネット関連技術,及び一般)
- コンテンツに基づくマスメイルフィルタリング(光ネットワーク構成技術,インターネット関連技術,及び一般)
- コンテンツに基づくマスメイルフィルタリング(光ネットワーク構成技術,インターネット関連技術,及び一般)
- ステレオカメラを用いた顔検出の高速化(一般セッション3)
- ステレオカメラを用いた顔検出の高速化(一般セッション3,CV/PR技術のVRへの応用)
- 特集「安心・安全のためのCV」の発行に寄せて(安心・安全のためのCV)
- 特集「安心・安全のためのCV」の発行に寄せて
- 二分探索型Belief Propagationの多次元拡張による領域分割
- Whiteningと線形予測を用いた人為的操作を伴うプラントの異常検出(一般,顔・人物・ジェスチャ・行動)
- FPGAを用いたSURFの実時間計算法(一般,顔・人物・ジェスチャ・行動)
- Whiteningと線形予測を用いた人為的操作を伴うプラントの異常検出(一般,顔・人物・ジェスチャ・行動)
- FPGAを用いたSURFの実時間計算法(一般,顔・人物・ジェスチャ・行動)
- 背景変化の共起性に基づく背景差分
- 複数カメラを用いたCONDENSATIONによる複数人物頭部の実時間検出・追跡(一般セッション11)
- 複数カメラを用いたCONDENSATIONによる複数人物頭部の実時間検出・追跡(一般セッション(5),CVのためのパターン認識・学習理論の新展開)
- MCMC/EMアルゴリズム/MDLを用いた床圧力センサからの複数人物位置追跡(一般セッション3)
- 制約付きEMアルゴリズムによる対象個数推定(一般セッション5)
- 制約付きEMアルゴリズムによる対象個数推定(一般セッション5,CV/PR技術のVRへの応用)
- インテグラルイメージを用いた主成分木による画像の最近傍探索の高速化(一般セッション(3),ユビキタス情報社会と複合現実感のためのパターン認識・メディア理解)
- インテグラルイメージを用いた主成分木による画像の最近傍探索の高速化
- 自動視線推定のためのアイモデルの個人適応法(一般セッション(2),ユビキタス情報社会と複合現実感のためのパターン認識・メディア理解)
- 連続特徴空間における決定木構築法と顔検出への応用(テーマ関連セッション4)
- 事例ベース対象追跡・認識のための近さ優先探索グラフの対話的構築アルゴリズム(テーマ関連セッション3)
- 効率的な距離計算戦略による高次元最近傍探索の高速化(テーマ関連セッション2)
- 空間分割と直交変換の統合による高次元最近傍探索の高速化(テーマ関連セッション2)
- 連続特徴空間における決定木構築法と顔検出への応用(テーマセッション(4)CVのためのパターン認識・学習理論の新展開)
- 事例ベース対象追跡・認識のための近さ優先探索グラフの対話的構築アルゴリズム(テーマセッション(3),CVのためのパターン認識・学習理論の新展開)
- 効率的な距離計算戦略による高次元最近傍探索の高速化(テーマセッション(2),CVのためのパターン認識・学習理論の新展開)
- 空間分割と直交変換の統合による高次元最近傍探索の高速化(テーマセッション(2),CVのためのパターン認識・学習理論の新展開)
- ハッシュを用いた最大類似度探索法に関する研究(一般セッション6)
- ハッシュを用いた最大類似度探索法に関する研究(一般セッション6,CV/PR技術のVRへの応用)
- 特集「CVにおけるパターン認識・学習理論の新展開」の発行に寄せて(CVにおけるパターン認識・学習理論の新展開)
- 最近傍探索・識別技術と画像理解(機械学習による自然言語処理・言語処理を利用したメディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 最近傍探索・識別技術と画像理解(機械学習による自然言語処理・言語処理を利用したメディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 4分木表現を用いた画像の高速最近傍識別(卒論セッション)
- 画像の4分木表現に対する最近傍識別(PRMU&NCテーマセッション(1) : 認識と学習)(認識と学習,模倣学習)
- 画像の4分木表現に対する最近傍識別(PRMU&NCテーマセッション(1) : 認識と学習)(認識と学習,模倣学習)
- 色競合における適応的事例収集法(卒論セッション)
- オプティカルフローの無相関化によるエゴモーション解析(一般セッション1)
- オプティカルフローの無相関化によるエゴモーション解析(一般セッション(1),CVのためのパターン認識・学習理論の新展開)
- 最近傍探索の理論とアルゴリズム (パターン認識・メディア理解)
- 画像を用いた対象検出・追跡(第2回)対象検出:総論