Design patterns for efficient graph algorithms in MapReduce
Design Patterns for Efficient Graph Algorithms in MapReduce Jimmy Lin and Michael Schatz University of Maryland, College Park {jimmylin,mschatz}@umd.edu ABSTRACT Graphs are analyzed in many important contexts, includ- ing ranking search results based on the hyperlink struc- ture of the world wide web, module detection of protein- protein interaction networks, and privacy analysis of social network
Algorithms for calculating variance - Wikipedia
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values. A formula for calculating the variance of an entire population of size N is: Usin
Efficient Parallel Set-Similarity Joins Using MapReduce
Department of Computer Science University of California, Irvine Abstract In this paper we study how to efficiently perform set-similarity joins in parallel using the popular MapReduce framework. We propose a 3-stage approach for end-to-end set-similarity joins. We take as input a set of records and output a set of joined records based on a set-similarity condition. We efficiently partition the dat
MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介 - Preferred Networks Research & Development
どうも，実は今年から開発チームにjoinしていた中川です．可愛い犬の写真がなかったので，可愛いマスコットの画像を貼っておきます． 最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました．これはつまり，それだけ大量のデータをなんとか処理したいという要望があるからだと思います．しかし当たり前ですが，MapReduceは銀の弾丸ではありません． ということで，最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について，社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います． Bulk Sychronous Parallel このアルゴリズム自体は1990年に誕生したものです．長いのでBSPと書きます．さて，グラフから最短経路を求める時，MapReduceは使えるでしょうか？このような論文が出るくらいですから出来ないことはあ
MapReduce デザインパターン (6) - めもめも
"Graph algorithms" を考えます。 下図の S, A, B, C, D は 5 つの Web ページで、矢印は、Web リンクを表しているとします。（このような関係は、『有向グラフ』と捉えることができます。）このとき、ページ S からスタートして、最低、何クリックで、A 〜 D の各ページに到達するかを計算します。 ___________ ___________ ｜ ↓| ↓ Ｓ → Ａ → Ｂ → Ｃ ← Ｄ ↑____|↑__________|____↑ 再帰的な計算をごにょごにょすれば、何とかなる気がしますが（普通は、ダイクストラのアルゴリズムを使います）、MapReduce の場合は、基本的には『端から順番になめていく』タイプの計算しかできないので、次のように考えます。 1. 各ページの求める答えを（最初は不明なので）『？』と定義します。（S 自身は、不明で
2010-09-20
※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです. さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop などの並列処理に向かないかを書いていきます. 玉入れとリレー まずは比喩で話を進めていき, 並列処理に向いているアルゴリズムとそうでないアルゴリズムの区別を考えていきましょう. 運動会の種目から「玉入れ」と「リレー」という 2 つの競技を取り上げます. これらはどちらも団体でそれぞれ入れた玉の数やタイムを競うものです. ただし, 同じ団体競技でもその性質は違います. 玉入れは競技人数を増やせば増やすほど得点の期待値は上がります. 例えば, 10 人で玉入れをしているチームと 20 人で玉入れをしている
文系 Hadooper でも分かる Dijkstra アルゴリズム - cocoatomo衝動日記〈移行後版〉
今日の Hadoop ソースコードリーディングで Dijkstra アルゴリズムの知名度が低かったので, 解説を書いてみたぜ. このアルゴリズムを一言で説明すると? グラフ上のある始点からあるノードへの最短経路とその距離を求めるアルゴリズム. 用語が分かんないんだけど... グラフというと y = 2x とかを思い浮かべるかもしれないが, この場合の「グラフ」というのは「いくつかの丸 (= ノード, 節) を線 (= エッジ, 辺) でつないだもの」で, 状態遷移図もグラフの一種. 状態遷移図は「有向グラフ」と呼ばる. 丸と丸とをただの線ではなく矢印でつなぐので「有向」=「向きが付いている」と言う. "DAG" は "Directed Acyclic Graph" の略で「非循環有向グラフ」と訳される. "Directed" と "Acyclic" の順序が逆になってるのは気にせんでくれい
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Lightweight Trie
ダイクストラ法