2011年7月14日木曜日

Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space


Yaniv Loewenstein1,∗, Elon Portugaly1, Menachem Fromer1 and Michal Linial2,

蛋白を階層クラスタリング。
ポイントは距離がすべての蛋白の間に定義されるわけではないこと。
また、三角形の1辺は2辺の和より短い、という法則が成り立たないこと。

この前提ではcentroidが定義できない。kmeansのような方法も使えなさそう。。。

メモリに乗る範囲で何とかやる方法を提案している。
距離でソートして、短いほうからメモリに乗る範囲で載せて、上限と下限でしばりながら
クラスタリングを行う。これをなんどか繰り返す。

並列化は非常に難しそう。簡単に出来る方法は思いつかない。

2011年7月5日火曜日

An Efficient Hierarchical Clustering Method for Large Datasets with Map-Reduce

Tianyang Sun, Chengchun Shu, Feng Li, Haiyan Yu, and Lili Ma, Yitong Fang
1.2T 1million user 6時間
テキストの分類。前処理とクラスタリングにそれぞれMRを使用。
クラスタリングは3回のMRで。
なんか肝心な部分をmasterノードでon memoryでやっている。
あと、ある程度近いものを有無を言わさずペアにしているようだが、厳密には
これではまずいはず。

A New Agglomerative Hierarchical Clustering Algorithm Implementation based on the Map Reduce Framework

Hui Gao, Jun Jiang, Li She, Yan Fu 中国 uestc.
文書の分類。neuron initialization とか言ってるな。。分割してクラスタリングしたものを
後でアグリゲートしている?ただしその方法については書いてない。

2011年7月4日月曜日

Divisive hierarchical clustering

というのは、上流からどんどん分割していく方法。具体的にはKMeansをつかって2分割し、分割されたモノにまたKMeansを適用して、というようにやるようだ。
KMeans がm段で収束するとして、分割の深さを log2Nとすると m * log2N段のMRをやることになる。
実装的には複数のKMeans を同時にやる用にしないといけなさそうで、割に大変っぽい。まあやればできそうだが。問題はこのようにして求めた階層クラスタが要件にあうのかどうかだ。

MrsRF: an efficient MapReduce algorithm for analyzing large collections of evolutionary trees

Suzanne J Matthews and Tiffani L Williams Department of Computer Science and Engineering, Texas A&M University, College Station, TX URL
何をやってるかというと、大量の進化木を比較してそれぞれの間に距離を定義したマトリックスを作ろうとしている。距離の定義は、木をリーフ以外の枝で切断してできた集合を比較することで行う。同じ集合対を与える切断があると1点、と言う具合に加算していく。
でこれを2段のMRでやっている。割にストレートフォワードかもしれない。
Phoenix を使ってる。Phoenixはshared memory の実装なので、注意が必要。
RFは Robinson-Foulds distanceを意味している。OpenMPIも使ってる。
HashRFという方法を改良している。
基本的に進化木の比較に特化して、n^2のマトリクスをハッシュを使って作る。
ローカルにはMapper内部でOpenMPIを使い、グローバルにはMRを使ってハッシュを集計している。

2011年6月10日金曜日

MapReduce 2011

Otus: Resource Attribution in Data-Intensive Clusters CMU
   monitoring / analyzing MR jobs
  ジョブなどのCPU/Memory/Disk利用状況を分割して表示。
  Mochi という Hadoopのvisualizerがあるようだ。
  
  Hadoop はJMX で情報を出している。これと/procからの情報などを
  ノード毎のCollectorに集めて、それを中央のAggregatorにあつめて
  Storage Backendにいれる。 
  - RRDToolを使っている。OpenTSDBに移行するよてい。
   メタデータはrrdのパス名にエンコード。うーん、無理がある。

  - JVM reuse は使い回すが、すぐに使われない場合があって結構危険
  - 失敗した Hadoop streaming job がクリーンナップされなくて
    仮想メモリを食いつぶすことがある。
