Keynote in Symposium on Experimental Algorithms

Engineering streaming algorithms, June 2017.
Invited talk at Symposium on Experimental Algorithms.

Streaming algorithms must process a large quantity of small updates quickly to allow queries about the input to be answered from a small summary. Initial work on streaming algorithms laid out theoretical results, and subsequent efforts have involved engineering these for practical use. Informed by experiments, streaming algorithms have been widely implemented and used in practice. This talk will survey this line of work, and identify some lessons learned.

Advertisements

Adams Prize 2017

Professor Graham Cormode has been awarded the 2017 Adams Prize by the Cambridge Faculty of Mathematics. The award recognizes his work on “Statistical Analysis of Big Data”, and is awarded jointly with Professor Richard Samworth of Cambridge. Professor Cormode says,

My work, in common with Prof Samworth’s, is about finding mathematical representations of data that allow useful information to be extracted effectively and accurately. These techniques allow ever larger quantities of data to be handled on ordinary computers.

Professor Cormode’s work on “data sketches” has been used in companies such as Netflix, Yahoo, Twitter, Google, AT&T and Sprint. He is currently leading Warwick’s involvement in the Alan Turing Institute at London, and working on questions to do with verification of machine learning, and privacy.

The prize is worth £15,000 and will be split equally between the two recipients.

 

Invited Keynote in DISC 2016

Matching and covering in streaming graphs, Sept. 2016.
Invited keynote talk at DISC 2016.

Problems related to (maximum) matchings and vertex covering in graph have a long history in Combinatorics and Computer Science. They arise in many contexts, from choosing which advertisements to display to online users, to characterizing properties of chemical compounds. Stable matchings have a suite of applications, from assigning students to universities, to arranging organ donations. These have been addressed in a variety of different computation models, from the traditional RAM model, to more recent sublinear (property testing) and external memory (MapReduce) models. Matching has also been studied for a number of classes of input graph: including general graphs, bipartite graphs, weighted graphs, and those with some sparsity structure.We focus on the streaming case, where each edge is seen once only, and we are restricted to space sublinear in the size of the graph (ie., no. of its vertices). In this case, the objective is to find (approximately) the size of the matching. Even here, results for general graphs are either weak or make assumptions about the input or the stream order. In this talk, we describe work which seeks to improve the guarantees in various ways. First, we consider the case when we are given a promise on the size of the solution: the matching is of size at most k, say. This puts us in the realm of parameterized algorithms and kernelization, but with a streaming twist. We show that algorithms to find a maximal matching can have space which grows quadratically with k. Second, we consider restricting to graphs that have some measure of sparsity — bounded arboricity, or bounded degree. This aligns with reality, where most massive graphs have asymptotically fewer than O(n2) edges. In this case, we show algorithms whose space cost is polylogarithmic in the size of the input, multiplied by a constant that depends on the level of sparsity, in order to estimate the size of the maximum matching. The techniques used rely on ideas of sampling and sketching, developed to handle data which arrives as a stream of observations, coupled with analysis of the resulting randomized algorithms.

Postdoc position in Algorithms Research (closes April 26th 2017)

We are seeking to recruit a postdoctoral research fellow to work in the area of designing algorithms for analysing large data sets.

You will be expected to perform high quality research under the supervision of Professor Graham Cormode, as part of the ERC funded project ‘Small Summaries for Big Data’. This can encompass streaming algorithms, sketching and dimensionality reduction, distributed monitoring and mergeable summaries, verification of outsourced computation, or other related topics. The expectation is that you will produce breakthrough research results in the summarisation of large volumes of data, and publish these results in top rated venues.

You will possess a PhD or an equivalent qualification in Computer Science or a very closely-related discipline (or you will shortly be obtaining it). You should have a strong background in one or more of the following areas: randomized and approximation algorithms; communication complexity and lower bounds; streaming or sublinear algorithms.

The post is based in the Department of Computer Science at University of Warwick, but collaborations with closely related research organisations such as the Centre for Discrete Mathematics and its Applications (DIMAP), the Warwick Institute for the Science of Cities (WISC); and the newly formed Alan Turing Institute (ATI) will be strongly encouraged. You will join a team of researchers led by Professor Cormode including other postdoctoral researchers and PhD students.

Candidates should provide with their application form a CV, a list of publications and a research statement.

Closing date: 26th April 2017 (this position is being readvertised)

More information:https://atsv7.wcn.co.uk/search_engine/jobs.cgi?owner=5062452&ownertype=fair&jcode=1640701&vt_template=1457&adminview=1

