Hashing is used everywhere in computing and is getting increasingly important with the exploding amount of data. A summer school at the University of Copenhagen provided an in-depth introduction to hashing, both theory and applications. The topics ranged from modern theory of hashing, to actual implementations of hash functions that are both efficient and provide the necessary probabilistic guarantees. Application areas studied, included sketching and data bases, similarity estimation, and machine learning.

Slides from the summer school are available now, and videos will be uploaded soon.

The paper "Privbayes: Private data release via bayesian networks" was presented at the ACM SIGMOD 2014 conference in Utah in June 2014. The paper is a collaboration between Graham Cormode (University of Warwick), Magda Procopiuc, Divesh Srivastava (AT&T Labs Research), Xiaokui Xiao, and Jun Zhang (NTU Singapore). It shows how the private data can be released under the model of differential privacy while preserving much of the original structure of the original data, by using the model of Bayesian networks. These identify the important correlations between attributes in the data, while avoiding the "curse of dimensionality".

Prof Cormode is one of 25 researchers worldwide selected for a Yahoo! Faculty Research and Engagement Program (FREP) award. This award will support Prof Cormode's collaboration with Yahoo researchers into smart algorithms and data structures to allow large scale search and query suggestion over massive data sets.

The paper “An improved data stream summary: The count-min sketch and its applications,” authored by Graham Cormode and S. Muthukrishnan, published in LATIN 2004, has been awarded the 2014 Imre Simon Test-of-Time Award.

The Imre Simon Award was created in 2012, with the aim of recognizing the papers published in LATIN which have had the most relevant and lasting impact. Since then, each edition of the conference awards a paper published in LATIN that is at least 10 years old, in order to assess its long-term impact in the area of Theoretical Computer Science. See http://www.latintcs.org/prize for more information.

For more information on the Count-Min sketch and its applications, see the Count-Min website.

A Microsoft Research scholarship place is available to study the topic of "Sketching Algorithms for Massive Graphs and Matrices" at the University of Warwick, under the guidance of Professor Graham Cormode and Dr. Milan Vojnovic of Microsoft Research. [Update July 2014: This place has been provisionally filled and we are no longer accepting applications].

The Microsoft PhD Scholarship Programme recognises and supports exceptional students who show the potential to make an outstanding contribution to science and computing. Each Microsoft scholarship consists of an annual bursary for up to a maximum of three years. In addition, every Scholar receives a laptop with a selection of software applications.

During the course of their PhD, Scholars are invited to Microsoft Research in Cambridge for an annual Summer School that includes a series of talks of academic interest and posters sessions, which provides the Scholars the opportunity to present their work to Microsoft researchers and a number of Cambridge academics. Some of the Scholars may also be offered, at the discretion of Microsoft Research, an internship in one of the Microsoft Research laboratories. Internships involve working on a project alongside and as part of a team of Microsoft researchers. Scholars are paid during their internship, in addition to their scholarship bursary.

Applicants require a first-class Honours degree or equivalent in Computer Science, Mathematics or Computer Engineering, experience in programming and aptitude for mathematical subjects. A Masters degree is desirable. Before the Scholarship can be awarded the candidate must also undergo the formal admission procedure to the university, and approval from Microsoft Research.

To apply, please contact Graham Cormode or Milan Vojnovic directly. There is no final deadline, but applications received before the end of May 2014 will have the greatest chance of success. The planned start date would be October 2014, but January 2015 would also be possible.

Project Summary

Increasingly, we are faced with larger and larger volumes of data from which to extract insights and intelligence. An important case surrounds data that can be represented as a graph or (adjacency) matrix. A promising approach is to look for ways to “sketch” such structures: to build a representation that is much more compact than the input, but which allows some function of interest on the original data to be approximated accurately using the sketch. Such sketches are well-known and widely used for data that can be represented as a vector (such as to identify the most frequent elements, or to count the number of distinct items). The goal of this scholarship project is to develop new algorithms for sketching of massive graphs and matrices, and to demonstrate their usefulness via theoretical analysis and empirical evaluation.

Further details and suggested reading is available from Prof. Graham Cormode