Phoenix++: Modular MapReduce for Shared-Memory Systems
shared memory machine でon memory  でMR.を行うPhoenix シリーズ,
1,2ときて最新版が++ 。OpenMPの代用としてつかうようなもの。
  オリジナルの問題点
   - hash が固定長
   - combiner がmapの後にしか走らない
   -  
    Metis というのもある。

   modular storage 
    KV の性質はいろいろある。 *:*, *:K, 1:1。それぞれにたいしてコンテナを容易
 
   C++ テンプレートとinline 展開を用いてループオーバヘッドを削減。
Static Type Checking of Hadoop MapReduce Programs
   Hadoopでの型違い問題をstaticに解決。たしかにHadoopで実行時にエラーがでるのは
  非常にむかつくので有意義かも。
INRIA のBlobSeer のKeynote
  Google のGreg Malewicz が  Beyond MapReduceというすごく面白そうな
  Keynoteをする予定だったのだけど残念ながらキャンセル。かわりに
  INRIAの名前失念さんがBlobSeerに関するおはなしを。
   HDFSをBlobSeer上に実装、というところだけがつながりか?

   ANLとかといっしょにやってる? ARPEGE Call ってなんだ?

   AzureBrain? BlobSeer on Azure を使ってBrain とneuroを一緒に解析
 
Tall and Skinny QR Factoriazations in MapReduce (from sandia)
 500,000,000 by 100 matrix 423.3 GB HDFS 
 極端に細い行列のQR Factorization.

 カスケードしたいくつかの行列積に分割している。
Rapid Parallel Genome Index using MapReduce.
  DNA sequencingのための
  suffix arrayの生成をHadoopで。 - BWT (Burrows Wheeler Transform)
  EC2でやってるな。
  cloudburst, crossbow, Quake, Contrail 
Full-Text Indexing for Optimizing Selection Operations inLarge-Scale Data Analytics
Twitterのはなし。 Lucene をつかってindexして、Hadoop で探す。
  Jimmy Lin (Qatar であった) Twitter
Exploring MapReduce Efficiency with Highly-Distributed Data
  分散環境でHadoop。データの配置、通信をおこすタイミングをshuffleにしたりmapの
  前にしたりして、実験。ごくごく当たり前の結果。やらんでもわかるだろ。
  という感じも。
Parallelizing large-scale data processing applications with data skew: a case study in product-offer matching
MSインターンでやった内容だそうだ。
  Data skew とは?
  Product Offer Matching - 商品の名寄せ。
   機械学習をつかっている。training をする。
 

2010年11月29日月曜日

ComSys 2010@大阪

 ●招待講演1 [13:15~14:15] 60分      座長:阿部洋丈(阪大)
   (1) 新世代ネットワークで変わるICT研究
       下條真司 (NICT)
各国のネットワーク研究の現状を紹介。日本では今後どちらの方向にいくのか。
 ●一般講演1:仮想マシン(1)[14:35~15:45]70分      座長:光来健一(九工大)
   (2) 仮想マシンモニタによる透過的ネットワークブート方式 【若手優秀論文賞】
       表 祐志,品川 高廣,加藤 和彦(筑波大)
ストレージのみを集中管理した環境を作るのが目的。 ネットワークブートを透過的にするために、デバイス類はパススルー、仮想ディスクだけはトラップして ネットワークディスクで提供、ということ。SACSISのポスターでみたような。ATA over Ethernet.
ネットワークドライバは、パススルーなのに、ATAの転送も食わせるので、ここが一番大変そう。 ブート前とブート後で挙動が違うらしい。
 
   (3) 準パススルー型仮想マシンモニタへのマルウェア検出機能の拡張 (S)
       Tran Truong Duc Giang,大山 恵弘(電通大),忠鉢 洋輔,
       品川 高廣,加藤 和彦(筑波大)
 
アンチウィルスソフトをBitvisorレベルでやる、というはなし。VMMでやるという話はたくさんあるのだけど、 これは、ハイパーバイザ型なところが違うとうのこと。
 ●一般講演2:分散システム[16:05~17:05]60分      座長:高野了成(産総研)
   (4) DTS: Broadcast-based Content-aware TCP Connection Handover
       Fujita Hajime,Ishikawa Yutaka(The University of Tokyo)
   (5) データストリーム処理系System SとHadoopの統合実行環境 (S)
       松浦 紘也,雁瀬 優(東工大),鈴村 豊太郎(東工大/IBM)