[StreamGraph] Mining Large Time-evolving Data Using Matrix and Tensor Tools, SIGMOD 20007 tutorial

Mining Large Time-evolving Data Using Matrix and Tensor Tools, SIGMOD 20007 tutorial
http://www.cs.cmu.edu/~christos/TALKS/SIGMOD-07-tutorial/

How can we find patterns in sensor streams (eg., a sequence of temperatures, water-pollutant measurements, or machine room measurements)? How can we mine Internet traffic graph over time? Further, how can we make the process incremental? We review the state of the art in four related fields: (a) numerical analysis and linear algebra (b) multi-linear/tensor analysis (c) graph mining and (d) stream mining. We will present both theoretical results and algorithms as well as case studies on several real applications. Our emphasis is on the intuition behind each method, and on guidelines for the practitioner.

[StreamGraph] 既存のインクリメンタルグラフマイニング

1. An incremental frequent structure mining framework for real-time alert correlation, 2009
2. Incremental Pattern Discovery on Streams, Graphs and Tensors, 2007

[StreamGraph] インクリメンタルな Proximity 計算

Fast Incremental Proximity Search in Large Graphs, ICML 2008
http://portal.acm.org/citation.cfm?id=1390269

In this paper we investigate two aspects of ranking problems on large graphs. First, we augment the deterministic pruning algorithm in Sarkar and Moore (2007) with sampling techniques to compute approximately correct rankings with high probability under random walk based proximity measures at query time. Second, we prove some surprising locality properties of these proximity measures by examining the short term behavior of random walks. The proposed algorithm can answer queries on the fly without caching any information about the entire graph. We present empirical results on a 600, 000 node author-word-citation graph from the Citeseer domain on a single CPU machine where the average query processing time is around 4 seconds. We present quantifiable link prediction tasks. On most of them our techniques outperform Personalized Pagerank, a well-known diffusion based proximity measure.

[StreamGraph] Incremental PageRank 関連論文

Incremental PageRank for Twitter Data Using Hadoop
http://homepages.inf.ed.ac.uk/miles/msc-projects/abdullah.pdf

Fast Incremental and Personalized PageRank
http://www.citeulike.org/user/seeding-films/article/7795698

SYSTOR 2011

https://www.research.ibm.com/haifa/conferences/systor2011/

ACM KDD 2011

http://www.kdd.org/kdd2011/

2011/8 SanDiego, US

[StreamGraph] RWR の並列化・高速化

　ノード間の関連度を計算する手法　Random Walk With Restarts は　PEGASUS の１アプリケーションとしても実装されており、ソースコードにも入っています。

　また、RWRのGPUによる高速化が以下の論文で発表されています。

