[StreamGraph] Proximity Tracking on Time-Evolving Bipartite Graphs

Hanghang Tong, Spiros Papadimitriou, Philip S. Yu, Christos Faloutsos, Proximity Tracking on Time-Evolving Bipartite Graphs, SDM 2008, Atlanta, USA. [PDF]   Best paper award

http://www.siam.org/proceedings/datamining/2008/dm08_64_Tong.pdf


Given an author-conference network that evolves over time,
which are the conferences that a given author is most closely
related with, and how do they change over time? Large
time-evolving bipartite graphs appear in many settings, such
as social networks, co-citations, market-basket analysis, and
collaborative filtering.
Our goal is to monitor (i) the centrality of an individual
node (e.g., who are the most important authors?); and
(ii) the proximity of two nodes or sets of nodes (e.g., who
are the most important authors with respect to a particular
conference?) Moreover, we want to do this efficiently and
incrementally, and to provide “any-time” answers. We propose
pTrack and cTrack, which are based on random walk
with restart, and use powerful matrix tools. Experiments on
real data show that our methods are effective and efficient:
the mining results agree with intuition; and we achieve up to
15∼176 times speed-up, without any quality loss

[StreamGraph] グラフアルゴリズムの GPU による高速化

Accelerating large graph algorithms on the GPU using CUDA
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf


fast GPU algorithm for graph connectivity
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5470817

Collaborative Filtering with Temporal Dynamics

http://research.yahoo.com/pub/2824 こちらも必見

Collaborative Filtering with Temporal Dynamics
Authors:
Koren, Y.
Source:
KDD 2009, ACM, Paris, France (2009)
Abstract:
Customer preferences for products are drifting over time. Product perception and popularity are constantly changing as new selection emerges. Similarly, customer inclinations are evolving, leading them to ever redefine their taste. Thus, modeling temporal dynamics should be a key when designing recommender systems or general customer preference models. However, this raises unique challenges. Within the eco-system intersecting multiple products and customers, many different characteristics are shifting simultaneously, while many of them influence each other and often those shifts are delicate and associated with a few data instances. This distinguishes the problem from concept drift explorations, where mostly a single concept is tracked. Classical time-window or instance-decay approaches cannot work, as they lose too much signal when discarding data instances. A more sensitive approach is required, which can make better distinctions between transient effects and long term patterns. The paradigm we offer is creating a model tracking the time changing behavior throughout the life span of the data. This allows us to exploit the relevant components of all data instances, while discarding only what is modeled as being irrelevant. Accordingly, we revamp two leading collaborative filtering recommendation approaches. Evaluation is made on a large movie rating dataset by Netflix. Results are encouraging and better than those previously reported on this dataset.
Notes:
Won KDD'09 Best Research Paper award

[StreamGraph] Pregel: a system for large-scale graph processing

SIGMOD 2010で発表された Google の論文。必見。

http://portal.acm.org/citation.cfm?doid=1807167.1807184

Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs - in some cases billions of vertices, trillions of edges - poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.

有害 Tweet リアルタイム監視

データストリーム処理が応用できる例

http://japan.internet.com/busnews/20100831/5.html

"利用者のツイートが掲載される企業のキャンペーンページなどに無関係な宣伝や公序良俗に反するツイートが投稿された際は、リアルタイムでブロックしたり、メールでアラート"
"オプションで、ハッシュタグや一般キーワードの監視、商品購入を薦めるフレーズなどの自動ピックアップ機能"

DEDUCE: at the intersection of MapReduce and stream processing

System S のランタイム上で MapReduce 処理系を作った話。必見。

DEDUCE: at the intersection of MapReduce and stream processing
Proceedings of the 13th International Conference on Extending Database Technology 2010
Vibhore Kumar(IBM)

http://portal.acm.org/citation.cfm?id=1739120

[StreamGPU] Singular Value Decomposition for Collaborative Filtering on a GPU

