グラフ分解を用いた構造による部分グラフ問い合わせ処理の改良とその実験的評価(セッション6c:問合せ処理・インデクシング)
スポンサーリンク
概要
- 論文の詳細を見る
グラフは複雑な構造を表現する重要な構造として,ますます重要性が高まっている.それに伴い,グラフデータベースに対する効率的な検索が求められている.しかし,部分グラフ同型判定問題はNP完全であることが知られており,そのような検索は複雑かつ困難である.そのため,グラフデータベースを効率的に検索するための索引付けの研究が数多く成されている.しかし,索引付けの多くはクエリを含むグラフの数が多いほど,候補者集合の検証に時間がかかり,非効率的になってしまう.一方,布施らはクエリを含むグラフの数が非常に多い場合により有効である検索手法を提案した.我々は,既存のグラフの枝刈り手法を利用することで,彼らの手法をより一般的なデータも効率的に処理できるように改良した.実験では,改良した手法を彼らの提案した手法,VF2による逐次処理,HeらによるClosure Treeを修正した手法と比較し性能を評価した.
- 2008-09-14
著者
関連論文
- グラフ分解を用いた構造による部分グラフ問い合わせ処理の改良とその実験的評価(セッション6c:問合せ処理・インデクシング)
- 関係データベースを利用したXMLリポジトリのためのアクセス管理手法
- Max Flowアルゴリズムを用いたWebページのクラスタリング方法とその評価
- 差異を意識したクラスタリングとその特徴量集約手法の検討(クラスタリング, 夏のデータベースワークショップDBWS2005)
- Max FlowアルゴリズムによるWebページのクラスタリング方法(Web検索, 夏のデータベースワークショップDBWS2005)
- 差異を意識したクラスタリングとその特徴量集約手法の検討(クラスタリング, 夏のデータベースワークショップ2005)
- Max FlowアルゴリズムによるWebページのクラスタリング方法(Web検索, 夏のデータベースワークショップ2005)
- 斜交基底を用いたメタ検索におけるランクリストの統合方法の提案(情報フィルタリング・情報要約, データ工学論文)
- Max Flowアルゴリズムを用いたWebページのクラスタリング方法の提案
- Interlace定理に基づく多分木を用いたグラフの索引手法(夏のデータベースワークショップ2007(データ工学,一般))
- インクリメンタルに更新可能なXPushマシンにおけるフィルタ交換のコスト削減(データ処理アルゴリズム)
- インクリメンタルに更新可能なXPushマシンにおけるフィルタ交換のコスト削減(データ処理アルゴリズム)
- Interlace定理に基づく多分木を用いたグラフの索引手法(インデックス,夏のデータベースワークショップ2007(データ工学,一般))
- ラベル付きグラフのフィルタリングのための行列サイズ縮小手法(夏のデータベースワークショップ2007(データ工学,一般))
- ラベル付きグラフのフィルタリングのための行列サイズ縮小手法(インデックス,夏のデータベースワークショップ2007(データ工学,一般))
- インクリメンタルに更新可能なXPushマシン
- 創発的XMLの提案(XML, 夏のデータベースワークショップDBWS2005)
- インクリメンタルに更新可能なXPushマシン(ストリームデータ2, 夏のデータベースワークショップDBWS2005)
- 創発的XMLの提案(XML, 夏のデータベースワークショップ2005)
- インクリメンタルに更新可能なXPushマシン(ストリームデータ2, 夏のデータベースワークショップ2005)
- グラフの連結性に基づくMessmerらの部分グラフ同型判定手法の改良
- インクリメンタルに更新可能な状態遷移表を用いたXPushマシン
- D-020 固有値を用いたグラフ検索のためのグラフの行列表現の比較(情報アクセスとマイニング,D分野:データベース)