今年２月の Twitter トラフィック分析。１ヶ月１２億 Tweet、１日単純平均４０００万。更に、単純に秒間で平均すると毎秒４６３ Tweet といったところ。
こちらは０９年１１月の分析。1時間当たりの Tweet 総数の最大値は10月2７日米国東海岸時間8時の 184万(毎秒511)、最小値は56万程度(毎秒155)で、差は3倍程度。
gnuplotでeps
12 年前
2010年4月29日木曜日
Twitter: １ヶ月で12億 Tweet
リンクマイニングに関する興味深い論文
リンク伝播法：リンク予測のための半教師付き学習法, 鹿島等 （PDF)
Fast Dynamic Reranking in Large Graphs, WWW2009
Fast Dynamic Reranking in Large Graphs, WWW2009
2010年4月24日土曜日
[StreamGraph] IPDPS 2010
Parallel Graph Algorithms II
Chair: Padma Raghavan
Optimization of Linked List Prefix Computations on Multithreaded GPUs Using CUDA
Zheng Wei (University of Maryland, US); Joseph Jaja (University of Maryland, College Park, US)
Parallel External Memory Graph Algorithms
Lars Arge (Aarhus University, Denmark); Michael Goodrich (University of California, Irvine, US); Nodari Sitchinava (Aarhus University, Denmark)
http://www.ics.uci.edu/~nodari/graph_pem.pdf
Engineering a Scalable High Quality Graph Partitioner
Mauel HoltGrewe (University of Karlsruhe, Germany); Peter Sanders (University of Karlsruhe, Germany); Christian Schulz (University of Karlsruhe, Germany)
2010年4月23日金曜日
Recent Various Papers
以下、本研究室に関係する最近の著名な論文。
The Problem With Treads, Edward Lee
http://courses.cs.vt.edu/~cs5204/fall09-kafura/Papers/Threads/ProblemWithThreads.pdfPeter Pietzuch, et.al, Network-Aware Operator Placement for Stream-Processing Systems, ICDE 2006
GPUTeraSort: high performance graphics co-processor sorting for large database management, SIGMOD
Optimization principles and application performance evaluation of a multithreaded GPU using CUDA
Accelerator: using data parallelism to program GPUs for general-purpose uses, ASPLOS
NVIDIA Tesla: A Unified Graphics and Computing Architecture
Erik Lindholm, John Nickolls, Stuart F. Oberman, John Montrym
Journal: IEEE Micro - MICRO
Data streams: algorithms and applications - 2003
Ceph: A Scalable, High-Performance Distributed File System
Network-Speed XML Processing on GPGPU
松浦君が StreamDS の次に遂行するテーマ XML Processing on GPU.
DSMS において、構造化されたデータは SOA の流れを受けて XML 化されており、それを高速に処理しなければ後続の高性能な処理に追いつけず、ボトルネックになる、というのが研究の Motivation。現在, XML 専用のハードウェアアプライアンスとして DataPower などの商用製品（数百万円する）があるが、GPU を用いればコモディティデバイス上での高速化が期待される。ざっと調べたところないので、うまくいけば（性能がもちろん一番）先駆的な研究になるであろう。
2010年4月22日木曜日
2010年4月21日水曜日
Twitter ログ分析 Web インタフェース
Twitter の Streaming API を用いて収集したデータを元に、StreamCloud, StreamDS, StreamAlgo プロジェクトの基礎統計データを集めたいと思います. Streaming API は間引かれているので、絶対的な値は利用できませんが、少なくとも以下の２点の統計情報が取れればと思います。
- Bursty 度合い： 定常状態とバースト時のトラフィックの比（相対的な比が保たれていれば良いのだが。。。）
- 時間的周期性： 定常状態において、時間によるトラフィックの周期性があるが、最もトラフィックが時間帯と最も低いときとの違い
- （べき乗則 (Power Law) も確認できれば, Load Shedding の戦略に役立つと思いますが。。。）
基礎統計データの取得が主眼なので可視化する必要性はありませんが、Streaming API を用いて時々刻々取得しているかどうか確認するためにも、以下のような グラフ化ツールを用いて Web 上で見れても面白いでしょう。
Open Flash Chart : Flash でグラフを生成するオープンソースのツール。PHP が必要。
GUI の要件としては、いつからいつまでどのくらいの間隔で取得するかどうかをユーザーが設定し（例えば、２０１０年３月１日０時００分～２０１０年３月３１日２３時５９分の間で１時間毎, もしくは２０１０年３月１日の００時から２４時までで５分毎、など）、再描画ボタンでグラフの再処理リクエストをサーバー側に送信。
サーバー側の PHP スクリプトでは、パラメータで設定された情報を元に、Twitter のログデータから件数を取得（または事前に件数をあるファイル又は DB に書き込んでおいてもよい）。X 軸を時間、Y 軸をデータ件数として、Open Flash Chart のオブジェクトにセットし、グラフを生成。
2010年4月20日火曜日
[StreamCDR] インメモリデータベース関係
Main-Memory Databases for Real-Time Telecom Applications (PDF)
Introduction to Main-Memory Databases
In-memory DB の適用分野に関する性能検証
XML データベースをインメモリ化する話
2010年4月19日月曜日
[StreamCloud] アーキテクチャ考察
StreamCloud の System S 上での実現方法を石井君と議論を行ったので、そのメモを記す。現行の System S では、ホストの動的な削除は可能だが、ホストの動的な追加はできない（正確には、インスタンスへのホストの追加は streamtool addhost コマンドで可能だが、新たなホストには PE が割り当てられない）。この制限はクラウド環境を用いて、データが低レートの時は System S が稼動する VM をsuspend し, bursty な状況においては その VM をresume するようなシステムを構築する際に問題となる。
この問題を（比較的きれいに）解決するため、以下の図のように System S/SPADE の import/export 機能を用いた疎結合なアーキテクチャ構成を考える。
要はモノシリックな SPADE アプリケーションにしてしまうと、現行の System S の機能では新たに追加されたホストへのデータ供給が難しい。しかし、import/export を用いれば、データを受信しスケジューリングするコンポーネントと、計算側のコンポーネントを分離でき、必要なときにクラウド側の計算用 SPADE ジョブを立ち上げ、import 機能でデータを取り込むような構成にすれば上記の問題が解決される、というわけだ。但し、実装上、本当に可能かはより詳細な検討・検証が必要であろう。
Job Scheduler の役割と、ジョブが処理されるまでの流れは以下の通り。
- ホストとストリーム番号のマッピングテーブルの管理: UDOP の出力ストリームは物理ホストを指定することができないので、Job Scheduler (UDOP) では、内部で出力ストリーム番号（以下、ストリーム番号と省略する）とホスト名をマッピングするテーブルを持たせる。このテーブルには、その他にも、スケジューリングアルゴリズムのために必要な各ホストの属性情報（CPU,メモリ、OS,動的負荷情報、メモリ使用量, レイテンシの平均及び分散、クラウド環境のホストかどうか）を持たせる。
- バースト度合いの計算： Job Scheduler はデータ到着レートを見てバースト度合いを計算。LAN 内のクラスタで処理できる量かどうかを調べる。
- バーストでない場合： ２の計算にてバーストでないと判断された場合には、Cluster Load Management Component (Python などのスクリプト言語を用いた軽量実装） からストリームとして流れる各ホストのロード情報を用いて、データを投げるホストを決定。決定したホスト名に相当するストリーム番号を上記のテーブルから引いてきて、データとプロパティをセットし、ストリームをexport する。export のプロパティは、クラウド環境も含めた一意の ID とする。
- バーストな場合： ２の計算にてバーストと判断された場合に、Cloud Controller (こちらも 同じく Python などのスクリプト言語を用いた軽量実装とする）に指令を出す。Cloud Controller はあるポート番号にて Listen しており、Job Scheduler からの指令を待つ。クラウドに対する VMM の管理コマンドが Job Scheduler から発行された場合には、Amazon EC2 や Eucalyptus などのクラウド環境に対して REST API を用いてその管理コマンドを発行する。また、VM の resume 時には、その VM にて System S のジョブが実行されるように、ジョブをサブミットする。計算側でのジョブは、import でデータを取り込み、処理を開始する。VM の suspend の際にはジョブキャンセルを実行する。
ちなみに、Cluster Load Management や Job Scheduler の機能は、System S の管理デーモンである SRM (Streams Resource Manager) や SCH (Scheduler) と同等の役割を果たしており、それらのデーモンを改変、拡張すれば良いのではとの指摘を受けると思われるが、そのような指摘に対して事前に対応するため、素直に前提条件として、「管理デーモンを改変することができない」ことを述べた方が良いだろう。
ただし、クラウドを用いた Elastic なデータストリーム処理という考え方、及びそれらのスケジューリングポリシーを提案することが、本研究の Contribution であることを強調し、今回 SPADE 上でアプリケーションレベルで実装したのとは本質的な差はないことを述べれば良い。
電子情報通信学会 データ工学6月研究会
6月研究会
日時：2010年6月28日（月）
場所：名古屋大学（愛知県名古屋市）
議題：「センサ情報処理，ストリームデータベース，および一般」
申込締切：5月7日(金)（ただし，学会誌に暫定プログラムを掲載する関係上，4月14日(水)までに申込いただけますと助かります）
原稿締切：6月7日(月)
申込みは http://www.ieice.org/ken/program/index.php?tgid=IEICE-DE からお願いします．
詳細はこちらをご覧ください．
ICDE 2011
ICDE 2011 の締め切りは 7月16日。Notification は10月下旬。
---
ICDE 2011
http://www.icde2011.org/call_for_papers.htmlAbstract due: July 16, 2010
Full paper submissions due: July 23, 2010
Author feedback time window: Sep. 24 - Oct 1, 2010
Notification of authors: Oct. 30, 2010
Final versions due: Nov. 30, 2010
2010年4月18日日曜日
Continuous Subgraph Pattern Search over Graph Streams
Continuous Subgraph Pattern Search over Graph Streams, ICDE2009
http://portal.acm.org/citation.cfm?id=1546683.1547430
http://portal.acm.org/citation.cfm?id=1546683.1547430
Burst Detection
データストリームに対するバースト検出に関する論文。StreamDS, StreamCloud 及び StreamAlgo に関係してきますので、要チェック.
- Adaptive Burst Detection in in a Stream Engine (PDF)
- Better burst detection, ICDE 2006
- Efficient Elastic Burst Detection in Data Streams, SIGKDD 2003
- Statistical monitoring of thousands of data streams in real time, VLDB2002
2010年4月15日木曜日
データストリーム処理システム実装に向けて
数年前からサーバーサイド (Web アプリケーションサーバーやサーブレットエンジン、EJB サーバー, WSO2 Carbon Platformなど）や Eclipse などで OSGi フレームワークを使って実装されていることが多くなってきている。OSGi ベースで実装することにより、システムのコンポーネント化、モジュール化の基盤として使えるだろう。また、ネットワーク上からコンポーネントの追加・停止をJVM (Java Virtual Machine) を止めることなくできるので、DSMS (Data Stream Management System) において、実行時に動的にオペレータのデータフローを最適化していくような仕組みもこれを利用すれば、比較的容易に実現できるかもしれない。OSGiの実装としては、Apache Felix が代表的なので、少しずつ調べていきましょう。
2010年4月14日水曜日
2010年4月10日土曜日
2010年4月8日木曜日
2010年4月7日水曜日
[StreamCloud] Amazon EC2
Amazon EC2 の SLA (Service Level Agreement) や課金体系、Reservation 機能の有無などをざっと調べてみましょう。
http://aws.amazon.com/ec2/
http://aws.amazon.com/ec2/
2010年4月2日金曜日
COLA: optimizing stream processing applications via graph partitioning
COLA: optimizing stream processing applications via graph partitioning
URL
System S などのデータストリーム処理では、オペレータ（頂点）とオペレータ間を流れるストリーム（エッジ）をデータフローグラフとしてアプリケーションを記述することが一般的になっている。このような論理的なフローを実際の物理的な計算機環境上で稼動させ、かつ最適なパフォーマンスを出すためには、ある単位でオペレータを一つのOSのプロセスとして Fusion （統合）することが不可欠となる。Fusion の仕方としては、各オペレータの処理時間とオペレータ間の通信時間のバランスを考えて、Fusion をさせるかしないかを判断するが、多くのオペレータが存在する場合には到底、人間が判断することができない。当論文では、この Fusion のアルゴリズムを最小カットのグラフ分割問題として定式化することで、最適な Fusion パターンを割り出す手法を提案している。
URL
System S などのデータストリーム処理では、オペレータ（頂点）とオペレータ間を流れるストリーム（エッジ）をデータフローグラフとしてアプリケーションを記述することが一般的になっている。このような論理的なフローを実際の物理的な計算機環境上で稼動させ、かつ最適なパフォーマンスを出すためには、ある単位でオペレータを一つのOSのプロセスとして Fusion （統合）することが不可欠となる。Fusion の仕方としては、各オペレータの処理時間とオペレータ間の通信時間のバランスを考えて、Fusion をさせるかしないかを判断するが、多くのオペレータが存在する場合には到底、人間が判断することができない。当論文では、この Fusion のアルゴリズムを最小カットのグラフ分割問題として定式化することで、最適な Fusion パターンを割り出す手法を提案している。
登録:
投稿 (Atom)