協調フィルタリング用 特異値分解の GPU 用による高速化
----
Singular Value Decomposition for Collaborative Filtering on a GPU, 2010

A collaborative ltering predicts customers' unknown preferences from known preferences. In a computation of the collaborative ltering, a singular value decomposition (SVD) is needed to reduce the size of a large scale matrix so that the burden for the next phase computation will be decreased. In this application, SVD means a roughly approximated factorization of a given matrix into smaller sized matrices. Webb (a.k.a. Simon Funk) showed an e ffective algorithm to compute SVD toward a solution of an open competition called "NetixPrize". The algorithm utilizes an iterative method so that the error of approximation improves in each step of the iteration. We give a GPU version of Webb's algorithm. Our algorithm is implemented in the CUDA and it is shown to be effi cient by an experiment.


http://iopscience.iop.org/1757-899X/10/1/012017/pdf/1757-899X_10_1_012017.pdf

---

Collaborative Filtering 関連の参考論文

A Survey of Collaborative Filtering Techniques, 2009
http://www.hindawi.com/journals/aai/2009/421425.html

Yunhong Zhou, Large-scale Parallel Collaborative Filtering forthe Netflix Prize
http://www.hpl.hp.com/personal/Robert_Schreiber/papers/2008%20AAIM%20Netflix/netflix_aaim08(submitted).pdf

戦略的高性能計算システム開発に関するワークショップ

8月上旬に金沢で行われた「戦略的高性能計算システム開発に関するワークショップ」の資料が以下にアップされています。
http://www.open-supercomputer.org/workshop/

汎用並列分散処理基盤としての SPADE / System S

System S の処理系及び SPADE のプログラミングモデルは、元々、低レイテンシを第一の目的にするデータストリーム処理の基盤及び言語として設計されてはいるものの、実際にはスループットを最大化する汎用的な分散並列処理基盤として活用することができます。実際に、鈴村が関わっている商用システムの構築プロジェクトにおいては、そのような使われ方がされつつあります。

　このような使われ方はむしろ迎合すべきもので、後者の計算モデルをバッチ型計算モデルと呼ぶとすると、データストリーム処理モデルと同様のプログラミングモデルとしてシステムを記述することができる利点があります。また、研究としては、このような考えを元に SPADE というデータフロー型のプログラミング言語を捉えると、以下の2つのアイデアが浮かんできます。

1.「SPADE プログラムから CPU/GPU (or Multi-GPU) 上で効率的に稼動するコードを生成する技術」
関連研究は以下の論文でMapReduce プログラムを GPU 上で稼動させる研究です。
Mars: A MapReduce Framework on Graphics Processors by Bingsheng He , Naga K. Govindaraju

2.「MapReduce プログラミングモデルを SPADE プログラムにコード変換する技術」
MapReduce プログラミングモデルで記述されたコードは Hadoop だけでなく、汎用の分散並列処理基盤としての System S 上で実行することができようになります。

Ricardo: Integrating R and Hadoop

SIGMOD 2010 の Industry Truck に採択された IBM Almaden の論文。

Ricardo: Integrating R and Hadoop (URL)

Sudipto Das University of California, Santa Barbara, USA
Yannis Sismanis IBM Almaden Research Center, San Jose, USA
Kevin S. Beyer IBM Almaden Research Center, San Jose, USA
Rainer Gemulla IBM Almaden Research Center, San Jose, USA
Peter J. Haas IBM Almaden Research Center, San Jose, USA
John McPherson IBM Almaden Research Center, San Jose, USA

[StreamScale] 実装時の参考文献、参考技術

[スケーラビリティ]
- Doug Lea による Java NIO を用いたサーバーサイド実装のスライド "Scalable IO in Java"
http://gee.cs.oswego.edu/dl/cpjslides/nio.pdf

