西井くんの論文投稿先を考えています。音声以外では以下の研究会やシンポジウムでしょうか。国際学会もどこに出すか考えていきたいですね。
情報処理学会 DPS 研究会：マルチメディアと分散処理研究会
発表申込締め切り 7/12, 原稿締め切り 8月中旬
gnuplotでeps
14 年前
2010年5月29日土曜日
[StreamSR] 音声認識のスケーラビリティに関する研究
「音声対話システムにおけるスケーラビリティ評価モデルの検討」
［論文誌Vol.46, No.9, pp. 2269-2278 (2005)］
モバイル環境において，情報検索など利用者の目的を達成するためのインタフェースとして音声対話システムが注目されている．本論文では，サーバ処理能力と完全重複ユーザ数を求めることで，サーバ認識型音声対話システムのシステムスケーラビリティを推定する手法を提案する．サーバ処理能力は応答間隔および遅延時間から算出され，完全重複ユーザ数は発話間隔および同時接続ユーザ数より算出される．これらの値を応答時間で補正してサービスに必要なサーバ台数であるスケーラビリティを推定する．そして，「レストラン検索」および「駐車場検索」をサービス例とした検証評価を行い，サービス要件に応じたシステムスケーラビリティ推定の可能性を示した．
[StreamGPU] Regular Expression on GPU
正規表現を GPU 上で実行する研究。GPU に関係している人、要チェック。
Regular Expression Matching on Graphics Hardware for Intrusion Detection
StreamScale: データストリーム処理系の実装
そろそろ、うちの研究室でのデータストリーム処理系の設計を始めようと思います。やはり、コンポーネント化が重要であるので、OSGi のバンドル機構を使ってどのように実装していくかを調査していきましょう。
OSGi は Eclipse のプラグインなどに使われていますが、Spring, JBOSS, WebLogic, GlassFish, WebSphere Application Server v7.0 などのサーバーサイドでも使われだしています。以下は、WAS v7.0 の OSGi フレームワークの使われ方を開発したものです。チェックして見て下さい。
2010年5月20日木曜日
[Data Distribution / StreamScale] データストリーム処理におけるデータ分散最適化
来週からイスラエルで始まる 国際会議 SYSTOR 2010 では、ETL (Extract-Transform-Load) 処理にデータストリーム処理をした際の様々な性能解析と性能最適化に関する論文を発表します。
さて、この研究の続きとして以下のことを考えています。
SYSTOR の論文では、データを計算側に送る供給量が並列環境では十分ではなく、計算側のノード数、コア数を増加させたときにスケーラビリティが得られないという問題点をあげています。その解決策として、データの供給側を増やすことによって、リニアな性能向上を達成できたというのがこの研究の貢献です。この論文を受けて、以下の研究テーマを考えています。
1. 自動最適化： 先行研究では、供給側の増加は、供給側の分割数を試行錯誤しながら行いましたが、自動的に最適な分割数を探索し、かつプログラム変換によって自動最適化を行う手法を考えます。また、計算側のオペレータは、事前にプログラマによって SPLIT などによって、並列化していることを前提としていますが、開発者は論理的にデータ読み込みと計算部分を並列化を意識せずに開発し、最適化機構によって、ソース数と計算オペレータ数を最適化するようなプログラム変換を施し最高性能を得ます。
2. 実行時自動最適化： 1 は実行時前の最適化ですが、実行時にプロファイリングしながら最適化することも考えられます。こちらは難易度が高いですし、現行の System S ではできないでしょう。本研究室でデータストリーム処理系を作るとしたら、まず、このような最適化ができるような仕組みを作っておく必要があります。
2010年5月18日火曜日
2009年度 IA 研究会 研究賞受賞
老木君が主著の論文「ストリーム処理 System S を基盤にしたＷｅｂサーバーの構築」が2009年度の IA 研究会（インターネットアーキテクチャ）の研究賞を受賞しました。研究賞は、09年に研究会で発表された論文の中から数件採択されるものなので、価値が高いものです。老木君、おめでとうございます！
2010年5月17日月曜日
[StreamGraph] グラフアルゴリズムのライブラリ
Java 実装
- Jung (Java Universal Network/Graph Framework) ：グラフ(ネットワーク)構造の視覚化や分析を行うための、Java ベースのオープンソースライブラリ (Link)
- JGraphT: http://www.jgrapht.org/
Python 実装
- Python Graph : http://code.google.com/p/python-graph/
C++ 実装
- Boost Graph Library (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/index.html)
[StreamSR] Call Centers of the Future
先日ゼミで少し紹介した次世代コールセンターに関する記事が以下の PDF にのっています。
"Call Centers of the Future" http://lvs004.googlepages.com/callcenters.pdf
西井君、チェックしてみてください。
以下、ほんの一部ですが、紹介を。
- 最近のコールセンターにかけると、"Please note that this call may be recorded for training and evaluating purposes" と言われることも多く、顧客とのやりとりは録音されている。
- "Shall I make the bookings for you" と言う所を、"Can I lock this for you ?" と良く言う人がいたら、それを即座に訂正するような仕組みを作りたい
- Call Center には お客様からのコールを待つ Inbound （航空券の予約システム、お客様コールセンター) と お客さまへの売り込みをかけるOutbound がある。Outband で売り上げが良いオペレータ (Agent) の言い回しなど、Association マイニングなどを用いて行いたい。
- Call Center の成功にはオペレータの教育が重要だが、それにもコストがかかる。集団教育以外に、個別の教育も重要で、ここをコンピュータである程度 Automation できると良い
2010年5月14日金曜日
新メンバー第1回目演習発表会
新メンバー4人（石井君、上野君、雁瀬君、西井君）の第1回目演習発表会がありました。それぞれテーマは違いますが、頑張ったと思います。お疲れ様です。
次の発表に向けて、ひとつだけ気をつけて欲しいことがあります。 研究では、”実用性”、”新規性”、”進歩性”をディフェンスする要素を定量的なり定性的なり言う必要がありますが、何をやったかを正確に伝える技術に加えて、自分の研究の Contribution を正確に伝える技術がとても重要です。
これをやるには、参考文献や他の研究の詳細をちゃんと調べなければいけないので時間はかかりますが、大事なことなので意識して研究に勤しんでください。
2010年5月2日日曜日
2010年4月29日木曜日
Twitter: １ヶ月で12億 Tweet
今年２月の Twitter トラフィック分析。１ヶ月１２億 Tweet、１日単純平均４０００万。更に、単純に秒間で平均すると毎秒４６３ Tweet といったところ。
こちらは０９年１１月の分析。1時間当たりの Tweet 総数の最大値は10月2７日米国東海岸時間8時の 184万(毎秒511)、最小値は56万程度(毎秒155)で、差は3倍程度。
リンクマイニングに関する興味深い論文
リンク伝播法：リンク予測のための半教師付き学習法, 鹿島等 （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 が代表的なので、少しずつ調べていきましょう。
登録:
投稿 (Atom)