Postdoc position in algorithms (closing March 31st 2016)

We are seeking to recruit a postdoctoral research fellow to work in the area of designing algorithms for analysing large data sets.

You will be expected to perform high quality research under the supervision of Professor Graham Cormode, as part of the ERC funded project ‘Small Summaries for Big Data’. This can encompass streaming algorithms, sketching and dimensionality reduction, distributed monitoring and mergeable summaries, verification of outsourced computation, or other related topics. The expectation is that you will produce breakthrough research results in the summarisation of large volumes of data, and publish these results in top rated venues.

You will possess a PhD or an equivalent qualification in Computer Science or a very closely-related discipline (or you will shortly be obtaining it). You should have a strong background in one or more of the following areas: randomized and approximation algorithms; communication complexity and lower bounds; streaming or sublinear algorithms.

The post is based in the Department of Computer Science at University of Warwick, but collaborations with closely related research organisations such as the Centre for Discrete Mathematics and its Applications (DIMAP), the Warwick Institute for the Science of Cities (WISC); and the newly formed Alan Turing Institute (ATI) will be strongly encouraged. You will join a team of researchers led by Professor Cormode including other postdoctoral researchers and PhD students.

Candidates should provide with their application form a CV, a list of publications and a research statement.

Closing date: 31st March 2016

More information:http://www.jobs.ac.uk/job/AUC577/research-fellow-77780-026/

PhD positions in Data Summarization available

A funded studentship is available in the area of computer science to work on algorithms and data structures for summarization of massive data sets. Funding is provided through the prestigious ERC program, under project 647557, “Small Summaries for Big Data”.

Project Overview:
A fundamental challenge in processing the massive quantities of information generated by modern applications is in extracting suitable representations of the data that can be stored, manipulated and interrogated on a single machine. A promising approach is in the design and analysis of compact summaries: data structures which capture key features of the data, and which can be created effectively over distributed data sets. Popular summary structures include the Bloom filter, which compactly represents a set of items, and sketches which allow vector norms and products to be estimated.
Such structures are very attractive, since they can be computed in parallel and combined to yield a single, compact summary of the data. Yet the full potential of summaries is far from being fully realized. Professor Cormode is recruiting a team to work on important problems around creating Small Summaries for Big Data. The goal is to substantially advance the state of the art in data summarization, to the point where accurate and effective summaries are available for a wide array of problems, and can be used seamlessly in applications that process big data. PhD studentships can work on a variety of topics related to the project, including:
• The design and evaluation of new summaries for fundamental computations such as large matrix computations
• Summary techniques for complex structures such as massive graphs
• Summaries that allow the verification of outsourced computation over big data.
• Application of summaries in the context of monitoring distributed, evolving streams of data
The expectation is that this will lead to novel results in the summarization of large volumes of data, which will be published in top-rated venues.
You will possess a degree in Computer Science, mathematics or very closely related discipline (or you will shortly be obtaining it). You should have good knowledge of one or more of the following areas: algorithm design and analysis; randomized and approximation algorithms; communication complexity and lower bounds; streaming or sublinear algorithms. The post is based in the Department of Computer Science at the University of Warwick, but collaborations with closely related research organizations such as the centre for Discrete Mathematics and its Applications (DIMAP), the Warwick Institute for the Science of Cities (WISC); and the newly formed Alan Turing Institute (ATI) will be strongly encouraged.
For examples of relevant research and related topics, please consult Prof. Cormode’s web pages at http://www2.warwick.ac.uk/fac/sci/dcs/people/Graham_CormodeEligibility:
Candidates should hold a degree in Computer Science, Mathematics or closely related discipline, or expect to complete one before the commencement of the studentship. The degree should show a high level of achievement (1st or 2.1 level).
Funding level:
Funding is available to support stipend and fees at the UK/EU level for 4 years (this does not cover fees for non-EU students, see http://www2.warwick.ac.uk/study/postgraduate/funding/fees/ for more information).
Application details:
Please send a CV to giving details of your education and achievements to date, including details of performance in relevant university-level subjects (such as Algorithms, Data Structures, Complexity, Mathematical analysis of algorithms, linear algebra and so on). Please also include a covering note explaining how your background and interests make you relevant to the aims of the project.
Applications will be reviewed as they are received, with an initial deadline of November 30th 2015, and a final deadline of 31st March 2016.This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 647557).

Funding Notes

Funding is available to support stipend and fees at the UK/EU level for 4 years (this does not cover fees for non-EU students, see View Website for more information).