狠狠撸

狠狠撸Share a Scribd company logo

叠濒耻别辫谤颈苍迟蝉について

?Download as PPT, PDF?
?
Tetsuro Nagae
Tetsuro Nagae

グラフDBの叠濒耻别辫谤颈苍迟蝉についてのスライドです。Titanについても紹介しています。間違いがありましたらご連絡いただければ幸いです。

1 of 26
Downloaded 136 times
Blueprints & Titan 永江 哲朗
プロパティグラフモデル プロパティ name=wheel part_of （ = タイプ） name=car color=red ノード エッジ 構成要素 　?ノード (node; 別名 : 頂点 ) 　?エッジ (edge; 別名 : 辺 ) 　　　方向とタイプを有する。 ( ラベル付きで有向 ) 　?プロパティ (property; 別名 : 属性 ) 　　　ノードとエッジにおける属性
グラフ トラバーサル ?グラフ トラバーサル (Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ の図を利用 ) knows 上記の例でノード 1 から出て” knows” という条件でエッジを移動し、ノード 2, 8 に入ります。このようにエッジの向きやエッジのラベルなどをもとにグラフ を移動することを「グラフ トラバーサル」といいます。
グラフ トラバーサルを使ったリコメンデー ション リコメンデーションの例 (“The graph traversal pattern” (http://arxiv.org/abs/1004.1001/ )” Content-Based Recommendation に具体名を追加 ) feature 8 feature Goal 『江戸』 2 likes 6 resource person likes 『百日紅』 likes start feature 1 likes 3 likes 7 person resource person likes 『江戸名所図会』 4 feature 7 resource feature “( トラバーサル開始ノード ) –( エッジ :feature)-> ( ノード ) <–( エッ ジ :feature)- ( トラバーサル終了ノード )” という関係をノード 3 に適用すると 、ノード 2 がみつかります。
グラフ DB ● グラフ DB の特徴 　?テーブルにデータを保存しない。グラフというデータ構造だけがあります。 　?ノードとエッジは隣接する頂点やエッジに直接の参照をもっているの で、 RDB でいう「結合」という操作の概念がありません。むしろ、データ構 造は定義されたエッジによって既に「結合された」状態です。 ● メリット 　?グラフトラバーサルのコストは、グラフの局所的な繋ぎ方 ( トポロジー ) に依 存する 　　→ 移動のコストは全体のグラフのサイズによらず、ほぼ一定になります。 ( た だし、局所的でないクエリ [ 例えばグラフ全体にまたがる最短パスを求めるな ど ] は遅いという印象です ) 　　　 cf. RDB での結合ではデータのサイズの増加にともなってクエリのコストも 増加する ● デメリット 　?シングルサーバーを超えてスケールするのは難しい。
グラフ DB が有効な分野 ?ソーシャルネットワークデータのモデリング 　例 . Twitter でのフォロー、被フォローの関係や、ツイート?リツイ ートの関係 ?リコメンデーション ? PageRank ? RDB でいう Join を多く含むクエリーにも有効な場合があります。 グラフ DB は例えば Neo4j であれば 1 秒あたり百万トラバーサル以上 を処理できます。この場合、 1 クエリに平均 100 トラバーサルかか るとしても１万クエリ以上処理できます。
Blueprints ? Blueprints はプロパティグラフモデル用のインターフェイスや実装、 API などの セットです。 ? Blueprints は異なるグラフバックエンドを交換することを容易にします。そのた め、ベンダーロックインを回避することが可能です。 ? Blueprints は人気のあるグラフ DB(Neo4j, OrientDB, DEX, InfiniteGraph) に対する コネクターをもっています。 ? Blueprints は人気のあるグラフフレームワーク (JUNG(Java Universal Network/Graph Framework 等 ) に対するコネクターをもっています。 ? Blueprints は GraphML や GML, GraphSON といったグラフ ファイルフォーマッ トを読み込むことができます。 ? Blueprints とその他の TinkerPop スタックは、 BSD ライセンスのオープンソース です。
Blueprints の構成要素 ? Rexster: RESTful なグラフサーバーを実 現 ? Furnace: グラフアルゴリズムのパッケ ージ ? Frames: ノードとエッジをオブジェクト と関係に変換するオブジェクト - グラ フ マッパー ? Gremlin: Pipes にコンパイルされるグラ フ トラバーサル言語。 https://github.com/tinkerpop/blueprints/wiki/ より抜粋 ? Pipes: lazy( 遅延評価。結果が必要にな ったら処理を行う ) なグラフ トラバー サルを可能にするデータフローフレー
Gremlin ? Gremlin はグラフ トラバーサル用の言語です。 ? Gremlin は Blueprints プロパティグラフモデルを実装するグラフデー タベースやグラフフレームワークの上で動きます。例えば TinkerGraph, Neo4j, OrientDB, DEX, InfiniteGraph, Titan, Rexter, Sail RDF Stores など。
Gremlin の例 Gremlin の例 (Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ の図 ” Traversing vs. Pattern Matching” にメモ追記 ) goal start
Rexster ? Rexster Rexster は REST にフォーカスしたグラフサーバーです。拡張によってサ ーチやスコアリング、ランク、リコメンデーションといった一般的な グラフトラバーサルをサポートします。 Rexster は Blueprints, Pipes, Gremlin を広範囲に使用します。 Rexster では以下のようなグラフ DB 上で動作します。 ? TinkerGraph in-memory graph ? Neo4j graph database ? OrientDB graph database ? DEX graph database ? Titan graph database ? Sesame 2.0 compliant RDF stores ( 引用元 https://github.com/tinkerpop/rexster )
Pipes ? Pipes Pipes はプロセスグラフを使ったデータフローのフレームワークです。 プロセスグラフとはエッジで繋がった Pipe のノードから構成されま す。 Pipe はシンプルな計算のステップを実現しそれは他のオブジェ クトと結合して大きな計算を構成できます。それらのデータフロー のグラフによって、分割やマージ、ループ、一般的には入力からの データを出力に変換することができます。 ( 引用元 https://github.com/tinkerpop/pipes/wiki )
グラフ DB のスケール性 従来のグラフ DB では、グラフのサイズ、処理能力が複数サーバーで スケールしないという大きなデメリットがあります。 ?複数のインスタンスにまたがるグラフデータというものが今まで なかった ?? → このデメリットを克服するために分散化グラフ DB の研究開発が進 められています。
分散グラフ DB ? Apache Hama: 行列、グラフ、ネットワークのための大規模な科学 計算用フレームワーク。 HDFS 上で動作します。 ? Pregel: Google の分散グラフ?プラットフォーム (closed) 。 BSP( バ ルク同時並列 ) という概念を基盤とします。 ? Apache Giraph: Hadoop 環境上で動作する Pregel の実装です ? Titan: Blueprints の関係者 (Aurelius) が開発を進めている分散グラフ データベース。現時点 (2012 Oct) では始まったばかりでバージョン も 0.1 です )
Pregel ? Bulk Synchronous Parallel （ BSP 、バルク同期並列） ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
Titan ? Titan は分散化グラフデータベースです。大規模なグラフを複数のマ シン上で処理することができます。 ?分散化のストレージとして、現在は Cassandra と HBase をサポート しています。 ? Titan はネイティブな Blueprints-enable なデータベースであり、すべ ての TinkerPop スタックをサポートします。
Titan の利点 ? Titan は、シングルノードのサーバーが提供できる量を超えた容量と処 理能力を必要とするような巨大なグラフを処理することをサポートでき るように設計されました。これは Titan の基本的なメリットです。 【一般的な Titan の利点】 　?サーバークラスターにマシンを追加することによって、巨大なサイズ のグラフを分割して複数のインスタンスで使用できるようにします。 　?マシンをクラスターに追加することで、並列的なトランザクションを サポートします。 ( 複数マシンにまたがるグラフは並列化できないのか 調査中です ) 　?グラフトラバーサル用の言語 Gremlin をサポートします。 　? Rexster と容易に連携できます。
Titan でキーとなるアイデア ? edge compression ( エッジ圧縮 ) Titan におけるエッジ圧縮は次のようなことを可能とするために様々な 手法によって構成されます。 ?それそれのエッジのメモリ使用量をできるだけ小さくすること ?すべてのエッジの情報を、連続したメモリブロックに格納すること 。 これらによってデータの取得を速くすることができます。 ? vertex centric query support ( ノード中心クエリのサポート ) Vertex centric queries allow users to query for a specific set of edges by leveraging vertex centric indices and a query optimizer. ( ノード中心のイン デックスとクエリオプティマイザーを利用することで、特定のエッジ の集合をクエリすることができます ) ? graph partitioning ( グラフパーティショニング ) アクセスされる頻度が高いデータが同じサーバー上に載るように複数 のマシンにグラフを分散させます。
グラフパーティショニング ?グラフパーティショニング “Titan: The Rise of Big Graph Data” by Marko Rodriguez p.138 (http://www.slideshare.net/slidarko/titan-the-rise-of-big-graph-data)
まとめ ?グラフ トラバーサル ? Blueprints ? Gremlin ?分散化グラフ DB ? Titan
参考文献 ?” The Graph Traversal Pattern”, Marko A. Rodriguez, Peter Neubauer, Apr 2010 http://arxiv.org/abs/1004.1001/ ? Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ ? Blueprints wiki https://github.com/tinkerpop/blueprints/wiki/ ? InfoQ “ グラフデータベース、 NOSQL 、 Neo4j” http://www.infoq.com/jp/articles/graph-nosql-neo4j ? Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ ? ODBMS Industry Watch “On Big Graph Data. ” http://www.odbms.org/blog/2012/08/on-big-graph-data/ ?” Pregel: A System for Large-Scale Graph Processing” http://www.slideshare.net/shatteredNirvana/pregel-a-system-for-largescale-graph-processing ?グラフ問題とバルク同期並列の常識を Giraph で体得 http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/01.html ? Titan: The Rise of Big Graph Data http ://www.slideshare.net/slidarko/titan-the-rise-of-big-graph-data ? Titan wiki https://github.com/thinkaurelius/titan/wiki ? ODBMS Industry Watch “On Big Graph Data.” http:// www.odbms.org/blog/2012/08/on-big-graph-data/
BSP superstep (1) 以下のようなグラフで、東京から那覇への最小コストのパスを求める場合 （分散環境では、各都市の処理は異なったプロセッサで処理され、スケーラブル な構成になります）。 東京 1 6 ( エッジについている数字 9 は移動のコストを示しま す) 名古屋 1 大阪 福岡 2 那覇 3 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) を参考にしました
BSP superstep (2) step1: 始点「東京」は隣接する「名古屋」、「大阪」、「福岡」に時間を送信 します。 東京 0 1 6 9 名古屋 大阪 福岡 那覇 ∞ ∞ ∞ ∞ ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
BSP superstep (3) step2: ?名古屋では、現在値∞とメッセージの 1 より時間を「 1 」にし、隣接する大阪、福 岡へ「 1 ＋それぞれへの時間」を送信。 ?大阪では、現在値∞とメッセージの 9 より時間を「 9 」に更新します。 ?福岡では、現在値∞とメッセージの 8 より時間を「 8 」にし、隣接する那覇へ「 6 ＋そこへの時間」を送信します。 東京 0 1+1 6+2 名古屋 大阪 福岡 那覇 ∞→1 ∞→9 ∞→6 ∞ 1+3 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
BSP superstep (4) step3: ?大阪では、現在値「 9 」とメッセージの 2 より時間を「 2 」に更新します。 ?福岡では、現在値「 6 」とメッセージの 4 より時間を「 6 」にし、隣接する那 覇へ「 4 ＋そこへの時間」を送信します。 ?那覇では、現在値∞とメッセージの 8 より時間を「 8 」に更新します。 東京 0 名古屋 大阪 福岡 4+2 那覇 1 9→2 6→4 ∞→8 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
BSP superstep (5) step4: ?那覇では、現在値「 8 」とメッセージの 6 より時間を「 6 」に更新し ます。 東京 0 名古屋 大阪 福岡 那覇 1 2 4 8→6 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋

More Related Content

叠濒耻别辫谤颈苍迟蝉について

  • 1. Blueprints & Titan 永江 哲朗
  • 2. プロパティグラフモデル プロパティ name=wheel part_of （ = タイプ） name=car color=red ノード エッジ 構成要素 　?ノード (node; 別名 : 頂点 ) 　?エッジ (edge; 別名 : 辺 ) 　　　方向とタイプを有する。 ( ラベル付きで有向 ) 　?プロパティ (property; 別名 : 属性 ) 　　　ノードとエッジにおける属性
  • 3. グラフ トラバーサル ?グラフ トラバーサル (Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ の図を利用 ) knows 上記の例でノード 1 から出て” knows” という条件でエッジを移動し、ノード 2, 8 に入ります。このようにエッジの向きやエッジのラベルなどをもとにグラフ を移動することを「グラフ トラバーサル」といいます。
  • 4. グラフ トラバーサルを使ったリコメンデー ション リコメンデーションの例 (“The graph traversal pattern” (http://arxiv.org/abs/1004.1001/ )” Content-Based Recommendation に具体名を追加 ) feature 8 feature Goal 『江戸』 2 likes 6 resource person likes 『百日紅』 likes start feature 1 likes 3 likes 7 person resource person likes 『江戸名所図会』 4 feature 7 resource feature “( トラバーサル開始ノード ) –( エッジ :feature)-> ( ノード ) <–( エッ ジ :feature)- ( トラバーサル終了ノード )” という関係をノード 3 に適用すると 、ノード 2 がみつかります。
  • 5. グラフ DB ● グラフ DB の特徴 　?テーブルにデータを保存しない。グラフというデータ構造だけがあります。 　?ノードとエッジは隣接する頂点やエッジに直接の参照をもっているの で、 RDB でいう「結合」という操作の概念がありません。むしろ、データ構 造は定義されたエッジによって既に「結合された」状態です。 ● メリット 　?グラフトラバーサルのコストは、グラフの局所的な繋ぎ方 ( トポロジー ) に依 存する 　　→ 移動のコストは全体のグラフのサイズによらず、ほぼ一定になります。 ( た だし、局所的でないクエリ [ 例えばグラフ全体にまたがる最短パスを求めるな ど ] は遅いという印象です ) 　　　 cf. RDB での結合ではデータのサイズの増加にともなってクエリのコストも 増加する ● デメリット 　?シングルサーバーを超えてスケールするのは難しい。
  • 6. グラフ DB が有効な分野 ?ソーシャルネットワークデータのモデリング 　例 . Twitter でのフォロー、被フォローの関係や、ツイート?リツイ ートの関係 ?リコメンデーション ? PageRank ? RDB でいう Join を多く含むクエリーにも有効な場合があります。 グラフ DB は例えば Neo4j であれば 1 秒あたり百万トラバーサル以上 を処理できます。この場合、 1 クエリに平均 100 トラバーサルかか るとしても１万クエリ以上処理できます。
  • 7. Blueprints ? Blueprints はプロパティグラフモデル用のインターフェイスや実装、 API などの セットです。 ? Blueprints は異なるグラフバックエンドを交換することを容易にします。そのた め、ベンダーロックインを回避することが可能です。 ? Blueprints は人気のあるグラフ DB(Neo4j, OrientDB, DEX, InfiniteGraph) に対する コネクターをもっています。 ? Blueprints は人気のあるグラフフレームワーク (JUNG(Java Universal Network/Graph Framework 等 ) に対するコネクターをもっています。 ? Blueprints は GraphML や GML, GraphSON といったグラフ ファイルフォーマッ トを読み込むことができます。 ? Blueprints とその他の TinkerPop スタックは、 BSD ライセンスのオープンソース です。
  • 8. Blueprints の構成要素 ? Rexster: RESTful なグラフサーバーを実 現 ? Furnace: グラフアルゴリズムのパッケ ージ ? Frames: ノードとエッジをオブジェクト と関係に変換するオブジェクト - グラ フ マッパー ? Gremlin: Pipes にコンパイルされるグラ フ トラバーサル言語。 https://github.com/tinkerpop/blueprints/wiki/ より抜粋 ? Pipes: lazy( 遅延評価。結果が必要にな ったら処理を行う ) なグラフ トラバー サルを可能にするデータフローフレー
  • 9. Gremlin ? Gremlin はグラフ トラバーサル用の言語です。 ? Gremlin は Blueprints プロパティグラフモデルを実装するグラフデー タベースやグラフフレームワークの上で動きます。例えば TinkerGraph, Neo4j, OrientDB, DEX, InfiniteGraph, Titan, Rexter, Sail RDF Stores など。
  • 10. Gremlin の例 Gremlin の例 (Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ の図 ” Traversing vs. Pattern Matching” にメモ追記 ) goal start
  • 11. Rexster ? Rexster Rexster は REST にフォーカスしたグラフサーバーです。拡張によってサ ーチやスコアリング、ランク、リコメンデーションといった一般的な グラフトラバーサルをサポートします。 Rexster は Blueprints, Pipes, Gremlin を広範囲に使用します。 Rexster では以下のようなグラフ DB 上で動作します。 ? TinkerGraph in-memory graph ? Neo4j graph database ? OrientDB graph database ? DEX graph database ? Titan graph database ? Sesame 2.0 compliant RDF stores ( 引用元 https://github.com/tinkerpop/rexster )
  • 12. Pipes ? Pipes Pipes はプロセスグラフを使ったデータフローのフレームワークです。 プロセスグラフとはエッジで繋がった Pipe のノードから構成されま す。 Pipe はシンプルな計算のステップを実現しそれは他のオブジェ クトと結合して大きな計算を構成できます。それらのデータフロー のグラフによって、分割やマージ、ループ、一般的には入力からの データを出力に変換することができます。 ( 引用元 https://github.com/tinkerpop/pipes/wiki )
  • 13. グラフ DB のスケール性 従来のグラフ DB では、グラフのサイズ、処理能力が複数サーバーで スケールしないという大きなデメリットがあります。 ?複数のインスタンスにまたがるグラフデータというものが今まで なかった ?? → このデメリットを克服するために分散化グラフ DB の研究開発が進 められています。
  • 14. 分散グラフ DB ? Apache Hama: 行列、グラフ、ネットワークのための大規模な科学 計算用フレームワーク。 HDFS 上で動作します。 ? Pregel: Google の分散グラフ?プラットフォーム (closed) 。 BSP( バ ルク同時並列 ) という概念を基盤とします。 ? Apache Giraph: Hadoop 環境上で動作する Pregel の実装です ? Titan: Blueprints の関係者 (Aurelius) が開発を進めている分散グラフ データベース。現時点 (2012 Oct) では始まったばかりでバージョン も 0.1 です )
  • 15. Pregel ? Bulk Synchronous Parallel （ BSP 、バルク同期並列） ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
  • 16. Titan ? Titan は分散化グラフデータベースです。大規模なグラフを複数のマ シン上で処理することができます。 ?分散化のストレージとして、現在は Cassandra と HBase をサポート しています。 ? Titan はネイティブな Blueprints-enable なデータベースであり、すべ ての TinkerPop スタックをサポートします。
  • 17. Titan の利点 ? Titan は、シングルノードのサーバーが提供できる量を超えた容量と処 理能力を必要とするような巨大なグラフを処理することをサポートでき るように設計されました。これは Titan の基本的なメリットです。 【一般的な Titan の利点】 　?サーバークラスターにマシンを追加することによって、巨大なサイズ のグラフを分割して複数のインスタンスで使用できるようにします。 　?マシンをクラスターに追加することで、並列的なトランザクションを サポートします。 ( 複数マシンにまたがるグラフは並列化できないのか 調査中です ) 　?グラフトラバーサル用の言語 Gremlin をサポートします。 　? Rexster と容易に連携できます。
  • 18. Titan でキーとなるアイデア ? edge compression ( エッジ圧縮 ) Titan におけるエッジ圧縮は次のようなことを可能とするために様々な 手法によって構成されます。 ?それそれのエッジのメモリ使用量をできるだけ小さくすること ?すべてのエッジの情報を、連続したメモリブロックに格納すること 。 これらによってデータの取得を速くすることができます。 ? vertex centric query support ( ノード中心クエリのサポート ) Vertex centric queries allow users to query for a specific set of edges by leveraging vertex centric indices and a query optimizer. ( ノード中心のイン デックスとクエリオプティマイザーを利用することで、特定のエッジ の集合をクエリすることができます ) ? graph partitioning ( グラフパーティショニング ) アクセスされる頻度が高いデータが同じサーバー上に載るように複数 のマシンにグラフを分散させます。
  • 19. グラフパーティショニング ?グラフパーティショニング “Titan: The Rise of Big Graph Data” by Marko Rodriguez p.138 (http://www.slideshare.net/slidarko/titan-the-rise-of-big-graph-data)
  • 20. まとめ ?グラフ トラバーサル ? Blueprints ? Gremlin ?分散化グラフ DB ? Titan
  • 21. 参考文献 ?” The Graph Traversal Pattern”, Marko A. Rodriguez, Peter Neubauer, Apr 2010 http://arxiv.org/abs/1004.1001/ ? Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ ? Blueprints wiki https://github.com/tinkerpop/blueprints/wiki/ ? InfoQ “ グラフデータベース、 NOSQL 、 Neo4j” http://www.infoq.com/jp/articles/graph-nosql-neo4j ? Graph Pattern Matching with Gremlin 1.1 http://markorodriguez.com/2011/06/15/graph-pattern-matching-with-gremlin-1-1/ ? ODBMS Industry Watch “On Big Graph Data. ” http://www.odbms.org/blog/2012/08/on-big-graph-data/ ?” Pregel: A System for Large-Scale Graph Processing” http://www.slideshare.net/shatteredNirvana/pregel-a-system-for-largescale-graph-processing ?グラフ問題とバルク同期並列の常識を Giraph で体得 http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/01.html ? Titan: The Rise of Big Graph Data http ://www.slideshare.net/slidarko/titan-the-rise-of-big-graph-data ? Titan wiki https://github.com/thinkaurelius/titan/wiki ? ODBMS Industry Watch “On Big Graph Data.” http:// www.odbms.org/blog/2012/08/on-big-graph-data/
  • 22. BSP superstep (1) 以下のようなグラフで、東京から那覇への最小コストのパスを求める場合 （分散環境では、各都市の処理は異なったプロセッサで処理され、スケーラブル な構成になります）。 東京 1 6 ( エッジについている数字 9 は移動のコストを示しま す) 名古屋 1 大阪 福岡 2 那覇 3 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) を参考にしました
  • 23. BSP superstep (2) step1: 始点「東京」は隣接する「名古屋」、「大阪」、「福岡」に時間を送信 します。 東京 0 1 6 9 名古屋 大阪 福岡 那覇 ∞ ∞ ∞ ∞ ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
  • 24. BSP superstep (3) step2: ?名古屋では、現在値∞とメッセージの 1 より時間を「 1 」にし、隣接する大阪、福 岡へ「 1 ＋それぞれへの時間」を送信。 ?大阪では、現在値∞とメッセージの 9 より時間を「 9 」に更新します。 ?福岡では、現在値∞とメッセージの 8 より時間を「 8 」にし、隣接する那覇へ「 6 ＋そこへの時間」を送信します。 東京 0 1+1 6+2 名古屋 大阪 福岡 那覇 ∞→1 ∞→9 ∞→6 ∞ 1+3 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
  • 25. BSP superstep (4) step3: ?大阪では、現在値「 9 」とメッセージの 2 より時間を「 2 」に更新します。 ?福岡では、現在値「 6 」とメッセージの 4 より時間を「 6 」にし、隣接する那 覇へ「 4 ＋そこへの時間」を送信します。 ?那覇では、現在値∞とメッセージの 8 より時間を「 8 」に更新します。 東京 0 名古屋 大阪 福岡 4+2 那覇 1 9→2 6→4 ∞→8 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋
  • 26. BSP superstep (5) step4: ?那覇では、現在値「 8 」とメッセージの 6 より時間を「 6 」に更新し ます。 東京 0 名古屋 大阪 福岡 那覇 1 2 4 8→6 ※ “ グラフ問題とバルク同期並列の常識を Giraph で体得” グラフ問題に特化したバルク同期並列「 Pregel 」 (http://www.atmarkit.co.jp/fjava/rensai4/bigdata_java05/02.html) より抜粋