1月投稿予定の論文

今月投稿予定の論文は以下の通りです。特に4年生は山場ですが、頑張りましょう。

国内5本、国際会議7本

情報処理学会全国大会 x 2本（石井、雁瀬）
SACSIS/ACS 論文誌 x 3本（石井、上野、雁瀬）

国際会議 ACM HPDC2011 x 3本（上野、松浦, Miyuru)
国際会議 IEEE Cloud 2011 x 1本 (石井）
国際会議 SYSTOR 2011 x 1本（鈴村/森田）
国際会議 IEEE ICWS 2011 x 1本（鈴村/老木）
国際会議 IEEE ICC Workshop (カメラレディ) x 1本（老木）

[StreamGPU] 高データレートストリーム処理へのGPUタスク並列の適用

上野氏: 次の論文（まずは査読つき国内論文）の概要
ターゲット学会：FIT査読付き論文、またはその他


----
タイトル：高データレートストリーム処理へのGPUタスク並列の適用

問題
・小さい計算量のアルゴリズムへの対応
・データレートが高い場合の、IOボトルネック
・計算量の異なるタスクを同時に計算するには？（ウィンドウサイズが異なるなど）

解決策
・問題サイズの大きさによっては、warpごとのタスク並列で計算（○）
・データ転送と計算のオーバーラップ（△）
・計算量の異なるタスクを、複数カーネル同時実行で計算（△）

評価
・IKA-SST

結果
・条件が良ければ、CPU1コアに対して、teslaで60倍、GTX 460で40倍の性能

考察
・CPU計算部分の計算量は、ウィンドウサイズによらず一定なので、ウィンドウサイズを小さくすると、CPUの計算がボトルネックになる

Cloud Computing and Grid Computing 360-Degree Compared

Cloud Computing and Grid Computing 360-Degree Compared, Ian Foster
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4738445

Hadoop 上の機械学習ライブラリ Apache Mahout

http://mahout.apache.org/

Collaborative Filtering
User and Item based recommenders
K-Means, Fuzzy K-Means clustering
Mean Shift clustering
Dirichlet process clustering
Latent Dirichlet Allocation
Singular value decomposition
Parallel Frequent Pattern mining
Complementary Naive Bayes classifier
Random forest decision tree based classifier
High performance java collections (previously colt collections)
A vibrant community

[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/