ネイティブグラフデータベースにおける再帰的走査の効率化に向けた経路管理方法の提案

• Item type: SIG Technical Reports(1)
• 公開日: 2019-09-03
• タイトル: ネイティブグラフデータベースにおける再帰的走査の効率化に向けた経路管理方法の提案
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: データ工学
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 同志社大学大学院文化情報学研究科／日本学術振興会
• 著者所属: 同志社大学文化情報学部
• 著者所属(英): en
• 著者所属(英): Doshisha University /
• 著者所属(英): en
• 著者所属(英): Doshisha University
• 著者名: 楠, 和馬; 波多野, 賢治
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフは節点と関係辺で構成されるデータ構造であり，ソーシャルネットワークや知識ベース，電子商取引履歴などのデータ内に存在する関係性を取り扱うデータの表現に多く利用されている．しかしそれらグラフデータの問合せや分析には，データベースに格納されている関係性を辿る （以下，グラフ走査） ことで NP 完全問題である部分グラフ抽出を行う必要がある．これにより，データベースのデータ量に依存せずグラフ走査を一定の処理コストで行うことができるネイティブグラフデータベース (以下，GDB) においても，関係辺を辿る回数が多くなるほどグラフ走査性能がスケールしない問題が生じる．この原因の一つとして，グラフ走査において複数の関係辺を一問合せにおいて発生する際に，ネイティブ GDB では不要な節点でもグラフを展開するために一度読み込む必要がある，といった冗長さにある．したがって，複数の関係辺を辿らずに直接的に目的の節点への経路を辿ることが可能になれば，節点読込みやグラフ走査回数の少ない効率的なグラフ走査を行うことができる．そこで本稿では，データベース内に含まれている同一関係性の連なりを記録しネイティブ GDB で管理することで，効率的なグラフ走査の補助方法を提案する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10114171
• 書誌情報: 研究報告情報基礎とアクセス技術（IFAT）; 巻 2019-IFAT-136, 号 11, p. 1-4, 発行日 2019-09-03
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8884
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会