高次元データのための相対的近似を用いた索引手法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 高次元空間探索を高速化するための新たな索引構造を提案する.高次元空間探索における最も優れた手法として, SR-treeとVA-Fileを挙げることができる.しかし, これまで両手法を比較した結果は報告されていない.そこで, 本論文ではまず両手法の比較結果を示し, その特性について論じる.我々が実施した両手法の比較実験では, SR-treeとVA-File, 双方の問題点を明らかにしている.SR-treeは分布に偏りがあるデータ集合において優れた特性を示すものの, 次元が高くなるに従い, ノンリーフノードにおけるエントリの容量の大きさが性能劣化要因につながる.VA-Fileは, 分布が一様でないような実用的なデータ集合に適しておらず, 分布の偏りが近似ファイルによるフィルタリングの効果を低減化させ, 探索性能の劣化につながる.実験結果の分析から, これらの性能劣化要因による影響を抑制し, 大幅な探索性能向上を実現するVR-tree(Virtual/Real tree)を考察した.VR-treeでは, 包囲方形及びデータオブジェクトの相対的近似に基づくアルゴリズムを導入する.相対的近似によって構築された木構造はノードにおけるエントリ容量が小さく, 探索処理において高い性能を示す.実データ集合を用いた実験では, VR-treeは64次元において, SR-treeと比べ約78.1%, またVA-Fileと比べ約78.6%のコスト削減を達成している.
- 社団法人電子情報通信学会の論文
- 2000-12-25
著者
-
児島 治彦
日本電信電話株式会社 NTTサイバースペース研究所
-
植村 俊亮
奈良先端科学技術大学院大学情報科学研究科
-
植村 俊亮
奈良先端科学技術大学院大学
-
吉川 正俊
奈良先端科学技術大学院大学 情報科学研究科
-
児島 治彦
NTTサイバーソリューション研究所
-
櫻井 保志
日本電信電話株式会社NTTサイバースペース研究所
-
児島 治彦
日本電信電話株式会社nttサイバースペース研究所
-
桜井 保志
NTTサイバースペース研究所
-
児島 治彦
NTTサイバースペース研究所
関連論文
- Webディレクトリを用いた2言語オントロジーの構築
- 映像の構造情報を活用した視聴者間コミュニケーション方法の提案
- D-045 言語横断情報検索におけるWebディレクトリを利用した訳語の曖昧性解消(D.データベース)
- Webディレクトリを言語資源として利用した言語横断情報検索
- D-35 ディレクトリ型検索エンジンを利用した言語横断情報検索(情報検索,D.データベース)
- オンライン業務プログラムの環境独立処理方式
- 日本語プログラム言語"まほろば"の言語仕様
- 日本語プログラム言語"まほろば"の言語仕様と記述評価
- プログラム言語での多バイト符号系支援時の設計指針
- 日本語プログラム言語"まほろば"の文法と記述評価
- 映像データベースシステムにおける映像演算の実装
- 動画像データベースの格納構造
- 重要なblogger発見を目的としたblogスレッド解析手法
- D-029 遺伝性疾患データベースを利用した関連遺伝子検索システムの開発(D.データベース)
- 効率的なXQuery処理のためのDTMに基づくXMLストレージ(クエリ,夏のデータベースワークショップDBWS 2006)
- 標準プログラム言語の国際化
- 入力要素を保存する集約に基づくビューへの問合せ最適化手法
- オブジェクトリンクを有する構造化文書に対する問合せ
- 大規模XMLデータに対する分散問合せ処理の効率化(XML,テーマ : 「デジタルアーカイブの活用(応用)」および一般)
- XMLストリームに対する時制問合せの一手法(XML,テーマ : 「デジタルアーカイブの活用(応用)」および一般)
- ユーザからの負担なく構築したプロファイルに基づく適応的Web情報検索(コンテンツ技術,Web情報システム)
- XML木のための動的範囲ラベル付け手法
- XMLのための動的範囲ラベル付け手法 : その評価およびXRelへの適用について
- 更新に強いXML節点数え上げ手法とその管理
- 情報探索技術を用いたXML部分文書の探索手法
- 2000-DBS-122-48 構造化文書を対象とした文字列検索とベクトル検索の統合について
- DE2000-70 構造化文書を対象とした文字列検索とベクトル検索の統合について
- オブジェクトの相対位置関係に基づく検索要求の視覚的記述とその処理方法
- 楕円体問合せのための空間変換を用いた類似探索アルゴリズム
- 楕円体問合せのための類似探索手法の提案
- 検索結果を統合するための関数選択手法(マルチメディア)(夏のデータベースワークショップDBWS2004)
- 検索結果を統合するための関数選択手法(セッション8A : マルチメディア)(夏のデータベースワークショップ : DBWS2004)
- オブジェクトの相対位置関係に基づく検索要求の視覚的記述とその処理方法
- 大規模XMLデータに対する分散問合せ処理の効率化(XML,テーマ : 「デジタルアーカイブの活用(応用)」および一般)
- XML文書検索システムにおける文書内容の統計量を利用した検索対象部分文書の決定(コンテンツ技術, Web情報システム)
- Prologを使ったRDFデータからのユーザ指定による文書構築(セッション4 : XML・構造化文書の蓄積とアクセス)
- Prologを使ったRDFデータからのユーザ指定による文書構築(セッション4 : XML・構造化文書の蓄積とアクセス)
- Prolog を使ったRDFデータからのユーザ指定による文書構築
- 自動化・統合化された Web サービス動的実行システム(情報システム開発の支援環境と手法)(情報システム論文)
- 自動化・統合化された Web サービス動的実行システム
- キーワードに基づいた部分文書検索における解答部分文書が持つ性質の分析(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- キーワードに基づいた部分文書検索における解答部分文書が持つ性質の分析(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- M-074 移動端末のためのトポロジ変化に強いクラスタリング手法(M.ネットワーク・モバイルコンピューティング)
- E-006 文書構築のためのツールとしてのProlog(E.自然言語・文書・ゲーム)
- キーワードを利用したXML文書検索
- 移動オブジェクトのクラスタリング手法に関する一提案(知識の蓄積と活用)(ユビキタス社会における情報流通および一般)
- 検索結果を統合するための情報量の概念を考慮したスコア正規化手法
- ハイパリンクで結ばれた隣接ページの内容に基づくWebページのためのTF-IDF法の改良(情報検索・文書分類)
- 動画像データベースの格納構造
- 5M-9 映像構造化のためのテロップ属性抽出・分類法の提案
- A-16-30 SceneMarket : 映像素材流通のための協調アノテーション
- SceneCabinet:映像解析技術を統合した映像インデクシングシステム
- 高次元データのための相対的近似を用いた索引手法
- D-12-20 二段階ライン二値化による低解像度テロップ文字領域抽出
- 映像コンテンツの構造化・検索技術 (特集 情報流通プラットフォームが拓く21世紀のネットワーク化社会(2))
- 映像コーパスの構築と分析 (知能情報メディア論文特集)
- 多次元空間における類似探索手法の提案
- ハイパーテキストデータベーススキーマ作成のためのノードの分類法
- D-12-27 分散並列型映像インデクシング方式の提案
- D-11-91 動きベクトルと輝度差分による映像中の動き特徴抽出
- 映像アーカイブ技術の動向
- XMLストリームに対する時制問合せの一手法(XML,テーマ : 「デジタルアーカイブの活用(応用)」および一般)
- 更新に強いXML節点数え上げ手法とその管理
- 「マルチメディア情報べース技術の研究」が目指すもの (メディア統合および環境統合のための高機能データベースシステム、および一般)
- XML文書における要素名と文書構造を利用した情報フィルタリング
- CD-ROMによる文献データベースの検索及び管理
- 情報処理用語のJIS規格における関連語検索
- Web対応事務処理スクリプト言語「COBOLスクリプト」
- 誤差を考慮した時系列マイクロアレイデータの時間軸補正方法(セッション6)
- 誤差を考慮した時系列マイクロアレイデータの時間軸補正方法(セッション6)
- 異なる時系列マイクロアレイデータの比較のためのデータ補正方式(Expression analysis)
- 言語横断情報検索における辞書ベースと統計ベースのアプローチの統合
- 言語横断情報検索における辞書ベースと統計ベースのアプローチの統合
- オブジェクトリンクを有する構造化文書に対する問合せ
- データベースを用いたグループアノテーションの実現
- 楕円体問合せのための類似探索手法の提案
- 仮想包囲矩形に基づく多次元データ集合に対する近傍探索
- ビットコーディングを用いたR-treeに基づく多次元空間内近傍探索の高速化
- 自律ディスクによる広域分散ストレージシステムの通信およびストレージのオーバヘッドを考慮した性能評価
- 自律ディスクによる広域分散ストレージシステムの通信およびストレージのオーバヘッドを考慮した性能評価(ストレージ,夏のデータベースワークショップDBWS 2006)
- 自律ディスクによる広域分散ストレージシステムの通信およびストレージのオーバヘッドを考慮した性能評価(ストレージ)
- 自律ディスクによる広域分散ストレージシステムの通信およびストレージのオーバヘッドを考慮した性能評価
- 自律ディスクによる広域分散ストレージの静的な性能解析(ストレージ2, 夏のデータベースワークショップDBWS2005)
- 自律ディスクによる広域分散ストレージの静的な性能解析(ストレージ2, 夏のデータベースワークショップ2005)
- 自律ディスクによる広域分散ストレージのデータ移動制御方式(セッション3 : データベース基盤技術)
- 分散メディエータ環境における索引情報のキャッシング手法の提案
- 歴史的文献画像のための電子スクラップブックシステム
- 意味付き文字画像を用いた文献の電子化
- 意味付き文字画像を用いた文献の電子化
- 仮想空間管理のための記述形式独立なデータモデル
- 利用者ごとの仮想空間の構築と共有
- 領域定義による仮想空間での情報選択
- 領域定義による共有仮想空間内での情報交換支援
- 領域定義による共有仮想空間内での情報交換支援
- 3次元仮想空間を用いたコミュニケーション支援 (時空間データベース)
- 動画像中のオブジェクトに注目したデータモデルと問合せ処理
- 映像データベースのための異種メディア間の演算
- 映像データベースのための同種メディアの統合
- 同一時間軸上の複数動画像の検索法
- 同一時間軸上の複数メディアの演算