親子関係をもつデータの階層図を作成したい。

[wildrose]

お疲れ様です。
ＨＡＤＯＯＰビギナーです。

以下のような親子関係をもつＣＳＶファイルがあります。
このデータからデータの階層図を作りたいのです。
お勧め方法を教えていただきたいです。

階層は結構深いです。
例えば、あるサイトのＷＥＢページから参照先のＵＲＬを取り出した。
＃再帰呼び出しはまずないと前提。

（１）データ例
親 , 子リスト
---- ----------
001 002,003
002 003
003 004
・・・・

（２）結果例

001
|---002
| |---003
|
|---003
|---004
・・・

ＲＤＢ処理だとこんな感じです。

① 001を検索し、子リストを取得
select 子 from TAB1 where 親 = 001 ;
結果： 002,003 取得

② 子リストのデータをキー（002,003)として子リストを取得
select 子 from TAB1 where 親 = 002 or 親 = 003 ;
または
select 子 from TAB1 where 親 = 002;
select 子 from TAB1 where 親 = 003;

結果： 003,004 取得

③ 子リストのデータをキー（003,004)として子リストを取得
select 子 from TAB1 where 親 = 003 or 親 = 004 ;
または
select 子 from TAB1 where 親 = 003;
select 子 from TAB1 where 親 = 004;

結果： 004 取得
・・・

この繰り返し処理で階層関係を表示するためのINDENT番号を管理する。


例えば、ＨＢＡＳＥテーブルを以下のように作成し
ＲＤＢの検索方式と同じくキー検索を繰り返す。

こうした場合、
１row のキー検索の繰り返すだけなので、map/reduce を使った
分散処理は可能でしょうか？
簡単な疑似コードを教えていただければ幸いです。

create 'tab1','saki'

put 'tab1','001','saki:1','002'
put 'tab1','001','saki:2','003'
put 'tab1','002','saki:1','003'
put 'tab1','003','saki:1','004'
・・・・・

ーーーアプリ例ーーー
MethodA(String 親) {
・・・
Get get = new Get(Bytes.toBytes(親));
get.addFamily(Bytes.toBytes("saki"));
Result result = table.get(get);
NavigableMap map = result.getMap();

for(Entry columnFamilyEntry : map.entrySet()){
for( Entry ・・
for( Entry ・・・
MethodA( cellEntry.getValue() ) ; ◆繰り返す。
}

以上、よろしくお願いいたします。

[Sho Shimauchi]

はじめまして、嶋内と申します。
ご質問に対して、簡単にお答えいたします。

Hadoopは高スループットを出すことができますが、一回の処理ごとにオーバヘッドが発生するため
ある程度小さなデータの場合は使わない方が圧倒的に速くなります。
今回のように図示できる程度のサイズであればHadoopを使わない方がいいのではないかと思われます。

これは典型的なグラフ構造、DAGと呼ばれるものなので、
ドキュメントルートに相当するノードが1つしかないことが保証されていれば、
トポロジカルソートによりそのノードは必ず先頭に配置することができます。

例示していただいた構造はツリー構造なので、その方法で図示するのであれば
合流をどのように分割して図示するかはユーザ定義によると思います。
例示していただいたグラフのノード003はその典型例です。
これは 001 - 002 - 003 - 004 と一本につなげて表現することもできてしまいます。

残念ながら私はグラフアルゴリズムは専門外なので詳しくはわかりませんが、
同様のことをされている方は過去にたくさんいるはずですので、
何らかの参考書籍があるのではないかと思われます。
テキストにこだわらないのであれば、graphviz等のグラフ作成ツールと連携するのも一つの手です。

いずれにせよ、一度Hadoop(と、SQL)を使わないで処理する方法を検討していただけないでしょうか。
もしそれでもHadoopを使う必要があるのであれば、Data-Intensive Text Processing with MapReduce という本の5章が
グラフ問題に対するMapReduceアルゴリズムについて書かれている章ですのでそちらが参考になると思います。
http://www.umiacs.umd.edu/~jimmylin/book.html

以上、よろしくお願いいたします。

2011年4月8日15:36 wildrose <wildr...@gmail.com>:

--
---
Sho Shimauchi

[wildrose]

嶋内殿

いつもお世話になっております。
田と申します。

ご回答ありがとうございました。
教えて頂いたBOOKは以下のサイトからダウンロードし参照させて頂きます。

http://www.umiacs.umd.edu/~jimmylin/MapReduce-book-final.pdf

説明が足りなかったと思いますね。

実際、ＲＤＢで１００万行くらいの階層を作るくらいの複雑な関係で
親からの検索だけではなく、子からの検索もできるようにするロジックも必要です。
例えば、
003 を指定すると 001、002
004 を指定すれば 001、003 を求める仕組みも必要です。

データも変更や追加があり、バージョン管理も必要だし、
将来のデータの増加を考えて、分散バッチをもっと検討してみたいです。

ありがとうございました。
今後もよろしくお願いします。

On 4月8日, 午後5:26, Sho Shimauchi <sho.shimau...@gmail.com> wrote:
> はじめまして、嶋内と申します。
> ご質問に対して、簡単にお答えいたします。
>
> Hadoopは高スループットを出すことができますが、一回の処理ごとにオーバヘッドが発生するため
> ある程度小さなデータの場合は使わない方が圧倒的に速くなります。
> 今回のように図示できる程度のサイズであればHadoopを使わない方がいいのではないかと思われます。
>
> これは典型的なグラフ構造、DAGと呼ばれるものなので、
> ドキュメントルートに相当するノードが1つしかないことが保証されていれば、
> トポロジカルソートによりそのノードは必ず先頭に配置することができます。
>
> 例示していただいた構造はツリー構造なので、その方法で図示するのであれば
> 合流をどのように分割して図示するかはユーザ定義によると思います。
> 例示していただいたグラフのノード003はその典型例です。
> これは 001 - 002 - 003 - 004 と一本につなげて表現することもできてしまいます。
>
> 残念ながら私はグラフアルゴリズムは専門外なので詳しくはわかりませんが、
> 同様のことをされている方は過去にたくさんいるはずですので、
> 何らかの参考書籍があるのではないかと思われます。
> テキストにこだわらないのであれば、graphviz等のグラフ作成ツールと連携するのも一つの手です。
>
> いずれにせよ、一度Hadoop(と、SQL)を使わないで処理する方法を検討していただけないでしょうか。
> もしそれでもHadoopを使う必要があるのであれば、Data-Intensive Text Processing with MapReduce という本の5章が
> グラフ問題に対するMapReduceアルゴリズムについて書かれている章ですのでそちらが参考になると思います。http://www.umiacs.umd.edu/~jimmylin/book.html
>
> 以上、よろしくお願いいたします。
>

> 2011年4月8日15:36 wildrose <wildros...@gmail.com>: