データマイニングってこんなに大変なのか!?

現在のプログラムだと、8,000件の2次元データを処理するために、初期化で30分以上かかる。
そして初期化が終わると5分くらい。
データの書き出しにまた5分くらい。

10,000件だと1時間経っても初期化が終わらない。

原因ははっきりしていて、MST生成時にO(N^2)のコストをかけているから。
Primのアルゴリズムを使うとO(NlogN)までコストが下がるらしいので、勉強してみるか。。。

あと10,000件で1.5GBメモリを食うので、そしてメモリはN^2に比例するので、100,000件のデータを処理する為には150GBのメモリが必要。
DBに退避させる(クラスタにDBが必要)か、距離は適宜計算する(「現在の計算コスト*世代数*個体数」分の計算コストがかかる。今1時間かかってるとしたら、ざっと計算して1[hours]*200[generations]*50[solutions]=10,000[hours]かかる。10,000[hours]⇒1年以上)か。。。

まぁ確実に前者な訳だけど、だとすると500,000件のデータを扱うためにはDB用にHDDが3.75TB必要。

マジ?
Googleさんって1億以上のサイトをどうやって処理してるの??
1億って10,000の10,000倍...2次元の実数値データでも...150PB!?
GridとかHPCとかの次元でなんとかなるもんなの???

Read more