- JDK 6 の NIO パッケージの新機能 http://download.oracle.com/javase/6/docs/technotes/guides/io/enhancements.html#6
java.nio.channels.SelectorProvider クラスの実装が、Linux Kernel 2.6 から導入された epoll システムコールを使用するように書き換えられている

- Distributed computing using Java: A comparison of two server designs

- NPTL (Native Posix Threading Library) : POSIX スレッドのアプリケーションをOS レベルで効率的に動作させる機能。Linux Kernel 2.6 以降から導入されたが、Java の Non-Blocking IO などの必要不可欠性が薄まりつつある可能性もある

[コンポーネント化]
- Apache Cocoon: Spring ベースのソフトウェアコンポーネント化ライブラリ。Matt Welsh の SEDA (Staged Event Driven Architecture) を踏襲. OSGi とも類似している

[StreamSR] 国際会議

国際会議ですが、マルチメディア系の分散並列処理関係の会議に出すのが適切ではないかと思います。以下、候補ですが、アップデートする予定。どの会議に出すかは吟味するとして、次のテーマに移るべく9月中旬までには英語化を完成させましょう。

DASFAA 2011 (投稿予定日：9月中旬, 12月10日採択通知）

ICME (International Conference on Multimedia & Expo) （投稿予定日：2011年1月）
http://www.icme2010.org/dates.html (ICME 2010)

DMS (International Conference on Distributed Multimedia Systems) (投稿予定日：2011年3月30日）
http://www.ksi.edu/seke/dms11.html

DASFAA 2011

松浦君の StreamDS の成果を以下の国際会議に投稿予定
http://www.cintec.cuhk.edu.hk/DASFAA2011/index.html

インターン報告会

　Ｍ浦君のインターン報告会。行った課題も研究室のテーマに関連しており、かつ彼のこれからの研究プロジェクトにも強く関連してくるので、非常に良いインターンだったのではないでしょうか。特に M1 のうちに、こういう経験をすることは非常に重要です。

IBM SUR Award

　本年度、我々の研究室が IBM の SUR (Shared University Relationship) Award という賞をもらうことが決定し、サーバー機器が贈呈されることになりました。日本からは2件の受賞です。

SWoPP 2010

HPC (High Performance Computing), OS（Operating System) , Arch （計算機アーキテクチャ）分野の研究者が毎年一同に会する学会 SWoPP 2010 に参加してきました。我々の研究室からの参加者は、鈴村と上野君。HPC 研究会の前半は特に GPU 関連の研究が非常に多くありました。

鈴村は BoF セッションでのパネリストとして参加。特に昨今、博士課程に進学することを非常に間違った解釈でとらえている人がいるので、そのような学生向けに、民間企業の研究所の立場としてお話ししました。前に3年生の授業で話したことがありますが、もし興味があったらいつでも話します。

データストリーム処理におけるメモリ消費量を考慮したジョブスケジューリング

　データストリーム処理のアプリケーションでは、Aggregate(条件にマッチするまでメモリ上に蓄えられる) や Join (複数ストリームの待ち合わせ) など、オンメモリ上にデータを蓄えて処理するような処理が必要になるものがある。このとき、Split オペレータなどによってデータのある属性のハッシュ値を元にデータを並列ノードに分散させる場合、データの偏りが生じ、物理メモリを使い果たす場合がある。例えば、CDR 処理においては、ある特定のユーザーの通話履歴が極端に多い場合、そのユーザーのハッシュ値を担当する物理ホストのメモリ量では賄い切れなくなる。このような問題に対応する為、実行時にデータの偏りとメモリ使用量を定期的に監視し、負荷の均衡が保たれなくなった場合には、負荷を実行時に動的に均等にする機構が必要となる。

　実行時に動的に均衡を適正に保つ上で、いくつかの条件を満たす必要があるが、その例を次に示す。

- 溜めていたデータはロスしてはならない。すべての溜めていたデータは正しくマイグレーション先に送られる。マイグレーション先への負荷を最小限に留める。

- データは留め止めなく流れてくるため、上流のオペレータのバッファで滞留しないように、瞬間的にマイグレーションできなければならない

[StreamDS] 論文投稿完了

松浦君が COMSYS 2010 に論文投稿を完了しました。大変お疲れ様です。結果はただ待つのみですが、どちらにしてもやり残したことがいくつかあると思うので、インターンが終了したら少し整理していきましょう

[StreamCloud] 関連論文

先日フロリダで行われた国際学会 Cloud 2010 で、StreamCloud プロジェクトに関連するであろう論文一覧です。詳細はhttp://www.thecloudcomputing.org/2010/IEEE-ICWS-SCC-CLOUD-SERVICES-AdvanceProgram.pdfを見てください。

- Understanding Performance Interference of I/O Workload in Virtualized Cloud Environments (CLOUD2010-3007), Xing Pu
- Performance Measurements and Analysis of Network I/O Applications in Virtualized Cloud (CLOUD2010-3008), Yiduo Mei
- Integrating Resource Consumption and Allocation for Infrastructure Resources On-Demand (CLOUD2010-3010), Ying Zhang
- Mining Twitter in the Cloud: A Case Study (CLOUD2010-3014), Pieter Noordhuis
- Maximizing Cloud Providers' Revenues via Energy Aware Allocation Policies (CLOUD2010-3017), Michele Mazzucco
- Workload Migration into Clouds . Challenges, Experiences, Opportunities（CLOUD2010-3020), C. Ward
- Performance and Power Management for Cloud Infrastructures (CLOUD2010-3042), Hien Nguyen Van
- Optimal Resource Allocation in Clouds (CLOUD2010-3053), Fangzhe Chang
- Fault Tolerance Middleware for Cloud Computing (CLOUD2010-3009), Wenbing Zhao
- Using Cloud Technologies to Optimize Data-Intensive Service Applications (CLOUD2010-3003)
Dirk Habich

