The purpose of the Dagstuhl seminar ’Sublinear Algorithms’ was to bring together researchers working on the development of algorithms for very large data sets. Over the last few years data sets have become increasingly massive and the need to design special algorithms and data structures that deal with such amounts of data has emerged. For example, the set of all credit card transactions in the world for a month would have been considered a massive data set some time ago. That is comparable to the number of packet transactions a single router processes in one hour on an interface and we are now facing problems of analyzing the traffic at a large network of such routers, each with many interfaces! Internet traffic logs, clickstreams, web data are all examples of modern data sets that show unprecedented scale. Managing and analyzing such data sets forces us to revisit the traditional notions of efficient algorithms. The long-held golden standard of "linear algorithms" - algorithms that take time proportional to the input and store no more space than it takes to archive the input - is no longer as efficient as one needs or can afford. Thus, there is now a need for sublinear algorithms, that is algorithms that use resources (time and space) significantly less than the input size.

The main areas addressed in the workshop were property testing, sublinear time approximation algorithms, and data streaming algorithms. These areas are not only connected by the fact that they require algorithms with sublinear resources but also that they heavily rely on randomization and random sampling. Therefore, we hoped that this workshop helped to exchange ideas between these different areas.

During the seminar one could obtain a good overview of the current state of sublinear algorithms. In many interesting talks new algorithms and models as well as solutions to well-known open problems were presented.

Concluding remarks

The seminar was attended by 52 researchers from eight countries (19 USA, 13 Israel, 10 Germany, 4 Canada, 2 France, 2 United Kingdom, 1 Switzerland, 1 Hungary). From our own experience and the feedback from the participants we believe that the workshop was very successful. Interesting talks, fruitful discussions between researchers working on different areas of sublinear algorithms, and the wonderful working and living environment of Schloss Dagstuhl contributed to the success of the workshop.