[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 がユニークであろう。詳細は論文を。

時空間データベースに関する論文

Geotagging with Local Lexicons to Build Indexes for Textually-Specified Spatial Data, Michael, D. Lieberman (University of MaryLand), ICDE 2010,

インターネット上の記事などから地名データを抽出し、周りのコンテキスト情報からその地名データをほぼ正確に緯度、軽度に変換するための手法を提案。昨今、写真共有データベースの Flickr などでは、写真に位置情報を付与するサービスを提供しているが、それよりも更に難しい問題に取り組んでいる。

C3: Concurrency Control on Continuous Queries over Moving Objects, Jian Dai, ICDE 2010

GPS や RFID など常に移動し続けている移動物体オブジェクトの位置情報を管理し、それに対するクエリを一貫性を保ちつつ正確な答えを返す lazy-update の方式を提案。空間データベースのインデックスとして良く使われている R 木 は覚えておくべし。

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

データストリーム処理のスケジューリングの研究では、System S のSODA や COLA などの論文において、主にＣＰＵやネットワークの通信量を見ながら全体のスループットを向上させる論文があるが、メモリ量を最小化するようなスケジューリング方式が以下の論文に述べられている。

------

Chain: Operator Scheduling for Memory Minimization in Data Stream Systems

Babcock, Brian and Babu, Shivnath and Datar, Mayur and Motwani, Rajeev (2003) Chain: Operator Scheduling for Memory Minimization in Data Stream Systems. In: ACM International Conference on Management of Data (SIGMOD 2003), June 9-12, 2003, San Diego, California .

データ工学研究会のプログラム

来週 6月28日、松浦君と森田君がデータ工学研究会で発表を行います。場所は名古屋大学です。以下、プログラム。

http://www.ieice.org/ken/program/index.php?mode=program&tgs_regid=47f142a95586bfa10dd18d213411b033e450b0214431c01668661d79fabe984e&tgid=DE&layout=&lang=

[StreamGreen] Google Map + 渋滞情報

[全力案内ナビ] ユビークリンク社 (野村総合研究所 NRI が 100% の会社。URL)

個々の走行車両の位置データから道路の混雑を生成。ユビーリンクと契約しているタクシー１２０００台と、全力案内！会員の位置情報から独自に生成。また、カーナビ用だけではなく、徒歩などのナビ（音声あり）にも使える。

http://rik.skr.jp/archives/2009/07/iphone_42.html

[Google が提供する　Google Map 上の渋滞情報]

http://jp.techcrunch.com/archives/20090825google-maps-will-now-show-you-traffic-conditions-on-the-back-roads/

Google Maps Navigation takes a mobile turn

http://news.cnet.com/8301-30684_3-10384544-265.html

ICDE 2010 論文読み準備

今週は、研究室全体で ICDE 2010 の論文読みをしています。結構、タフですが、有名な学会の論文の精読を何回かちゃんとやると、どのような論文が採択されるのかが、わかってくると思います。頑張りましょう。

[StreamGPU] 第72回全国大会優秀賞！！

森田君の論文が、第72回全国大会優秀賞・奨励賞選定委員で審議の結果、大会優秀賞 に選ばれました。おめでとうございます！http://www.ipsj.or.jp/01kyotsu/award/taikai_yushu/index.html

なお、表彰式は、次回の第73回全国大会（東京工業大学 大岡山キャンパス、2011.3.2-4）で行う予定だそうです。
http://www.ipsj.or.jp/10jigyo/taikai/73kai/index.html

[StreamSR] GPU による高速化

古井先生の「話し言葉音声の認識精度向上のために」という以下の論文の 5.3 章に GPU による高速化の話が少し述べられている。

http://www.furui.cs.titech.ac.jp/publication/2007/AI-Challenge.pdf

Internet Conference 2010

http://www.internetconference.org/

研究室からは以下の論文を提出したいと思います。

西井君: StreamSR の話

石井君：StreamCloud の話

こちらもがんばりましょう。

COMSYS 2010

COMSYS 2010 http://www.ipsj.or.jp/sig/os/index.php?ComSys2010

研究室からは以下の論文を出したいと思います。

- 松浦君＋雁瀬君 --> StreamDS の話

- 上野君 --> StreamGPU の話

7月23日が論文アップロード締め切りです。がんばりましょう。

[StreamCloud] Eucalyptus の内部アーキテクチャ

Eucalyptus の内部アーキテクチャに関して、もう少しどのようなアーキテクチャ構成になっているかを調べていきましょう。An Assessment of Eucalyptus Version 1.4 (PDF) は1年前のものなので、1.6.2 では大幅に改善されていると思いますが、少し参考になります。

- CLC (Cloud Controller), CC (Cluster Controller), NC (Node Controller) は Web Service として実装されており、WSDL (Web Service Description Language) が存在する。CLC-CC 間、および CC-NC 間はSOAP over HTTP で通信しており、eucalyptus.conf のデフォルト設定では、WS-Security が有効になっているので、暗号化して通信が行われている

- Amazon S3 (ストレージサービス） に相当する Walrus はどのように実装されているのでしょう。これも上記のドキュメントには Web サービスとして実装されていると記述されています。

- EMI (Eucalyptus 用のイメージ）の CC から NC への転送、NC 側でのキャッシングポリシー、そして、CLC/CC 側での元の EMI イメージとの同期方法がまだよくわからないので、これも調べてください。

English, English, English !

　今日は慶応大学からのM2 の学生が来て、英語のテクニカルトークをしてもらいました。どの研究分野でもそうですが、国際舞台で自身の研究が認められてこその世界です。英語を聞く機会はいろんな情報ソースもあるので問題ないと思いますが、しゃべる機会は英会話教室などにでもいかないとなかなかないと思うので、率先して研究室で作っていきたいと思います。

[StreamCloud] System S on Eucalyptus 1.6.2

Eucalyptus 1.6.2 を tesla (Cloud Controller と Cluster Controller) と st00 (Node Controller) にインストールし、System S が Eucalyptus から立ち上げた VM インスタンス上で動くことを確認しました。これでこのプロジェクトは一歩前進したと言えるでしょう。

エンジニアリングなシステム構築は見えてきましたが、これからしっかりと、リサーチ的な新規性を考えていかないといけないでしょう。

ちなみに、rpm ではなく、ソースをダウンロードしてみました。 メインのほとんどが Java で書かれていますね。Cluster Controller / Cloud Controller のスケジューラーの部分は未成熟だと Eucalyptus に書かれているので、その部分に手を入れても面白いでしょう。

[StreamXML] XML Stream 関係の論文

特に松浦君に関係しますので、High Performance XML Stream Processing with GPU のテーマに移ったら、以下の論文を読んでいきましょう。

• Efficient Processing of XML Update Streams, ICDE 2008
• Distributed XML Stream Filtering with High Scalability, ICDE 2005,
• XML Prefiltering as a String Matching Problem, ICDE 2008

StreamGreen プロジェクト

３年生向けの StreamGreen プロジェクトのキックオフミーティングが6/7(月)に行われます。非常におおまかにいうと、昨今コモディティ化しているiPhone などの スマートフォンを利用し、それらの位置情報を取得することで、リアルタイムかつスケーラブルな環境・交通モニタリングを行う社会基盤を構築する、というのがプロジェクトの趣旨です。

プロジェクトには複数人参加するので、各自責任を持ってできるように、以下のように役割分担をしていきたいと思います。

1. システムの全体構想を固める
   - プロジェクトの成功の条件は？
   - プロジェクトの出口は？
   - 類似の研究プロジェクトとの差異は？（新規性）
2. Stakeholder とのミーティングを行い、実用性、有効性を確認する
3. システムの全体設計
4. システムのコンポーネント化と詳細設計
5. 上記のシステムのうち、技術的な課題を洗い出し、研究テーマとしてくくりだす（一番重要）

Waterfall 型のシステム開発ではなく、Agile に進めていきたいと思います。まず月曜日は、再度プロジェクトの詳細を鈴村から説明し、その後、毎週のゴールを決めていきたいと思います。

Spatial Skyline Query Using Boronoi Diagram

Google Video が提供するビデオには、テクニカルなトークもあり、面白いです。

以下のビデオは、位置情報サービス（Location-Based Service) における Spatial なSkyline Queryに対応するために、ボロノイ図を利用する 研究発表です。

http://video.google.com/videoplay?docid=-2755539754474649930#

ちなみに、Google Map などの地図上で現在地がわかり、ユーザーは、”まずガソリンスタンドに行き、イタリアンレストランに行き、そして映画館に行きたい”というクエリをシステムに出すとします。 Skyline Query とは, これらの複数の条件を同時に満たすような結果(この場合には最短経路) を返すクエリのことをさします。

Must Submit !! SPSS 2011

締め切りは12月。来年は研究室から少なくとも1件はサブミッションしましょう。

International Workshop on Scalable Stream Processing System 2010

http://research.ihost.com/ssps/

WikiCFP

学会の CFP (Call for Papers) の情報を集めたサイト

http://www.wikicfp.com/

[StreamCDR] 通信業界用標準ベンチマーク策定に向けて

携帯通信業界におけるデータストリーム処理の標準ベンチマークの策定を考えていきたいと思っています.

SPEC （Standard Performance Evaluation Corporation) が定めるWeb の標準ベンチマークSPECWeb 2005 では、E-commerce (楽天などのWeb ショッピングサイト, SSL あり、なしミックス）、Banking (SSL オンライン銀行サイト、SSL あり), そして Support (企業のドライバダウンロード。ファイル転送中心で動的スクリプト実行部分は少ない、ＳＳＬなし）の3つのシナリオが用意されています。各シナリオはそれぞれ異なる処理パターンを持っており、世の中の大部分のウェブアプリケーションの特徴をカバーしようとしています。

これに習って、携帯通信業界における代表的なシナリオを考えていきましょう。

１．課金計算の前処理

• バイナリデータから ASCII データへの変換
• Filtering : 課金計算に必要な項目のみを抽出する
• Data Schema Validation: Filtering によって抽出した項目に対するデータ妥当性検証。例えば、パケット数がある範囲を超えていないか、数値データであるのに文字列が入っていないか、など
• 遅延データ：　末端の機器の故障などで CDR / XDR が遅れて到着する場合があり、そのデータに関しては別途ファイルに退避する必要がある。
• 計算：　後続の課金処理に必要な基本的な計算（足し算、引き算など）
• Aggregate 処理：　ある ユーザーID に対して、一定時間における使用パケット数、使用通話時間。ユーザー数は膨大であるため、この処理はメモリインテンシブとなる。

2. 顧客属性に応じた課金計算

• データベースからのユーザー属性付与：　CDR には顧客 ID のみが格納されており、課金計算に必要な情報が格納されていない。それらの情報はデータベースに格納されているため、そこから課金情報に必要な様々な情報を抽出して、データに付与する。属性情報としては、企業情報（法人契約で契約している場合があり、その場合は課金形態が異なってくる）、契約時のキャンペーンＩＤ（ダブル定額、学生割引、家族割引、指定ユーザー割引など）などが含まれている
• CDR のユーザーが契約期間内かどうかのチェック (Fraud Detection)
• ユーザー属性に応じた課金計算（契約形態に応じて様々な課金計算パターンがある）
• 携帯会社にとって重要な1契約あたりの平均売り上げ APRU (Average Revenue Per User)のリアルタイム計算（上記と同じ）

3. マーケティング用大規模ネットワークグラフ構築

• CDR グラフの 誰 (From) が誰 (To) にかけたかをグラフのエッジとし、大規模なネットワークグラフをインクリメンタルに構築する。エッジの属性としては、量的なもの（通話時間）、ノード間の関係（家族）などの質的な関係などを付加する
• インクリメンタルに構築されるネットワークグラフに対して、各ノードの次数を求め、より多くのエッジが集中するノード（ユーザー）の Top-K を計算する。これらは、マーケティング分析に使用する
• グラフが巨大になるため、グラフのデータ構造とメモリ使用量などの指標となる

　使用する CDR/XDR データは標準的なデータ形式がないため、これに関しては独自に定めていくしかありません。ベンチマーク策定団体では、SPEC のほかに、TPC (Ｔransaction Processing Performance Council） などがありますが、SPEC では実装 (Java や PHP) を提供していますが、TPC ではアプリケーションシナリオを記述したドキュメントのみを提供しており、実装は提供していません。

我々自身は、SPEC が提供する形態ではなく、 TPC のような形でドキュメント化し、その一実装形態として、System S およびその他の 分散処理システムで実装し、定性的および定量的な評価をすれば、ひとつの研究論文として仕上がると思います。データストリーム処理だけでなく、Hadoop などと比較するのも良いでしょう。

英語

　英語を勉強しましょう。読むことは論文を読んでいけば自然に身についていきますが、書くこと、しゃべること、聞き取ることは意識して勉強していくしかないです。外資系企業だけでなく、国内企業もグローバル化が必至であり、当然従業員は英語が必要になっているのは言うまでもないでしょう。

学生を終えたら、ゆっくり勉強する暇などないと思った方がいいです。学生である今しかないと思った方がよいので、英会話学校にいくなど、どんな手段でも良いですが、大学院を卒業するまでにはまっとうな英語を身につけることを強くお薦めします。

分散ファイルシステムにおける投機実行

http://www.logos.ic.i.u-tokyo.ac.jp/~kabe/pds/20100520.pdf