Alex Andoni (Microsoft Research, USA)
Sketching, Sampling, and other Sublinear Algorithms
We will learn about modern algorithmic techniques for handling large datasets, often by using imprecise but concise representations of the data such as a sketch or a sample of the data. The lectures will cluster around three themes
- Nearest Neighbor Search (similarity search): the general problem is, given a set of objects (e.g., images), to construct a data structure so that later, given a query object, one can efficiently find the most similar object from the database.
- Streaming framework: we are required to solve a certain problem on a large collection of items that one streams through once (i.e., algorithm's memory footprint is much smaller than the dataset itself). For example, how can a router with 1Mb memory estimate the number of different IPs it sees in a multi-gigabytes long real-time traffic?
- Parallel framework: we look at problems where neither the data or the output fits on a machine. For example, given a set of 2D points, how can we compute the minimum spanning tree over a cluster of machines.
The focus will be on techniques such as sketching, dimensionality reduction, sampling, hashing, and others.
Lars Arge (Aarhus University, Denmark)
I/O Efficient Algorithms and Data Structures
In many modern applications that deal with massive data sets, communication between internal and external memory, and not actual computation time, is the bottleneck in the computation. This is due to the huge difference in access time of fast internal memory and slower external memory such as disks. In order to amortize this time over a large amount of data, disks typically read or write large blocks of contiguous data at once. This means that it is important to design algorithms with a high degree of locality in their disk access pattern, that is, algorithms where data accessed close in time is also stored close on disk. Such algorithms take advantage of block transfers by amortizing the large access time over a large number of accesses. In the area of I/O-efficient algorithms the main goal is to develop algorithms that minimize the number of block transfers (I/Os) used to solve a given problem. In these four lectures, we will cover fundamental I/O-efficient algorithms and data structures, such as sorting algorithms, search trees and priority queues. We will also discuss geometric problems, as well as geometric data structures for various range searching problems.
Mihai Budiu (Microsoft Research, USA)
Systems for Data-Intensive Parallel Computing
This course will cover fundamental principles and techniques for building large-scale data parallel batch processing systems, with examples based on the DryadLINQ software stack, developed at Microsoft Research. We will start by discussing LINQ (language-integrated query), a functional data-parallel language, highlighting features which make it particularly suitable for large-scale parallelization. We then discuss the software architecture of a compiler/runtime for running LINQ on large-scale clusters (thousands of machines), highlighting distributed storage, distributed reliable execution, and compilation.
Giuseppe F. Italiano (University of Rome “Tor Vergata”, Italy)
Algorithms for Big Data: Graphs and Memory Errors
The first part of my lectures will be devoted to the design of practical algorithms for very large graphs. The second part will be devoted to algorithms resilient to memory errors. Modern memory devices may suffer from faults, where some bits may arbitrarily flip and corrupt the values of the affected memory cells. The appearance of such faults may seriously compromise the correctness and performance of computations, and the larger is the memory usage the higher is the probability to incur into memory errors. In recent years, many algorithms for computing in the presence of memory faults have been introduced in the literature: in particular, an algorithm or a data structure is called resilient if it is able to work correctly on the set of uncorrupted values. This part will cover recent work on resilient algorithms and data structures.