新たなデータストリーム処理系を作る動機

　今年後半から、研究室発のデータストリーム処理系を設計及び開発していこうと思いますので、そろそろ概要設計ぐらいには取り掛かりたいと思います。

　処理系の実装の動機は「System S のランタイム周りの制約から離れたい」というのが大まかな動機です。例えば、現在感じているだけでも以下のような制約があります。

(1) ランタイムの制御、特にスケジューラ周りに手を入れられなく、その周辺の研究に手を出しにくい。たとえば、今のスケジューラは CPU 使用率しか見ていませんが、メモリ使用率やリソース（データベースなど）の局所性を生かした作りになっていません. オペレータの最適配置問題を最適化問題に落として解こうと思っても、その結果をランタイムに反映できません

(2) 高信頼性（つまり必ずデータロスはない）を実現するデータストリーム処理系を実装するには、現在は、System S の外でその機構を作らないといけません。ランタイム自身にその機構を加えることができるはずです。

(3) 鈴村の SYSTOR 2010 で発表した論文では、入力データの自動分散化がスケーラビリティを出すには重要と書きましたが、System S でも強引にやればできますが、自然な形でランタイムでその機構が作れるはずです。

(4) システム自身が様々なパッケージに依存しており、「Write once, run anywhere」 ではありません. Amazon 上で動かしたり、TSUBAME などの巨大クラスタ上でスケーラビリティテストをやりたくてもできません。

　実装言語は Javaにします. 性能は多少犠牲にしますが、プラットフォーム独立性や開発生産性およびメンテナンス性を考え, Java で実装します。特に金融のようなマイクロ秒で勝負するような処理系を作ることを目的にしていないため、レイテンシなりスループットが少し下がっても問題ないでしょう。また、GPU との親和性は当然悪くなり、JNI 経由呼び出しになります。その代わり、Python や Ruby, PHP と言ったスクリプト言語の処理系も JVM ベースのものが最近はあるため、UDOP に相当するようなユーザ定義オペレータをそれらのスクリプト言語でも記述することも当然可能になります。

