| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-03-14 13:15 B+木を用いた補助記憶装置上での近似最近傍探索 ○姫井教考・和田俊和（和歌山大）  PRMU2008-273 |
|
| 抄録 | （和） | 最近傍探索は事例ベース画像処理・解析などに用いられる重要な処理であるが，高次元空間での最近傍探索の高速化は困難である．このため，近年，近似最近傍を求めることによって探索の高速化を図るという方法が研究されている．従来から，木探索を用いた最近傍探索に許容誤差を導入したApproximate Nearest Neighbor(ANN)や，ハッシュ型のLocality Sensitive Hashing(LSH)がよく知られている．特にLSHは，探索精度と探索時間の関係が明確であり，近年特に注目を集めている．このLSHを，格納するデータの分布を利用したPrincipal Component Hashing(PCH)は，p-stable LSHよりもさらに高速であり，格納されたデータから離れた部分にクエリが与えられても探索に失敗することがないという利点がある．しかし，従来の最近傍探索法はメモリ上にデータを展開してから探索を行うため，1)起動から探索開始までに要する時間が長い，2)扱うデータベースがメモリに乗らないほど大きなサイズになると探索が行えない，等の問題がある．そこで本研究では，PCHで扱うデータのハッシュ値をB+木の構造を持つファイルに格納することにより，主メモリではなく補助記憶装置の上で近似最近傍探索を行う手法を提案する．これにより，メモリに乗らないほど大きなデータベースでも探索が行え，しかもOSのメモリキャッシュ機能により，類似したクエリに対しては探索を繰り返すほど高速になることを確認した． |
| （英） | Nearest Neighbor (NN) search plays important roles in example-based Computer Vision algorithms. Accelerating NN search in very high-dimensional space, however, has a limitation, because of curse of dimensionality. For avoiding this problem, approximate NN search algorithms have been proposed. The most popular one is ANN which is basically a kd-tree based search algorithm with a feasible error. Recently, Locality Sensitive Hashing (LSH) is getting highlighted, because of its theoretical basis providing a clear relationship between the accuracy and the computational complexity. An improved hash based search algorithm, Principal Component Hashing (PCH), has been proposed, which is faster than ANN and LSH at the same accuracy without producing any search failures. However, most NN search algorithms share the limitations that 1) start-up time is mainly consumed for loading the data onto the memory, and 2) NN search for huge data cannot be executed, because the main memory size is limited. For solving this problem, we propose an external NN search algorithm which directly finds the approximate NN data on HDD based on PCH algorithm. The basic idea is simple. By replacing the hash bins on a projection axis by a file having B+ tree structure, we can realize memory efficient PCH which works on HDD. In the experiment, we confirmed that the algorithm can perform NN search on huge database, which cannot be loaded on main memory. Also, we noticed that the search algorithm gains unexpected acceleration by the cashing mechanism of Linux operating system that frequently accessed data on HDD is kept on the memory. | |
| キーワード | （和） | 高次元空間 / 近似最近傍探索 / 補助記憶装置 / HDD / PCH / B+木 / / |
| （英） | high dimensional space / approximate NN search / auxiliary storage / HDD / PCH / B+tree / / | |
| 文献情報 | 信学技報, vol. 108, no. 484, PRMU2008-273, pp. 223-228, 2009年3月. | |
| 資料番号 | PRMU2008-273 | |
| 発行日 | 2009-03-06 (PRMU) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | PRMU2008-273 |
|
| 研究会情報 | |
| 研究会 | PRMU |
| 開催期間 | 2009-03-13 - 2009-03-14 |
| 開催地（和） | 東北工業大 |
| 開催地（英） | Tohoku Institute of Technology |
| テーマ（和） | コンピュータビジョンとパターン認識のための学習理論 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | PRMU |
| 会議コード | 2009-03-PRMU |
| 本文の言語 | 日本語 |
| タイトル（和） | B+木を用いた補助記憶装置上での近似最近傍探索 |
| サブタイトル（和） | |
| タイトル（英） | Approximate nearest neighbor search algorithm on HDD based on B+ tree. |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 高次元空間 / high dimensional space |
| キーワード(2)（和/英） | 近似最近傍探索 / approximate NN search |
| キーワード(3)（和/英） | 補助記憶装置 / auxiliary storage |
| キーワード(4)（和/英） | HDD / HDD |
| キーワード(5)（和/英） | PCH / PCH |
| キーワード(6)（和/英） | B+木 / B+tree |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 姫井 教考 / Noritaka Himei / ヒメイ ノリタカ |
| 第1著者 所属（和/英） | 和歌山大学 (略称： 和歌山大) Wakayama University (略称： Wakayama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 和田 俊和 / Toshikazu Wada / ワダ トシカズ |
| 第2著者 所属（和/英） | 和歌山大学 (略称： 和歌山大) Wakayama University (略称： Wakayama Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-03-14 13:15:00 |
| 発表時間 | 30分 |
| 申込先研究会 | PRMU |
| 資料番号 | PRMU2008-273 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.484 |
| ページ範囲 | pp.223-228 |
| ページ数 | 6 |
| 発行日 | 2009-03-06 (PRMU) |
[研究会発表申込システムのトップページに戻る]