ビットコーディングを用いたR - treeに基づく多次元空間内近傍探索の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-08
• タイトル: ビットコーディングを用いたR - treeに基づく多次元空間内近傍探索の高速化
• タイトル / 言語: en
• タイトル: High Dimensional Nearest Neighbor Searching by R - tree Using Bit Coding
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科／NTTヒューマンインタフェース研究所
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology/NTT Human Interface Laboratories
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology
• 著者名: 櫻井, 保志; 吉川, 正俊; 植村, 俊亮
• 著者名(英): Yasushi, Sakurai; Masatoshi, Yoshikawa; Shunsuke, Uemura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，高次元空間内のオブジェクト近傍探索に有用な空間ビットコーディング法と呼ぶインデックス構築手法を提案し，その構造と探索，挿入，削除アルゴリズムについて述べる．画像データベースシステムにおいては，テキスト形式で記述された付加情報に基づく検索のみならず，画像の内容に基づく検索が優れたヒューマンインタフェースを実現する上で必要である．しかし内容検索を実現するには，画像処理を実行して特徴量を抽出した後，類似した特徴量を有する1つもしくは，複数個の画像サンプルをデータベースから探索する必要がある．特にデータベースが大規模化し，さらに特徴量における次元数が高次元化するほど，類似検索のための探索処理が高負荷となる．これに対し，R-treeおよびその派生手法は対象画像の射影空間位量に基づいて．迅速に類似検索を実行するためのインデックス探索法である．本論文で提案する空間ビットコーディング法はR-treeの技術を利用するとともに，これに範囲矩形(bounding rectangle)の位置，サイズをビットコーディングによって表現する仮想範囲矩形(virtual bounding rectangle)の概念を導入することにより，探索時においてさらなるディスクアクセスの低減化を実現した．本研究では実験を通じて，探索，挿入処理のディスクアクセス数を計測し，従来手法と比較することにより空間ビットコーディング法を評価する．その性能評価によって，大規模データ集合に対する本手法の優位性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present a new indexing method called the Spatial Bit Coding Method which is useful for nearest neighbor searching in high dimensional space, then introduce tree structure and algorithms for searching, insertion and deletion. An image database system has need for not only retrieval using added information described by text but also content based retrieval to achieve excellent human interface. Content based retrieval needs selecting one or some images which has similar feature extracted by image processing from image database. Especially, for high dimensional and large data set, retrieval processing using image feature involves high cost. The R-tree and its variants are index search method for fast similarity retrieval based on projective location of target image. Our proposed method, the Spatial Bit Coding Method using R-tree technique is introduced idea of the virtual bounding rectangle of which location and size is represented by bit coding. As a result of adoption this method, fewer disk accesses is achieved in search operation. Finally, measurements of page accesses for search and insert operation and comparison of new and usual method is presented. The performance test prove the superiority of our method for high dimensional data set.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 1998, 号 57(1998-DBS-116), p. 303-310, 発行日 1998-07-08
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会