DSMS におけるデータと処理の分類

以下、DSMS における対象データの分類と、処理の分類を行う。

[対象データの分類]

構造化データの処理
- 株価データ (データ形式：　企業名、時刻、株価）
- 通信会社の通話記録 CDR (Call Data Record)（データ形式： Caller ID, Called ID, 通話時間 など）
- GPS データ (位置情報）: 携帯電話、車等 (データ形式：　デバイスID, 緯度、経度)
- DNA シ－ケンサーからの塩基配列 (データ形式: ATCG からなる 50～100の塩基配列)
- イベントデータ：　

非構造化データの処理
- テキスト（自然言語）: ブログ
- 音声
- 画像 (非圧縮画像 TIFF など)


構造化データと非構造化データの上記組み合わせ

[分析処理の分類]

軽量処理
- 平均、最大値、最小値 (SPADE の built-in オペレータで OK) ; Window 処理
- 判定処理: 到着データがある閾値である場合 (Functor 処理)

重量処理 (UDOP で書かれる)
- 異常値スコアの計算 (行列計算など.ただし、Sliding Window のサイズによっては非常に小さな行列を計算する場合もあり、軽いこともある）
- 塩基配列の Sequence Matching

プロダクティブリーダー養成講座

http://www.productiveleader.jim.titech.ac.jp/application/index.html

留学支援制度

以下の公募があるようです。
http://www.iad.titech.ac.jp/studyabroad/top

演習発表お疲れ様です

二人とも今日は英語で発表しました。お疲れ様！
英語の発表はまだまだ慣れないと思いますが、これを重ねていくと慣れていくはずですよ。頑張ってください！

CPU と GPU

以下の論文は、FFT (高速フーリエ変換) を CPU と GPU を並存して計算し高速化する話。なかなか面白いです。http://matsu-www.is.titech.ac.jp/paper/ogata/ogata-swopp2007-paper.pdf

新たなハードウェアを活用した研究の価値はどこに？

ソフトウェア分野において、未来永劫続くであろう研究テーマは、新たなハードウェアを活用したソフトウェアの研究であろう。 昨今、GPU, Cell やSSD を用いた研究が流行っているが、この種の研究の価値はどこにあるのでしょうか？

一つ冷静に考えないといけないことがあります。「単にそのハードウェア上に実装した（ポーティングとも言える）」では駄目。なぜなら、そこで得られた効果はそのハードウェアの賜物であるから。

研究とは、そこに世の中にとって役に立つような技術的な新発見、知見があって始めて価値が出てきます。

例えば、

「XX (新規ハードウェア）には○○の特性があり、普通の使い方では十分な性能が得られない。これを解決する技術として■という先行技術があるが～の欠点が存在する。我々は、これを解決する△という技術を導入し、～% の性能向上を達成した。」

というようなことが言えれば、ちゃんとした研究になりますし、査読つきの論文にもちゃんと通るようになります。

GPU を活用したデータストリーム処理

GPU を流体解析、分子動力学 (Molecular Dynamics)などの科学技術計算に応用した例は多く、データベースの分野ではクエリ処理に GPU を活用して最適化する研究などがある。

ただ、データストリーム処理に GPU を用いた論文はまだわずか。とりあえず見つかったものだけでも、以下の SIGMOD 2005 の論文のみ。 今年、来年にかけて大分この辺の研究が多くなっていくと思われます。

• Fast and approximate stream mining of quantiles and frequencies using graphics processors (SIGMOD 2005)

研究テーマ方針修正

卒業研究テーマの方針を若干変更。研究室の人数の関係上、あまり手を広げず、一つの分野にフォーカスした方が良いので、本年度はデータストリーム処理システム（ストリームコンピューティング）に専念したいと思いますが、いかがでしょうか？その方が、チームとして、知識の共有もできるでしょうし、一体感が出せると思います。

＃もちろん、将来的にデータストリーム処理システムと Hadoop などのバッチシステムとの融合は必ずや必要となることは疑いの余地がありません。

Load Shedding

最近、DSMS (Data Stream Management System、つまりストリームコンピューティングのこと) における Load Shedding 技術に注目していて、論文を読んだり、新たな手法を模索している。

Load Shedding で重要なのは、システムのキャパシティぎりぎりにロードを如何に保てるかと、間引いた後に出力の品質を如何に下げないかだ。大きく分けて２つ手法があるが、確率的にランダムに、入力タプルを落とす (Random Dropという) やり方と、データやアプリケーションの特性を生かした (Semantic Dropという）やり方がある。

いくつか論文を読んでいて 思いついたアイデアを列挙する。

(1) Semantic Load Shedding for Internet Search Queries
検索クエリの特性 (Zipf 法則)を生かした Semantic Load Shedding

(2) Compensating Load Shedded Data with Eventual Consistency
Load Shedding は基本的に間引いたものは捨てるのが普通。捨てないで、Bursty ではない状況の時に、あとから処理をするという手法もありなのではなかろうか。アプリケーションに依存するだろうが。。。分散システムの世界において、データの複製間の一貫性として Strong Consistency（常に２つの複製データの一貫性は保たれている）, Weak Consistency（一貫性が保たれていないこともある） そして、Eventual Constitency （最終的には保たれている）の3つがある。Load Shedding においても、この最後の Eventual Consistency の考え方が適応できそうだ。

(3) Efficient Load Shedding with GPU
GPU を用いた Load Shedding. これは Load Shedding というよりは Load Balancing に近い。非常に Bursty な状況では, CPU 処理ではなく GPU に処理をまかせる

(4) Load Shedding with Differential XML Processing
XML データの処理。Load Shedding に差分XML処理の技術を生かす. (WWW 2005 などの論文を参考にする)

ストリーム処理が必要なアプリケーションとは？

前回、グリッドとストリーム処理の違いについて述べたが、今回は分散アプリケーションの分類を行い、ストリームコンピューティングのパラダイムが必要なアプリケーションを明確にする。

(1) 疎結合型
　一つ一つのジョブの粒度が大きい、または、通信と計算をオーバーラップできるぐらいの粒度のジョブを伴うアプリケーショ ン。典型的な例としては、保険や金融分野おけるリスク計算（Black Sholes 方程式など）などに使われているモンテカルロシミュレーション、タンパク質の立体構造解析（グラフの同型性問題に落ちる）などが挙げられる。この種のアプリケーションは、 Latency が数百 msec にわたる広域の WAN 上に散在する計算機を束ねるグリッドなどでも動作可能である。また、昨今、Google や Yahoo などで使われている MapReduce や Hadoop などで動作するログ解析、クラスタ分析もこの範疇に入る。

(2) 密結合型

計算機同士が密に結合し、頻繁に通信を行う必要があるアプリケーション。たとえば、分子動力学法 (Molecular Dynamics) など、生体分子間の相互作用を加味し、化学反応を計算機上でシミュレーションするようなアプリケーションでは、計算機が頻繁に通信を行う必要がある。この種のアプリケーションは、低レイテンシの通信環境が求められ、各ノードが密に結合している必要がある。

(3) ストリーム型
(1), (2) は、本質的に長時間の計算量が必要なアプリケーションを並列度を上げることによって高速化するタイプのアプリケーションである。一方、ストリーム型は、全く別のタイプのアプリケーションであり、特徴としては、(a) 複数のセンサーから恒常的にデータが到着する (b) 到着データレートが変化し、Bursty な状況もある (c) (a), (b) のデータから即座にレスポンスを返す, の３つが挙げられる。(a), (b) のレスポンスを高速化するためには、前処理が必要であり、そのような前処理には (1) や (2) のようなアプリケーションが実行される場合もある。また、(1), (2) 同様にノード数を増やすことによって、レスポンスタイムやスケーラビリティを向上できるアプリケーションも多い。例としては、msec の反応が求められるアルゴリズムトレーディング、製造工程や医療分野におけるリアルタイム異常検知、サイバーセキュリティなどが挙げられる。

グリッドコンピューティングとストリームコンピューティングの違い

本質的な質問とは思えないが、グリッドとストリームコンピューティングの違いをよく聞かれるので、その回答を書く。

- 世間のグリッドの定義とグリッド研究者の定義は大きく異なる
(1) 世間は、多数のコンピュータを利用すればグリッド、ぐらいにしか考えていない
(2) グリッド研究者は、異なる管理ドメインにある組織上の計算資源を利用して巨大な
計算基盤を作るのがグリッドと定義している。これを実現するには、さまざまな レベルのHeterogeneity（OS, マシンアーキテクチャ、ネットワークなどの異種性) の問題を解かなければならない
- ただ、現実的には (2) のグリッドは、必ずしも実現しているとは言えず、(1) の 理解も認める必要がある

- 上記の (1) をグリッドと定義すると、グリッドは単にバッチ型の計算となる。リアルタイム性は気にすることなく、スループットを重視する。数理モデルのシミュレーションや、モンテカルロシミュレーションによる金融のリスク計算などシミュレーションが主な対象だ。

- グリッドとストリームコンピューティングの本質的な違いは以下の通りである。

• ディスクに格納 vs. オンメモリ上で処理：　グリッドなどバッチ型計算では、基本的にはデータを一旦すべて格納する。高エネルギー加速器から放出されるイベントデータはテラバイトにも及ぶが、これらの莫大なデータを貯めるために、他拠点のストレージを透過的に統合するデータ処理基盤を提供する。一方、ストリームコンピューティングは、データの受信と同時に処理をし、必要なデータのみを受信するか、必要なデータだけをディスクに格納することによって、データの爆発に対処する。
  
  
• スループット vs. リアルタイム性：　グリッドのようなバッチ型計算機とは異なり、リアルタイム性を重視する。また、グリッドにおけるジョブとは異なり、ストリームコンピューティングでは、常時データが流れ続け、かつデータのトラフィックが時間によって増減し、システムのキャパシティを越えるようなトラフィックが流れることもある。このように Bursty な状況でもリアルタイム性を如何に確保するかが Research Challenge でもあり、これがグリッドと本質的に異なる点である。

以上

授業

離散構造とアルゴリズムの授業で、3年生にシリコンバレーの話しをした。授業そのものよりも、興味を持ってくれて聞いてくれているのがはっきりわかった。是非、若者（自分も若いつもりだが）には、若いときだからこそできることをどんどん挑戦して欲しいと思う。

挑戦がたとえ、失敗に終わったとしても、それが確実に身になるはずなので。。。

ゼミお疲れ様です

第2回目の分散システムのゼミ、お疲れ様です。大変だったと思いますが、資料の出来はとってもよかったと思います。また、次回も頑張ってください。

XML データストリーム処理の性能最適化

近年、様々なデータの表現方法に XML が採用されている。XML はバイナリエンコーディングよりも、可読性やインターオペラビリティが高いという利点がある。しかし、一方、その冗長性 (開始タグ、終了タグを必ずつけなければいけない）がパフォーマンスの低下につながっていることが指摘されてきている。

WWW 2005 の論文 (Deltarser) では、XML 文書の類似性を利用した性能最適化手法が提案されている。データストリーム処理システムの入力データとしても、どうように、XML が入力として使われるので、Deltarser と同様の最適化手法が使用できるのではないだろうか。

卒論準備期間の意義

卒論は院試の後9月から本格的に始まるのだが、B4 の4月から7月までのこの準備期間はとても重要な期間。というのは、卒論に入ると、もういきなり最先端の研究に飛び込まなければいけないため、基礎的なことを勉強する暇はほとんどなく、修士に進むと更にそれを国際学会に通すために卒論の研究を発展させなければいけないので時間がない。

なので、いろいろ大変だと思いますが、今のこの時期は研究に携わる前の準備期間として非常に重要なので、頑張ってください。

18th WWW (World Wide Web) が スタート

スペインまでは直行便がないため、ロンドンのヒースロー空港経由でマドリッドに入ってきました。自宅を出てからホテルに到着するまで23時間。結構かかります。

WWW 2009 は, Web 系の学会のため、Yahoo や Google などの存在感が非常に大きいです。最近は、ユーザーの Web 上でのクリックの傾向を見て、広告の提示などを個々のユーザーにカスタマイズして出すようにしてきていますが、Click Stream という言葉を使うようになってきました。

我々、ストリームコンピューティングの研究グループとしては、さまざまな応用領域に役立つ研究をやっていきたいですが、この一つがこの Click Stream でしょう。

WWW 20周年記念

今年はWeb の20周年ということで、World Wide Web の創始者ともいえる Tim Berners-Lee 氏が来週スペインで行われる 国際学会WWW2009の基調講演でお話されます。CERN の http://webcast.cern.ch/でも実況中継されるようです。この講演に関しては、またここに書きます

民間営利企業における研究所の役割

民間営利企業における研究所の役割とは何だと思いますか？研究所の応募用紙のひとつの質問にこのようなものがありました。是非、時間があるときにでも考えて、ブログに書いてみてください。

まだ研究を始めてないので、想像でしか書けないと思いますが、研究を進めていくうちにその認識が変わっていくと思います。

IBM Smarter Planet University Jam 2009

来週 IBM では「IBM Smarter Planet University Jam 2009」という全
世界的な、大学・学生の方の間のオンラインディスカッションを企画しています。
よりよい地球、よりよい環境を作っていくにはどうしたらよいか、世界中の多くの
人と議論するチャンスです。ファシリテータとして本学の元教員である丸山さんも
参加します。ぜひ、一度はのぞいてみてください。

http://www-06.ibm.com/jp/software/academic/ur/ujam.html

研究環境の整備

研究環境の整備、いろいろとありがとうございます! 感謝、感謝です。

Subversion 関連に関しては、土曜日に見てみましょう。