「Fast Mining Algorithms of Graph data on GPUs」,KDD LDMTAS2010 (KDD2010のワークショップ）, Xintian Yang (Ohio State University) (PDF)

[StreamGraph] 本プロジェクトの方向性

　本プロジェクトの方向性だが、時間的に動的変化するネットワーク（グラフ）に対するリアルタイム処理を実現する処理基盤、として体系化する方向性に行くべきだということは、ネットワーク・グラフ屋の論文を調べていくうちに確信が深くなっている。
あえて、上記で、「リアルタイム性」という表現を使って、データストリーム処理というキーワードを使わなかったかだが、それはGIM-Vの計算モデルを、GPUのようなアクセラレータを用いて既存のバッチ処理モデルを超並列処理してリアルタイム性を実現する手法、なども考えられるからだ。また、データストリーム処理というコンテキストで言えば、（１）インクリメンタルな差分更新による処理の効率化を実現する手法、（２）ヒューリスティックス（例：雁瀬くんの二次の隔たりの特性を生かしたグラフ分割と処理の分散）を用いた性能最適化、（３）メモリに載りきらないようなグラフストリームが到着した際に Persistent な分散ファイルシステムと協調し階層的にグラフ構造を格納、頻繁にアクセスされる部分グラフのみをオンメモリ上に確保するといった最適化手法、そしてそれらのグラフデータに対して開発者からシームレスにアクセスできるような処理基盤、と言った研究テーマが考えられるでしょう。
上記の研究テーマを遂行するにあたって、まずはとっかかりとして、バッチ処理の統一的な処理モデルとして提案されているGIM-Vおよびそのリファレンス実装であるPEGASUSを軸に、上記テーマの実現手法を考えていきましょう。例えば、このブログの前の記事に Incremental PageRank の論文を載せましたが、それをPEGASUS上（もしくは System S 上で）で実装してみて、GIM-V,プログラミングモデル、処理系の gap を分析し、上記（２）や（３）（（１）もできれば）を自然に表現できるモデルを提案できると良い研究成果につながると思います。

[StreamGraph] On the Bursty Evolution of Blogspace

On the Bursty Evolution of Blogspace, WWW 2005

http://www.springerlink.com/content/j15331281h531wmv/

[StreamGraph] 時系列動的グラフの視覚化

Interactive Visualization of Dynamic Social Network (PDF)

[StreamGraph] 時間的に変化する動的グラフに関する研究

Temporal Evolution of Communities in the Enron Email Data Set


Mining Temporally Evolving Graphs, 2004

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.6282


>Web mining has been explored to a vast degree and different techniques have been proposed for a variety of applications that include Web Search, Web Classification, Web Personalization etc. Most research on Web mining has been from a ‘data-centric ’ point of view. The focus has been primarily on developing measures and applications based on data collected from content, structure and usage of Web till a particular time instance. In this project we examine another dimension of Web Mining, namely temporal dimension. Web data has been evolving over time, reflecting the ongoing trends. These changes in data in the temporal dimension reveal new kind of information. This information has not captured the attention of the Web mining research community to a large extent. In this paper, we highlight the significance of studying the evolving nature of the Web graphs. We have classified the approach to such problems at three levels of analysis: single node, sub-graphs and whole graphs. We provide a framework to approach problems of this kind and have identified interesting problems at each level. Our experiments verify the significance of such analysis and also point to future directions in this area. The approach we take is generic and can be applied to other domains, where data can be modeled as graph, such as network intrusion detection or social networks.

評価の重要さ

　論文としての完成度を高めるには、徹底的に、提案する手法を定量的かつ定性的に評価する必要があります。良い研究であっても、その辺の Evidence がないと論文としては難しく、逆に、国際学会のいろいろな論文を見ると、提案する手法の新規性や進歩性が低くても、その辺の徹底的な分析があることによって、採択されている論文もあることに気づくでしょう。実装に比べると、評価は地道な作業ですが、そこが論文としては非常に重要であることを覚えておいてほしいと思います。

[StreamGraph] インクリメンタルなネットワーク分析手法

Incremental Page Rank Computation on Evolving Graphs (PDF), WWW 2005 ,

In this paper, we propose a method to incrementally compute PageRank for a large graph that is evolving. Our approach is quite general, and can be used to incrementally compute (on evolving graphs) any metric that satisfies the first order Markov property. Categories and Subject Descriptors

[Data Distribution] 投稿予定

データ分散最適化に関する研究の投稿先

HPDC 2011

Technical Papers Due:	17 January 2011
PAPER DEADLINE EXTENDED:	24 January 2011 at 12:01 PM (NOON) Eastern Time
Author Notifications:	28 February 2011

http://www.hpdc.org/2011/cfp.php

SYSTOR 2011

Paper Submission:	January 31, 2011
Paper Submission to highlights track:	March 4, 2011
Paper Notification:	March 21, 2011

https://www.research.ibm.com/haifa/conferences/systor2011/

[StreamCloud] 学会投稿予定

以下、StreamCloud の学会投稿予定

IEEE Cloud 2011 (http://www.thecloudcomputing.org/2011/cfp.html)

- Submission: January 20 (abstract) and 31, 2011

- Notification : March 15, 2011

IEEE CloudCom 2011 (3rd IEEE International Conference on Cloud Computing Technology and Science)

- Submission : August 21, 2011,

- Notification: September 26, 2011

[StreamGraph] Charactering Betweenness Centrality Algorithm on Multi-core Algorithms

Charactering Betweenness Centrality Algorithm on Multi-core Algorithms (PDF) , ISPA 2009

Evaluating Centrality Metrics in Real-World Networks on GPU (PDF)

[StreamGraph] Graph 500 Update

Graph500 のリファレンスコードのバージョン 1.2 が http://www.graph500.org/Reference.html に公開されている。実装は、sequential, MPI, OpenMP版（あと Cray XMT 用のコードもある）である。

入力データは、generator があり、クロネッカーグラフ (Jure の Kronecker Graph Tutorial, '08) を生成.処理はBFS( 幅優先探索)を実行。

BFS の実装自体はカスタマイズ可能。

[StreamGraph] SNAP (Stanford Network Analysis Package)

C++ベースのネットワーク分析ライブラリ: http://snap.stanford.edu/

スタンフォード大 Jure LesKovec 氏(コーネル大 Jon Kleinbergや PEGASUS の Christos Faloutsos 氏との元共同研究者）が管理.

Jure 氏の Ph.D Defense Talk : Dynamics of Large Network http://videolectures.net/sep08_leskovec_tdef/

[StreamGraph] Jon Kleinberg's Survey

http://www.cs.cornell.edu/home/kleinber/

時系列変化する動的グラフに関する参考文献 (http://www.cs.cornell.edu/Courses/cs6850/2008fa/より)

The Time Axis

Information networks are highly dynamic, but it is often hard to form a good picture of how they are evolving along their ``time axis.'' Temporal change spans many orders of magnitude, from the second-by-second dynamics of usage data to the year-by-year shifts in the global structure.

Survey Paper
J. Kleinberg. Temporal Dynamics of On-Line Information Streams. Draft chapter for the forthcoming book Data Stream Management: Processing High-Speed Data Streams (M. Garofalakis, J. Gehrke, R. Rastogi, eds.), Springer.
Short Time Scales: Usage Data and Bursty Dynamics
L.R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. In Proc. IEEE, Vol. 77, No. 2, pp. 257-286, Feb. 1989
J. Allan, J.G. Carbonell, G. Doddington, J. Yamron, Y. Yang, Topic Detection and Tracking Pilot Study: Final Report. Proc. DARPA Broadcast News Transcription and Understanding Workshop, Feb. 1998.
R. Swan, J. Allan, Automatic generation of overview timelines. Proc. SIGIR Intl. Conf. on Research and Development in Information Retrieval, 2000.
S. Havre, B. Hetzler, L. Nowell, ThemeRiver: Visualizing Theme Changes over Time. Proc. IEEE Symposium on Information Visualization, 2000.
J. Kleinberg. Bursty and Hierarchical Structure in Streams. Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
J. Aizen, D. Huttenlocher, J. Kleinberg, A. Novak. Traffic-Based Feedback on the Web. Proceedings of the National Academy of Sciences 101(Suppl.1):5254-5260, 2004.
R. Kumar, J. Novak, P. Raghavan, A. Tomkins. On the bursty evolution of Blogspace. Proc. International WWW Conference, 2003.
Y. Zhu and D. Shasha. Efficient Elastic Burst Detection in Data Streams. Proc. ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.
E. Gabrilovich, S. Dumais, E. Horvitz. NewsJunkie: Providing Personalized Newsfeeds via Analysis of Information Novelty. Proceedings of the Thirteenth International World Wide Web Conference. May 2004.
M. Vlachos, C. Meek, Z. Vagena, D. Gunopulos. Identifying Similarities, Periodicities and Bursts for Online Search Queries. Proc. ACM SIGMOD International Conference on Management of Data, 2004.
A..-L. Barabasi. The origin of bursts and heavy tails in human dynamics. Nature 435, 207-211 (2005).
Micah Dubinko, Ravi Kumar, Joseph Magnani, Jasmine Novak, Prabhakar Raghavan, Andrew Tomkins. Visualizing Tags over Time. WWW2006 Conference. See also the demo of flickr tag visualization.
Xuerui Wang and Andrew McCallum. Topics over Time: A Non-Markov Continuous-Time Model of Topical Trends. Conference on Knowledge Discovery and Data Mining (KDD) 2006.
Xuanhui Wang, ChengXiang Zhai, Xiao Hu, and Richard Sproat, Mining Correlated Bursty Topic Patterns from Coordinated Text Streams. Proceedings of the 2007 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'07 ), pages 784-793.

Temporal Analysis and Bursty Phenomena

• J. Leskovec, L. Backstrom, J. Kleinberg. Meme-tracking and the dynamics of the news cycle. Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2009.
  • See also the commpanying MemeTracker site, which uses the ideas in this paper to visualize the news cycle.
• L. Backstrom, J. Kleinberg, R. Kumar. Optimizing Web traffic via the Media Scheduling Problem. Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2009.
• J. Kleinberg. Temporal Dynamics of On-Line Information Streams. In Data Stream Management: Processing High-Speed Data Streams, (M. Garofalakis, J. Gehrke, R. Rastogi, eds.), Springer, 2004.
• J. Aizen, D. Huttenlocher, J. Kleinberg, A. Novak. Traffic-Based Feedback on the Web. Proceedings of the National Academy of Sciences 101(Suppl.1):5254-5260, 2004. (Also available in pre-print form.)
• J. Kleinberg. Bursty and Hierarchical Structure in Streams. Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
  • See also some sample results from the burst detection algorithm described in this paper.

J. Leskovec, J. Kleinberg, C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. Proc. 11th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2005.

[StreamGraph] Enron の E-mail データ

http://www.cs.cmu.edu/~enron/

[StreamGraph] スタンフォード大の公開データ

http://snap.stanford.edu/data/

公開しているデータは以下の通り。

Social networks: online social networks, edges represent interactions between people

Communication networks: email communication networks with edges representing communication

Citation networks: nodes represent papers, edges represent citations

Collaboration networks: nodes represent scientists, edges represent collaborations (co-authoring a paper)

Web graphs: nodes represent webpages and edges are hyperlinks

Amazon networks : nodes represent products and edges link commonly co-purchased products

Internet networks : nodes represent computers and edges communication

Road networks : nodes represent intersections and edges roads connecting the intersections

Autonomous systems : graphs of the internet

Signed networks : networks with positive and negative edges (friend/foe, trust/distrust)

Wikipedia networks and metadata : Talk, editing and voting data from Wikipedia

Twitter and Memetracker : Memetracker phrases, links and 467 million Tweets

[StreamGraph] Facebook Data

カリフォルニア大学の研究グループがクロールした Facebook のデータを公開

http://odysseas.calit2.uci.edu/wiki/doku.php?id=public:online_social_networks#datasets1

ニューヨーク MTA

http://mta.info/developers/

[StreamGraph] Public Data Sets

http://datamob.org/datasets

[StreamGraphPublic Data Sets

http://datamob.org/datasets

[StreamGraph] Livedoor Data

トップページがいかがわしいが、Livedoor が研究用途にデータを提供しているようだ。

http://labs.edge.jp/datasets/

[StreamGraph] データストリームに対する相関ルールを用いたコミュニティの時系列解析

データストリームに対する相関ルールを用いたコミュニティの時系列解析

https://kaigi.org/jsai/webprogram/2010/pdf/25.pdf

実験では、Livedoor が提供するソーシャルブックマークのデータを用いている

http://wiki.livedoor.jp/staff_clip/d/FrontPage

Body sensor data processing using stream computing

MIR '10 Proceedings of the international conference on Multimedia information retrieval

Advances in sensor technologies have accelerated the instrumentation of medical institutions. Today, modern intensive care units use sophisticated patient monitoring systems able to produce massive amounts of physiological streaming data. While these monitoring systems aim at improving patient care and staff productivity, they have the potential of introducing a data explosion problem. We address this problem by developing an open infrastructure upon which healthcare analytics can be built, managed, and deployed to analyze in real time physiological streaming data and turn this data into meaningful information for medical professionals. This infrastructure incorporates feature extraction and data mining functionalities for the discovery of clinical rules capable of identifying medically significant events. The system is based on a state of the art stream computing middleware. This paper presents this infrastructure from a programming model perspective. An exemplar application for arrhythmia detection is also described to illustrate its capabilities.

http://portal.acm.org/citation.cfm?id=1743465&dl=ACM&coll=DL&CFID=1325502&CFTOKEN=96177935

[StreamGraph] Some datasets available on the web

http://www.datawrangling.com/some-datasets-available-on-the-web

[StreamGraph] 食べログ

食べログ（http://u.tabelog.com/）には、１日に２００回までという制限がありますが、API があるようです。チェックしてみてください。２部グラフだと、グルメレビュアーとレストランとなるでしょう。グルメレビュアーは２０万人弱、レストランは６１万店舗となります。

[StreamGraph] Mixi Graph API

Mixi Graph API について Mixi に問い合わせたところ、直接お電話を頂いた。Graph API はパートナーとなる企業のみが使用できるのだが、どうも、それさえも、やはり、すべてのデータをクロールできるわけではないらしい。また、取得したデータは24時間以内には削除しなければならないのだそうだ。

今後、共同研究のような形で一緒にできるかどうかを話し合う機会がありそうだが、昨今の事情を考えると、日本のネット系の企業はあまり積極的ではない。WWWなどのウェブ系では著名な学会では、Facebook , Google, Flicker, Amazon などの実データを使った研究がたくさん出ているが、日本はとにかくそのあたり、消極的だ。米国を中心に、この手のネット企業が学会でプレゼンスを出すことにより、より Visibility を上げ、更には優秀な技術者が入ってくれるという良い循環となっている。

日本でも、そのように産学一体となって、この周辺の研究を加速化させ、Win-Win の関係を構築することが大変重要だと思うのだが。。。

[StreamGraph] Facebook App

Facebook の APIの手とのため、StreamGraph プロジェクト用にアプリケーションを登録。

http://developers.facebook.com/docs/authentication/#client_credentials

以下でアクセストークンを取得できる。your_app_id, your_app_secret は必要に応じて教えます。

curl -F grant_type=client_credentials \      -F client_id=your_app_id \      -F client_secret=your_app_secret \      https://graph.facebook.com/oauth/access_token

上記コマンドを発行すると、access_token が返ってくる。

[StreamGraph] Facebook Graph API

Facebook Graph API を用いれば実データは取れるそうだ。

------

The announcement was glossed over during Facebook’s many launches at f8 yesterday, but the company has introduced ways for developers to conduct a variety of searches for content in its Graph API. This could benefit any number of search companies and other developers who are looking for lots of public data to aggregate and organize.

The Open Graph allows applications, Pages, web sites and other software services to add Facebook features, like the “Like” button, to their own sites. Taking actions on other sites results in those actions being shared with your friends on Facebook, and may allow friends on those sites to see what you’re doing, too.

Many users have their privacy settings configured to allow status updates, likes and other activity to be public. Its terminology for this data is “public objects.” The generic search format is: https://graph.facebook.com/search?q=QUERY&type=OBJECT_TYPE.

Here are the specific types of searches that can be done:

All public posts: https://graph.facebook.com/search?q=watermelon&type=post

People: https://graph.facebook.com/search?q=mark&type=user

Pages: https://graph.facebook.com/search?q=platform&type=page

Events: https://graph.facebook.com/search?q=conference&type=event

Groups: https://graph.facebook.com/search?q=programming&type=group

News feeds of individuals can be searched, too, but you’ll need authorization. Here’s an example:

News Feed: https://graph.facebook.com/me/home?q=facebook

This search is restricted to public data about users and their immediate friends (not, say, their friends of friends), in keeping with Facebook’s existing data-sharing policies.

[StreamGraph] グラフアルゴリズムの GPU 化

Fast Mining Algorithms of Graph data on GPUs, LDMTA 2010

Scaling up the sparse matrix-vector multiplication kernel on modern Graphics Processing Units (GPU) has been at the heart of numerous studies in both academia and industry. In this article we present a novel approach to data representation for computing this kernel, particularly targeting sparse matrices representing power-law graphs. Using real data, we show how our representation scheme, coupled witha novel tiling algorithm, can yield signi ficant bene ts over the current state of the art GPU and CPU e orts on a number of core data mining algorithms such as PageRank, HITS and Random Walk with Restart.

http://arnetminer.org/confs/LDMTA2010/KDD-LDMTA-YangXintian.pdf

Accelerating Large Graph Algorithms on the GPU Using CUDA, 2007

http://www.springerlink.com/content/y4816x2q7475v93n/

Large graphs involving millions of vertices are common in many practical applications and are challenging to process. Practical-time implementations using high-end computers are reported but are accessible only to a few. Graphics Processing Units (GPUs) of today have high computation power and low price. They have a restrictive programming model and are tricky to use. The G80 line of Nvidia GPUs can be treated as a SIMD processor array using the CUDA programming model. We present a few fundamental algorithms – including breadth first search, single source shortest path, and all-pairs shortest path – using CUDA on large graphs. We can compute the single source shortest path on a 10 million vertex graph in 1.5 seconds using the Nvidia 8800GTX GPU costing $600. In some cases optimal sequential algorithm is not the fastest on the GPU architecture. GPUs have great potential as high-performance co-processors.

A Fast GPU Algorithm for Graph Connectivity, IPDPS 2010

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5470817

raphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.

[StreamGraph] Mixi Graph API

Mixi Graph API に関しては、パートナー契約が必要だそうで、登記簿などの提出が必要だそうです。なので、Mixi に大学などの研究組織に関しては、より手続きの簡素化ができるかどうか問い合わせをしておきました。

Mixi Graph API http://developer.mixi.co.jp/connect/mixi_graph_api

インターネットコンテンツの扱いに関して

著作権法改正案が国会提出、「ダウンロード違法化」など盛り込む

http://internet.watch.impress.co.jp/cda/news/2009/03/11/22747.html

文部科学省 著作権法の一部を改正する法律案

http://www.mext.go.jp/b_menu/houan/an/171/1251917.htm

文化庁のオフィシャルページ

http://www.bunka.go.jp/chosakuken/21_houkaisei.html

[StreamGraph] Netflix Challenge

ビデオレンタル会社 Netflix が依然実施した コンテスト (Netflix Prize: リコメンデーションの精度を10％以上向上させたら賞金) により、この分野における研究は大きく前進した。 当然、NetFlix は次のコンテストを企画していたそうだったが、個人を一意に特定できないことを証明することは難しく、プライバシーの問題でキャンセルしたそうだ。

http://www.techdirt.com/articles/20100312/1148468542.shtml

[StreamGraph] Graph 500

http://www.graph500.org/ のサイトが更新され、ランキングが出ています。

各種ネット企業の Web サービス API

価格.com の API http://apiblog.kakaku.com/KakakuItemInfoV1.0.html

Yahoo API http://developer.yahoo.co.jp/

楽天 Web サービス: http://webservice.rakuten.co.jp/

[StreamGraph] Social Graph API

最近, SNS の各社が Graph API を公開しだしているので、リストアップ。

Google Graph API http://code.google.com/intl/ja/apis/socialgraph/

- XFN（XHTML Friends Network）もしくはFOAF（Friend Of A Friend）を使用

- 使い方は、ここ などいろいろ記事があります。

Facebook Graph API http://developers.facebook.com/docs/api

Mixi Graph API

http://developer.mixi.co.jp/connect/mixi_graph_api/about_mixi_graph_api

SYSSTAT: Performance Analyzer

http://sebastien.godard.pagesperso-orange.fr/

VLDB 2010

http://www.vldb2010.org/proceedings/files/a_research.xml

p.472: The Performance of MapReduce: An In-depth Study
Dawei Jiang (National University of Singapore, Republic of Singapore), Beng Chin Ooi (National University of Singapore, Republic of Singapore), Lei Shi (National University of Singapore, Republic of Singapore), Sai Wu (National University of Singapore, Republic of Singapore)

p.129: Energy Management for MapReduce Clusters
Willis Lang (University of Wisconsin-Madison, United States of America), Jignesh Patel (University of Wisconsin-Madison, United States of America)

p.81: MapMerge: Correlating Independent Schema Mappings
Bogdan Alexe (University of California Santa Cruz, United States of America), Mauricio Hernández (IBM Research, United States of America), Lucian Popa (IBM Almaden Research Center, United States of America), Wang-Chiew Tan (University of California Santa Cruz, United States of Americ

p.449: iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques
Wook-Shin Han (Kyungpook National University, Republic of Korea), Jinsoo Lee (Kyungpook National University, Republic of Korea), Minh-Duc Pham (Kyungpook National University, Republic of Korea), Jeffrey Yu (The Chinese University of Hong Kong, People’s Republic of China)

p.340: On Graph Query Optimization in Large Networks
Peixiang Zhao (University of Illinois at Urbana-Champaign, United States of America), Jiawei Han (University of Illinois at Urbana-Champaign, United States of America)

p.330: Dremel: Interactive Analysis of Web-Scale Datasets
Sergey Melnik (Google, United States of America), Andrey Gubarev (Google, United States of America), Jing Jing Long (Google, United States of America), Geoffrey Romer (Google, United States of America), Shiva Shivakumar (Google, United States of America), Matt Tolton (Google, United States of America), Theo Vassilakis (Google, United States of America)

p.285: HaLoop: Efficient Iterative Data Processing on Large Clusters
Yingyi Bu (University of Washington, United States of America), Bill Howe (University of Washington, United States of America), Magdalena Balazinska (University of Washington, United States of America), Michael Ernst (University of Washington, United States of America)

p.264: Graph Pattern Matching: From Intractable to Polynomial Time
Wenfei Fan (University of Edinburgh, United Kingdom), Jianzhong Li (Harbin Institute of Technology, People’s Republic of China), Shuai Ma (University of Edinburgh, United Kingdom), Nan Tang (University of Edinburgh, United Kingdom), Yinghui Wu (University of Edinburgh, United Kingdom), Yunpeng Wu (National University of Defense Technology, People’s Republic of China)

p.276: GRAIL: Scalable Reachability Index for Large Graphs
Hilmi Yildirim (Rensselaer Polytechnic Institute, United States of America), Vineet Chaoji (Yahoo! Research Labs, United States of America), Mohammed Zaki (Rensselaer Polytechnic Institute, United States of America

p.220: High-Performance Dynamic Pattern Matching over Disordered Streams
Badrish Chandramouli (Microsoft Research, United States of America), Jonathan Goldstein (Microsoft Research, United States of America), David Maier (Portland State University, United States of America)

p.232: SECRET: A Model for Analysis of the Execution Semantics of Stream Processing Systems
Irina Botan (Eidgenössische Technische Hochschule Zürich, Switzerland), Roozbeh Derakhshan (Eidgenössische Technische Hochschule Zürich, Switzerland), Nihal Dindar (Eidgenössische Technische Hochschule Zürich, Switzerland), Laura Haas (IBM Almaden Research Center, United States of America), Renée Miller (University of Toronto, Canada), Nesime Tatbul (Eidgenössische Technische Hochschule Zürich, Switzerland)

p.244: Recognizing Patterns in Streams with Imprecise Timestamps
Haopeng Zhang (University of Massachusetts Amherst, United States of America), Yanlei Diao (University of Massachusetts Amherst, United States of America), Neil Immerman (University of Massachusetts Amherst, United States of America)

Amazon Web Service の記事

玉川さんによる Amazon Web Service の記事

http://aws.typepad.com/aws_japan/

Streaming k-means approximation

Paper: http://books.nips.cc/papers/files/nips22/NIPS2009_1085.pdf

Video Lecture : http://videolectures.net/icml09_monteleoni_opakmo/

プロジェクト体制のまとめ

今の研究室のプロジェクト体制を再度まとめましょう.

1. StreamGPU チーム (松浦君、上野君)

2. StraemGraphチーム (西井君、雁瀬君）

3. StreamCloud ＆StreamDS チーム(石井君、松浦君）

4. StreamScale チーム (Miyuru 君、上野君)

GPU における ゼロコピー通信

　昨日の議論で思い出したのだが、カーネル空間のソケットバッファからユーザー空間を経ずに直接 GPU のメモリにコピーするような機構が、データストリーム処理に対する GPU の適用には有効であるので、それを追求すれば良い。1年ぐらい前の議論になると思うが、再考する価値はあるでしょう。

[StreamGraph] ターゲットアプリケーション

どれがストリーム向きなのかを明確にするために、ターゲットアプリケーションをリストアップしていき、分類分けをしていきましょう。Graph チームの皆さんも補足してください。

• グラフの中心性 (HITS, PageRank,マルコフ中心性)
• クラスタリング（Betweennessアルゴリズム, KMeans, ...) 、セミクラスタリング
• Triangle の抽出
• 2部グラフの最大マッチング
• 最短経路問題
• グラフ直径
• ...

[StreamGraph] Jung

Jung(Java Universal Network/Graph Framework)

http://jung.sourceforge.net/

ネットワーク(グラフ) 構造の分析や視覚化を行うためのJavaのOSSライブラリ.

グラフ理論、データマイニング、ソーシャルネットワーク分析のアルゴリズムを数多く実装

BSDライセンス

国内学会

[査読あり]

Webとデータベースに関するフォーラム (WebDB Forum) 毎年8月締め切り、11月開催

[査読なし]

電子情報通信学会 Web インテリジェンスとインタラクション研究会

http://www.ieice.org/~wi2/index.html

次回は2011年3月

[StreamGraph] Related Papers

Internet: Diameter of the World-Wide Web, Arbert Barabashi, 1999

http://www.nature.com/nature/journal/v401/n6749/abs/401130a0.html

Graphs over Time: Densification Laws, Shrinking Diameters and Possible, Jon Kleinberg, KDD 2005

Scale-free characteristics of random networks: The topology of the world-wide web, Albert Barabashi, 2000

[StreamGraph] Random Walk with Restart

H. Tong, C. Faloutsos, and J.-Y. Pan. Fast Random Walk with Restart and Its Applications. In Proceedings of International Conference of Data Mining, 2006

http://www.cs.cmu.edu/~christos/PUBLICATIONS/icdm06-rwr.pdf

A Unified Framework for Link RecommendationUsing Random Walks

http://www.cs.uiuc.edu/homes/hanj/pdf/asonam10_zyin.pdf

[StreamGraph] Triangle Law

Evolution of the social network of scientific collaborations, Barabashi, 2001

The co-authorship network of scientists represents a prototype of complex evolving networks. In
addition, it offers one of the most extensive database to date on social networks. By mapping the
electronic database containing all relevant journals in mathematics and neuro-science for an eightyear period (1991-98), we infer the dynamic and the structural mechanisms that govern the evolution and topology of this complex system. Three complementary approaches allow us to obtain a detailed characterization. First, empirical measurements allow us to uncover the topological measures that characterize the network at a given moment, as well as the time evolution of these quantities.
The results indicate that the network is scale-free, and that the network evolution is governed by
preferential attachment, affecting both internal and external links. However, in contrast with most model predictions the average degree increases in time, and the node separation decreases. Second, we propose a simple model that captures the network’s time evolution. In some limits the model can be solved analytically, predicting a two-regime scaling in agreement with the measurements. Third, numerical simulations are used to uncover the behavior of quantities that could not be predicted analytically. The combined numerical and analytical results underline the important role internal links play in determining the observed scaling behavior and network topology. The results and methodologies developed in the context of the co-authorship network could be useful for a systematic study of other complex evolving networks as well, such as the world wide web, Internet,or other social networks.

Structure of a large social network. Barabashi, et.al, 2003

We study a social network consisting of over 104 individuals, with a degree distribution exhibiting
two power scaling regimes separated by a critical degree kcrit, and a power law relation between
degree and local clustering. We introduce a growing random model based on a local interaction
mechanism that reproduces all of the observed scaling features and their exponents. Our results
lend strong support to the idea that several very different networks are simultenously present in the human social network, and these need to be taken into account for successful modeling

[StreamGraph] Fast Counting of Triangles in Large Real Networks: Algorithms and Laws

http://www.cs.cmu.edu/~ctsourak/tsourICDM08.pdf

Fast Counting of Triangles in Large Real Networks: Algorithms and Laws

How can we quickly nd the number of triangles in a large graph, without actually counting them? Triangles are important for real world social networks, lying at the heart of the clustering coe cient and of the transitivity ratio. However, straight-forward and even approximate counting algorithms can be slow, trying to execute or approximate the equivalent of a 3-way
database join. In this paper, we provide two algorithms, the Eigen-Triangle for counting the total number of triangles in a graph, and the EigenTriangleLocal algorithm that gives the count of triangles that contain a desired node. Additional contributions include the following: (a) We show that both algorithms achieve excellent accuracy, with up to 1000x faster execution time, on several, real graphs and (b) we discover two new power laws ( Degree-Triangle and TriangleParticipa-
tion laws) with surprising properties.

EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

PDF: http://www.cs.cmu.edu/~badityap/papers/eigenspokes-pakdd10.pdf

通話記録からのソーシャルグラフのパターン検知

EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

We report a surprising, persistent pattern in large sparse social graphs, which we term EigenSpokes. We focus on large Mobile Call graphs, spanning about 186K nodes and millions of calls, and find that
the singular vectors of these graphs exhibit a striking EigenSpokes pattern wherein, when plotted against each other, they have clear, separate lines that often neatly align along specific axes (hence the term “spokes”). Furthermore, analysis of several other real-world datasets e.g., Patent Citations, Internet, etc. reveals similar phenomena indicating this to be a more fundamental attribute of large sparse graphs that is related to their community structure. This is the first contribution of this paper. Additional ones include (a) study of the conditions that lead to such EigenSpokes, and (b) a fast algorithm for spotting and extracting tightly-knit communities, called
SpokEn, that exploits our findings about the EigenSpokes pattern

MapReduce 上のグラフアルゴリズム

Design Patterns for Efficient Graph Algorithms in MapReduce

http://www.umiacs.umd.edu/~jimmylin/publications/Lin_Schatz_MLG2010.pdf

Jimmy Lin, Michael Schatz, University of Maryland
Graphs are analyzed in many important contexts, including ranking search results based on the hyperlink structure of the world wide web, module detection of protein-protein interaction networks, and privacy analysis of social networks. MapReduce provides an enabling technology for large-scale graph processing. However, there appears to be a paucity of knowledge on designing scalable graph algorithms. Existing best practices for MapReduce graph algorithms have significant shortcomings that limit performance, especially with respect to partitioning, serializing, and distributing the graph. We present three design patterns that address these issues and can be used to accelerate a large class of graph algorithms based on message passing, exemplified by PageRank. Experiments show that the application of our design patterns reduces the running time of PageRank on a web graph with 1.4 billion edges by 69%.


Graph Processing with MapReduce
http://horicky.blogspot.com/2010/07/graph-processing-in-map-reduce.html

Twister: Iterative MapReduce

インディアナ大学の Jeffery Fox のグループが作っている Iterative な MapReduce 処理系
Twister http://www.iterativemapreduce.org/

[StreamGraph] Extended Library for Graph Processing

Standard Template Library for XXL Data Sets

http://www.springerlink.com/content/6drvfrkj7uu4hq0a/
We present a software library , that enables practice-oriented experimentation with huge data sets. is an implementation of the C++ standard template library STL for external memory computations. It supports parallel disks, overlapping between I/O and computation, and pipelining technique that can save more than half of the I/Os. has already been used for computing minimum spanning trees, connected components, breadth-first search decompositions, constructing suffix arrays, and computing social network analysis metrics.


Building a Parallel Pipelined External Memory Algorithm Library


Large and fast hard disks for little money have enabled the processing of huge amounts of data on a single machine. For this purpose, the well-established STXXL library provides a framework for external memory algorithms with an easy-to-use interface. However, the clock speed of processors
cannot keep up with the increasing bandwidth of parallel disks, making many algorithms actually compute-bound. To overcome this steadily worsening limitation, we exploit today’s multi-core processors with two new approaches. First, we parallelize the internal computation
of the encapsulated external memory algorithms by utilizing the MCSTL library. Second, we augment the unique pipelining feature of the STXXL, to enable automatic task parallelization.
We show using synthetic and practical use cases that the combination of both techniques increases performance
greatly.

PDF
http://algo2.iti.kit.edu/singler/publications/parallelstxxl-ipdps2009.pdf

Hadoop Summit 2010

http://developer.yahoo.com/events/hadoopsummit2010/agenda.html

[StreamGraph] Max-Cover in Map-Reduce

Max-Cover in Map-Reduce, WWW 2010

http://research.google.com/pubs/pub36582.html

The NP-hard Max-k-cover problem requires selecting k sets from a collection so as to maximize the size of the union. This classic problem occurs commonly in many settings in web search and advertising. For moderately-sized instances, a greedy algorithm gives an approximation of (1-1/e). However, the greedy algorithm requires updating scores of arbitrary elements after each step, and hence becomes intractable for large datasets. We give the first max cover algorithm designed for today's large-scale commodity clusters. Our algorithm has provably almost the same approximation as greedy, but runs much faster. Furthermore, it can be easily expressed in the MapReduce programming paradigm, and requires only polylogarithmically many passes over the data. Our experiments on five large problem instances show that our algorithm is practical and can achieve good speedups compared to the sequential greedy algorithm.

Apache HAMA

http://incubator.apache.org/hama/

Apache Hama is a distributed computing framework based on BSP (Bulk Synchronous Parallel) computing techniques for massive scientific computations (e.g., matrix, graph, network, ..., etc), currently being incubated as one of the incubator project by the Apache Software Foundation.

Paper
http://salsahpc.indiana.edu/CloudCom2010/papers.html

DisCo: Distributed Co-clustering with Map-Reduce: A Case Study towards Petabyte-Scale End-to-End Mining

DisCo: Distributed Co-clustering with Map-Reduce: A Case Study towards Petabyte-Scale End-to-End Mining, 2008, ICDM

PDF http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.163.1677&rep=rep1&type=pdf

Huge datasets are becoming prevalent; even as researchers, we now routinely have to work with datasets that are up to a few terabytes in size. Interesting real-world applications produce huge volumes of messy data. The mining process involves several steps, starting from pre-processing the raw data to estimating the final models. As data become more abundant, scalable and easy-to-use tools for distributed processing are also emerging. Among those, Map-Reduce has been widely embraced by both academia and industry.

[StreamGraph] PEGASUS (Peta Graph Mining System)

Project URL http://www.cs.cmu.edu/~pegasus/

Paper URL ->
http://www.cs.cmu.edu/~ukang/papers/PegasusICDM2009.pdf

PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

In this paper, we describe PEGASUS, an open source Peta Graph Mining library which performs typical graph mining tasks such as computing the diameter of the graph, computing the radius of each node and finding the connected components. As the size of graphs reaches several Giga-, Tera- or Peta-bytes, the necessity for such a library grows too. To the best of our knowledge, PEGASUS is the first such library, implemented on the top of the HADOOP platform, the open source version of MAPREDUCE. Many graph mining operations (PageRank, spectral clustering,diameter estimation, connected components etc.) are essentially a repeated matrix-vector multiplication. In this paper we describe a very important primitive for PEGASUS, called GIM-V (Generalized Iterated Matrix-Vector multiplication). GIM-V is highly optimized, achieving (a) good scale-up on the number of available machines (b) linear running time on thenumber of edges, and (c) more than 5 times faster performance over the non-optimized version of GIM-V. Our experiments ran on M45, one of the top 50 supercomputers in the world. We report our findings on several real graphs, including one of the largest publicly available Web Graphs, thanks to Yahoo!, with 6,7 billion edges.

MapReduce Online

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-136.html


MapReduce is a popular framework for data-intensive distributed computing of batch jobs. To simplify fault tolerance, the output of each MapReduce task and job is materialized to disk before it is consumed. In this paper, we propose a modified MapReduce architecture that allows data to be pipelined between operators. This extends the MapReduce programming model beyond batch processing, and can reduce completion times and improve system utilization for batch jobs as well. We present a modified version of the Hadoop MapReduce framework that supports online aggregation, which allows users to see "early returns" from a job as it is being computed. Our Hadoop Online Prototype (HOP) also supports continuous queries, which enable MapReduce programs to be written for applications such as event monitoring and stream processing. HOP retains the fault tolerance properties of Hadoop, and can run unmodified user-defined MapReduce programs.

[StreamScale] ZooKeeper: Wait-free coordination for Internet-scale systems

http://research.yahoo.com/pub/3280

ZooKeeper: Wait-free coordination for Internet-scale systems

Authors:Hunt, P.; Konar, M.; Junqueira, F.P.; Reed, B.
Source: USENIX Annual Technology Conference (2010)

Abstract: In this paper, we describe ZooKeeper, a service for coordinating processes of distributed applications. Since ZooKeeper is part of critical infrastructure, ZooKeeper aims to provide a simple and high performance kernel for building more complex coordination primitives at the client. It incorporates elements from group messaging, shared registers, and distributed lock services in a replicated, centralized service. The interface exposed by Zoo- Keeper has the wait-free aspects of shared registers with an event-driven mechanism similar to cache invalidations of distributed file systems to provide a simple, yet powerful coordination service. The ZooKeeper interface enables a high-performance service implementation. In addition to the wait-free property, ZooKeeper provides a per client guarantee of FIFO execution of requests and linearizability for all requests that change the ZooKeeper state. These design decisions enable the implementation of a high performance processing pipeline with read requests being satisfied by local servers. We show for the target workloads, 2:1 to 100:1 read to write ratio, that ZooKeeper can handle tens to hundreds of thousands of transactions per second. This performance allows ZooKeeper to be used extensively by client applications.

[StreamScale] S4: Distributed Stream Computing Platform

http://s4.io/
http://labs.yahoo.com/node/476

S4: Distributed Stream Computing Platform
Authors: Neumeyer L, Robbins B, Nair A, Kesari A

Abstract: S4 is a general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows programmers to easily develop applications for processing continuous unbounded streams of data. Keyed data events are routed with affinity to Processing Elements (PEs), which consume the events and do one or both of the following: (1) emit one or more events which may be consumed by other PEs, (2) publish results. The architecture resembles the Actors model [1], providing semantics of encapsulation and location transparency, thus allowing applications to be massively concurrent while exposing a simple programming interface to application developers. In this paper, we outline the S4 architecture in detail, describe various applications, including real-life deployments. Our de- sign is primarily driven by large scale applications for data mining and machine learning in a production environment. We show that the S4 design is surprisingly flexible and lends itself to run in large clusters built with commodity hardware.

- PE がアクター（エージェント）となり、各イベントを処理していくモデル

- PE の開発者は、２つのメソッド processEvent と output メソッドを実装する。processEvent は受けたイベントを処理して、出力ストリームに渡す。output メソッドは、外部のコンポーネントから呼び出され、Aggregate のように定期的にバッファリングされたデータに対して処理するようなことができる

- 複数の PE は疎な結合となっており、どの PE とどの PE がつながっているかは、Spring フレームワークの Beans の記述として記述する。PE 同士の接続をアプリケーション側では書かない。

- Hadoop 上で実装されている、というネット上のコメントがあるが、それは全くの誤り。Hadoop 上では実装されていない。

- すべての PE は 対称的で、マスターデーモンのような存在はない。

- S4 のサンプルプログラムでは、Twitter Stream API を用いてトピックの数をカウントするアプリケーションを実装

[StreamTwitter] Twitterで株式市場を予測

http://news.goo.ne.jp/article/wiredvision/business/2010news1-28086.html

[StreamGraph] グラフベンチマーク Graph 500

グラフ処理用ベンチマーク。グラフ関係者必見。

Web Page: http://www.graph500.org/

仕様
http://www.graph500.org/spec.html

実装 v1.2
http://www.graph500.org/downloads.html

Data intensive supercomputer applications are increasingly important HPC workloads, but are ill suited for platforms designed for 3D physics simulations. Current benchmarks and performance metrics do not provide useful information on the suitability of supercomputing systems for data intensive applications. A new set of benchmarks is needed in order to guide the design of hardware architectures and software systems intended to support such applications and to help procurements. Graph algorithms are a core part of many analytics workloads. Backed by a steering committee of over 30 international HPC experts from academia, industry, and national laboratories, Graph 500 will establish a set of large-scale benchmarks for these applications. This BOF will unveil the first Graph 500 list, and discuss both today's Graph 500 benchmark and the evolution of that benchmark going forward. The Graph 500 steering committee is in the process of developing comprehensive benchmarks to address three application kernels: concurrent search, optimization (single source shortest path), and edge-oriented (maximal independent set). Further, we are in the process of addressing five graph-related business areas: Cybersecurity, Medical Informatics, Data Enrichment, Social Networks, and Symbolic Networks. The BOF will offer a forum for community and provide a rallying point for data intensive supercomputing problems, and follows the introduction of the Graph 500 at ISC2010. This is the first serious approach to complement the Top 500 with data intensive applications. Additionally, we are working with the SPEC committee to include our benchmark in their CPU benchmark suite. We anticipate the list will rotate between ISC and SC in future years.The Graph 500 was announced at ISC2010 and the first list will appear at SC2010.

[StreamXML] 関連論文

XML query processing using GPU
http://www.kde.cs.tsukuba.ac.jp/~vjordan/docs/

Regular Expression Matching on Graphics Hardware for Intrusion Detection
http://portal.acm.org/citation.cfm?id=1691157

Evaluating GPUs for Network Packet Signature Matching
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.4770

iNFAnt: NFA Pattern Matching on GPGPU Devices
http://netgroup.polito.it/Members/niccolo_cascarano/pub/cuda-02-2010.pdf

Research into GPU accelerated pattern matching for applications in computer security
http://www.cosc.canterbury.ac.nz/research/reports/HonsReps/2009/hons_0905.pdf

High-throughput stream categorization and intrusion detection on GPU
http://ieeexplore.ieee.org/Xplore/login.jsp?url=http://ieeexplore.ieee.org/iel5/5550962/5558619/05558648.pdf%3Farnumber%3D5558648&authDecision=-203


Small-ruleset regular expression matching on GPGPUs
http://portal.acm.org/citation.cfm?id=1810130

SQL/XML-IMDBg: A GPU In-Memory Database and Query Co-Processor
http://www.slideshare.net/NVIDIA/1105-gtc09

[StreamGraph] 超大規模ネットワークの高速コミュニティ検知手法

Fast unfolding of communities in large networks, Vicent D. Blondel, 2008

[StreamGraph] グラフアルゴリズムのベンチマーク

コミュニティ検知アルゴリズムの比較に用いられるベンチマークグラフの提案
Benchmark graphs for testing community detection algorithms, Andrea Lancichinetti et.al , 2008
http://pre.aps.org/abstract/PRE/v78/i4/e046110

[StreamGraph] Networks, Crowds, and Markets: Reasoning About a Highly Connected World

"Networks, Crowds, and Markets: Reasoning About a Highly Connected World", David Easley and Jon Kleinberg, http://www.amazon.co.jp/Networks-Crowds-Markets-Reasoning-Connected/dp/0521195330

Dive into A Data Deluge

http://diveintodata.org/

[StreamGraph] MapReduce 上でのグラフ処理

Graph Twiddling in a MapReduce World, Jonanthan Cohen, 2009
(PDF)

A Peta-Scale Graph Mining System - Implementation and Observations, 2009
(Slides)

[StreamGraph] グラフデータベース

グラフデータベース
http://www.infoq.com/jp/articles/graph-nosql-neo4j

[StreamScale] ビルド、コード管理など

- ビルド ant
- コード管理 sourceforge + SVN
- パフォーマンス測定ツール: JMeter
- ログ: Log4J

[StreamScale] JVM リモート監視

JMX を使いましょう

http://nadeausoftware.com/articles/2008/03/java_tip_how_get_cpu_and_user_time_benchmarking#UsingaSuninternalclasstogetJVMCPUtime
など

[StreamScale] 通信レイヤ

Apache MINA

MINA is a simple yet full-featured network application framework which provides:

Unified API for various transport types:
TCP/IP & UDP/IP via Java NIO
Serial communication (RS232) via RXTX
In-VM pipe communication
You can implement your own!
Filter interface as an extension point; similar to Servlet filters
Low-level and high-level API:
Low-level: uses ByteBuffers
High-level: uses user-defined message objects and codecs
Highly customizable thread model:
Single thread
One thread pool
More than one thread pools (i.e. SEDA)
Out-of-the-box SSL · TLS · StartTLS support using Java 5 SSLEngine
Overload shielding & traffic throttling
Unit testability using mock objects
JMX managability
Stream-based I/O support via StreamIoHandler
Integration with well known containers such as PicoContainer and Spring
Smooth migration from Netty, an ancestor of Apache MINA.

[StreamScale] DB

StreamScale のランタイムですが、Apache プロジェクトで利用できるコンポーネントは積極的に使っていきましょう。

- Apache Derby : RDB (Pure Java)
- Apache MINA : 効率的な通信レイヤの実装用
- APR (Apache Portable Runtime Project)
- Cassandra (http://cassandra.apache.org/)

[StreamScale] Java と Infiniband

StreamScale のノード間通信に重要


Efficient Java Communication Libraries over InfiniBand

Guillermo L. Taboada

http://www.computer.org/portal/web/csdl/doi/10.1109/HPCC.2009.87

This paper presents our current research efforts on efficient Java communication libraries over InfiniBand. The use of Java for network communications still delivers insufficient performance and does not exploit the performance and other special capabilities (RDMA and QoS) of high-speed networks, especially for this interconnect. In order to increase its Java communication performance, InfiniBand has been supported in our high performance sockets implementation, Java Fast Sockets (JFS), and it has been greatly improved the efficiency of Java Direct InfiniBand (Jdib), our low-level communication layer, enabling zero-copy RDMA capability in Java. According to our experimental results, Java communication performance has been improved significantly, reducing start-up latencies from 34μs down to 12 and 7μs for JFS and Jdib, respectively, whereas peak bandwidth has been increased from 0.78 Gbps sending serialized data up to 6.7 and 11.2 Gbps for JFS and Jdib, respectively. Finally, it has been analyzed the impact of these communication improvements on parallel Java applications, obtaining significant speedup increases of up to one order of magnitude on 128 cores.

[StreamScale] 機能

先日の機能要件で抜けている機能要件の一部。全部は最初は実装しないので、要件を一通り洗い上げて、最初のバージョンでどれを実装すれば良いかを選択するようにしましょう。

エンジン (SSR)
- データレート、CPU 使用率の計測

可視化ツール
- ストリームモニタリングツール（ちゃんとタプルが流れているかどうかを可視化する）
- どのオペレータがどのノードに今アサインされているかを可視化
（最初はテキストベースでも良いでしょうが、ないと不便でしょう）

[StreamScale] SSR (StreamScale Runtime) のリモート起動

自前でシェルスクリプトなどを用意するのでも良いが、GXP を使えばよいだろう。ただ、ちゃんとポータブルな実装になっているかどうかを確認する必要があるが。


リモートの JVM の監視ツールとしては以下のようなツールも存在する。
jps - Java Virtual Machine Process Status Tool
http://download.oracle.com/javase/6/docs/technotes/tools/share/jps.html

[StreamScale] 実装時に参考になるであろう情報

Efficient data transfer through zero copy
http://www.ibm.com/developerworks/library/j-zerocopy/

[StreamScale] 設計

概要設計(10月中いっぱいまでを予定）：2週間程度

第1回目： Programming Model / API (2010/10/13)
第2回目： Runtime Architecture (2010/10/18)
第3回目： 第1回目、第2回目のまとめ、他に必要な機能の議論

詳細設計：2週間程度 (11月1週目、2週目）
- API および SPI 決定

実装（第1ラウンド：11月中旬～12月下旬）
- 分担
- テストケース： Test First の思想に基づく

Agile な開発方式をするので、
まず第一プロトタイプを年内に完成させるのが目標

PGAS 2010

並列分散プログラミング言語 X10 は PGAS (Partitioned Global Address Space) と呼ばれる部類に入る言語ですが、PGAS のワークショップが開催されています。

以下が、採択された論文リストですが、まだダウンロードはできません。いくつか興味深い論文があります。


http://groups.google.com/group/pgas10/web/list-of-accepted-papers


The following papers (listed in no particular order) have been accepted for the conference:

Mads Ruben Burgdorff Kristensen and Brian Vinter. Numerical Python for Scalable Architectures
Vikas Aggarwal, Changil Yoon, Alan George, Herman Lam and Greg Stitt. Performance Modeling for Multilevel Communication in SHMEM+
Stefano Markidis and Giovanni Lapenta. Development and performance analysis of a UPC Particle-in-Cell code
Filip Blagojevic, Paul Hargrove, Costin Iancu and Kathy Yelick. Hybrid PGAS Runtime Support for Multicore Nodes
Megan Vance and Peter M. Kogge. Introducing mNUMA: An Extended PGAS Architecture
Nakao Masahiro, Lee Jinpil, Boku Taisuke and Sato Mitsuhisa. XcalableMP Implementation and Performance of NAS Parallel Benchmarks
Deepak Eachempati, Hyoung Joon Jun and Barbara Chapman. An Open-Source Compiler and Runtime Implementation for Coarray Fortran
Max Billingsley III, Beth Tibbitts and Alan George. Improving UPC Productivity via Integrated Development Tools
Nicholas Edmonds, Douglas Gregor and Andrew Lumsdaine. Extensible PGAS Semantics for C++
Montse Farreras and George Almasi. Asynchronous PGAS runtime for Myrinet networks
Han Dong, Shujia Zhou and David Grove. X10-Enabled MapReduce
Jithin Jose, Miao Luo, Sayantan Sur and Dhabaleswar K. Panda. Unifying UPC and MPI Runtimes: Experience with MVAPICH
Bill Scherer, Laksono Adhianto, Guohua Jin, John Mellor-Crummey and Chaoran Yang. Hiding Latency in Coarray Fortran 2.0

MapReduce 関係の最適化

Speeding Up Distributed MapReduce Applications Using Hardware Accelerators, Yolanda Becerra, ICPP 2009
http://personals.ac.upc.edu/dcarrera/papers/ICPP09.pdf


Phoenix Rebirth: Scalable MapReduce on a Large-Scale Shared-Memory System, Richard M. Yoo
http://csl.stanford.edu/~christos/publications/2009.scalable_phoenix.iiswc.pdf

Phoenix Project at Stanford University
http://mapreduce.stanford.edu/
Phoenix Project Slides

Deduce : 前のエントリ

オープンソースの LP Solver

LP (Linear Programming) の有名なソルバーでは、商用の CPLEX (AMPLという言語を通じて使用) が最も有名であるが、オープンソースのものでは、以下のソルバーが有名らしいです。石井君、参考にしてください。

COIN-ORプロジェクトのCLP: https://projects.coin-or.org/Clp
GNUのGLPK http://www.gnu.org/software/glpk/
性能比較: http://plato.asu.edu/ftp/lpfree.html

近況

　すっかりブログの更新をしていませんでしたが、皆さんはちゃんと更新お願いします。

最近は、来年度に向けた政府系予算取りに向けたプロポーザル作成に忙殺されています。採択された暁には、皆さんにご報告します。

10月下旬に行われるインターネットカンファレンス 2010 （査読つき）には、上野君、西井君、石井君の3人が採択されました。また、国際学会 DASFAA 2011 には西井君と松浦君が論文を投稿しました。

授業など忙しいと思いますが、やはり、論文、というのは単位や学士・修士論文以上に、個人の業績として一生残るものです。研究を大いに進めて、自分の大学での研究成果を積み重なっていってください。

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