ただ、最後に断っておきますが、当然、System S も併用していく予定です。ストリームマイニングやアルゴリズム周りの研究、そして GPU との統合は System S 上でも可能なはずです。

論文締め切り

　研究室メンバーのそれぞれの学会の締め切りが近づいてきました。Internet Conference 2010 と Comsys 2010、それぞれ査読つきなのでそれなりのまとまりが必要ですが、頑張っていきましょう。

「タブレットコンピューターとそれを取り巻く産業構造に係る最近の動向」

「タブレットコンピューターとそれを取り巻く産業構造に係る最近の動向」
http://www.ipa.go.jp/about/NYreport/201006.pdf

[StreamTwitter] 2010年6月の Tweet 数解析

6月1日から6月30日までの Tweet 数がすべて取れたので、再度解析しました。前回と同様に日本語の Tweet のみを抽出しています。

結果として面白いのは、20214番目のデータ(1単位は1分）で通常のピーク数よりも3倍の Tweet 数が見られ、Bursty なデータが見て取れるということです。20214番目は、6月14日あたりということですが、これはワールドカップで、日本とカメルーンが対戦した日です。

解析ですが、NFS がボトルネックとなるので、st01 のみの4コアで計測し、3時間程度で解析が終了しました。st01-st08 まで8台あるので、入力データ及び出力データをうまくローカルディスクを利用しながら解析すれば30分台で解析できるはずです。



以下は、そのバースト時が起きた時刻を中心とした1時間のデータ。



以下、6月10日から6月30日までのグラフ。バーストが何回か起きていることが見てとれる。

[StreamTwitter] べき乗則に従う Twitter のリプライ回数の頻度

1ヶ月の Twitter の返信頻度を System S / SPADE で解析した結果、べき乗則に従うことが見てとれる。

X軸はリプライの回数。Y軸は頻度を対数にした数値。用いたデータは4月中のほぼ1ヶ月のデータ。最大返信数は197．平均は 3.874 回、中央値は 3 回。

Twitter ログ解析 4/1 から 4/26 の１分間単位の Tweet 数の変遷

Twitter ログ解析 4/1 から 4/26 の１分間単位の Tweet 数の変遷

最大値：811
最小値：1 (怪しい）
平均値：241.82
中央値：235
標準偏差：112.37

以下、任意の3日間を切り出したときのグラフ





以下、ヒストグラム。X軸は 1分間のTweet 数。

講演＠NEC 中央研究所

　NEC中央研究所からの依頼で、「ストリームコンピューティングの最新動向」と題して、講演してきました。研究室からは、雁瀬君、石井君、そして徳田研の Li さんも来てくれました。結構、活発に質問してくださったので、こちらも非常にしゃべりやすかったです。やはり、「質問力」は重要ですね。あういう場できっちりと質問しているできる人こそ、社内での立場が良くなります。

　

　ところで、ブログ、ほぼ1ヶ月更新していない人がいますが、更新してください。

博士課程に進学するということ

たまには、研究以外のことも書きます。

博士課程に進む、ということはちゃんとした信念を持って進めば良いことだと思います。私自身は、修士から博士課程への進学を決めなければいけないときにちょうど米国に研究留学中でした。そもそもアメリカにそのまま残ってUSのシリコンバレーでの就職を目指していた私でしたので、鼻から博士課程など考えていませんでした。しかし、USでの就職というのは、Ph.D 、つまり博士号を持っているか持っていないかで、圧倒的に博士号を持っている方が有利ですし、格段に年収の差が出てきます。それと、USで研究していた研究テーマが SuperComputing という HPC (High Performance Computing) 系では競争率の高い国際会議に採択された、というのも大きな自分への勇気付けにもなったのですが、そんなこんなで、博士課程への進学を決めました。そんな人生の選択をせまられていた時期が、皆さんとあまり大差ない歳だったかと思います。

　博士号を取るということは決して簡単なことではないと思いますが、一番のメリットは、修士で企業に就職して習得できないことが、若くて吸収力のある3年間のうちに得られるということだと思います。ほとんどの企業がトップダウンに戦略を決めていくので、修士で入ってしまうと、その中で決められたプロジェクトに上から言われるがままに遂行するだけで、自らの発想力、プレゼンテーション能力、グローバルに活躍する素養などを身に着ける余裕などありません。しかし、それがある時、必ず必要になってくるのです。私自身、企業に勤めて、修士で入ってくる人材と博士で入ってくる人材を見ますが、格段にそれらの違いがあると感じます。

　ただ、一つだけ注意しなければいけないのは、ちゃんとしたビジョン、3年間で成し遂げておきたいことをしっかり持って博士課程に進まないと、これは逆に良くありません。これらを見極めるというのが、4年生の後半から M1 の冬ぐらいまでだと思います。企業の良し悪し、アカデミックの良し悪し、を私は幸いにも十分に感じています。各自、十分に考えて周りに流されず、進路を考えていってください。

ICDE 2010 勉強会

データベース系の会議 ICDE 2010 の勉強会で、研究室の学生5人が発表しました。大変、お疲れ様でした。http://qwik.jp/icde2010readings/

[論文紹介] Operator Placement Optimization

Query-Aware Partitioning for Monitoring Massive Network Data Streams, Theodore, (AT&T Labs)

[論文紹介] High-Availability Algorithms for Distributed Stream Processing, ICDE 2005

High-Availability Algorithms for Distributed Stream Processing, Jeon-Hyon Hwang, Micheal Stonebraker, ICDE 2005

データストリーム処理システムの耐故障性 (Fault Tolerance)、高可用性 (High Availability) に関する論文。かの有名な Micheal Stonebraker 等のグループの研究。データベース周辺ではこのような FT / HA に関しては既に様々な研究、技術が存在するが、この論文ではじめて、データストリーム処理システムに関する適用が試みられている。

当然、アプリケーションが要求するノードダウン時のデータ損失の影響度合いによるのだが、一般的に、当論文では、３つのリカバリーモデルが存在すると述べている。Precise Recovery, Rollback Recovery, Gap Recovery. いずれも、プライマリーサーバー、バックアップサーバーの２つを仮定しており、プライマリが落ちたらバックアップサーバーに処理を委譲。プライマリとバックアップのステートを常に同期させることも考えられるが、ランタイムへのオーバーヘッドは多大なものになる。よって、このオーバーヘッドを少なくするために、以下の３つのモデルを列挙。

• Precise Recovery: 一時的に処理の応答時間は増えるが、Failure を完全に排除し、結果にも影響を与えない。金融、証券系では必須
• Rollback Recovery: 入力データのデータリカバリまでは保証するが、出力する計算結果が完全に一致するとは限らない。プライマリとバックサーバーノードの２つがあり、バックサーバーで再処理させた場合に結果が異なることを許す
• Gap Recovery: 最もリカバリー保証がゆるい方式で、結果に影響を与えない古いデータは破棄し、ランタイムへのオーバーヘッドやリカバリーのスピードを高速化する方式

また、上記のモデルを実現するアプローチとしては以下の方式を提案

• Amenesia: ランタイムへのオーバーヘッドを与えずに Gap Recovery を実現
• Passive-Standby: プライマリはセカンダリ（バックアップ）に定期的にステートを送信
• Active-Standby: セカンダリはすべてのタプルを並行して処理
• Upstream backup: アプリケーション上の下流のノードが落ちた際には、上流のノードが、ログに一時的に保存しているタプルを再送信

4番目の Upstream Backup がユニークであろう。詳細は論文を。