The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:

Upper and Lower Bounds on the Cost of a Mapreduce Computation: A Tradeoff


Speaker: Prof. Foto Afrati
Affiliation: National Technical Universtity of Athens, Greece
Category: Colloquium
Location: Room 148, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions)
Date: Wednesday, July 24, 2013
Time: 11:00-12:00 EET
Host: Marios Mavronicolas (

As MapReduce/Hadoop grows in importance, we find more exotic applications being written this way. Not every program written for this platform performs as well as we might wish. There are several reasons why a MapReduce program can underperform expectations. One is the need to balance the communication cost of transporting data from the mappers to the reducers against the computation done at the mappers and reducers themselves. A second important issue is selecting the number of rounds of MapReduce. A third issue is that of skew. If wall-clock time is important, then using many different reduce-keys and many compute nodes may minimize the time to finish the job. Yet if the data is uncooperative, and no provision is made to distribute the data evenly, much of the work is done by a single node. In this talk we will focus on the tradeoff between communication cost and the computation cost of the reducers: the finer we partition the work of the reducers so that more parallelism can be extracted, the greater will be the total communication between mappers and reducers. We introduce a model of problems that can be solved in a single round of MapReduce computation, and use it to demonstrate the tradeoff. This model enables a generic recipe for discovering lower bounds on communication cost as a function of the computation cost of the reducers, which is captured as the maximum number of inputs that can be assigned to one reducer. We then use the model to compute lower bounds and present algorithms that meet these bounds for a number of problems described below. Algorithms and lower bounds will be presented for problems such as: Similarity joins, Matrix multiplication, subgraph finding, multiway joins.

Short Bio:
Foto Afrati received the BS degree from the Mechanical and Electrical Engineering Department of National Technical University of Athens (NTUA) and the PhD degree from Imperial College of the University of London. She is a professor in the Electrical and Computing Engineering Department of the NTUA, Greece and recently spent her sabbatical leave visiting Google at Mountain View (April 2012-June 2013). Her recent research interests are in the area of big data and specifically query optimization for mapreduce and other similar distributed platforms. She has been the programm committee chair for Conference on Principles of Databases (PODS) 2005 and for International Conference on Database Theory (ICDT) 1997 for which she was the organizing committee chair as well. She has served on the program committee of many conferences on databases and algorithms and she has published over a hundred papers in the areas of databases, algorithms and distributed computing.

Video Online:
 Recorded Video available through vimeo

  Mailing List:

Sponsor: The CS Colloquium Series is supported by a generous donation from Microsoft