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

"利用者のツイートが掲載される企業のキャンペーンページなどに無関係な宣伝や公序良俗に反するツイートが投稿された際は、リアルタイムでブロックしたり、メールでアラート"
"オプションで、ハッシュタグや一般キーワードの監視、商品購入を薦めるフレーズなどの自動ピックアップ機能"