University of the West of Scotland Featured PhD Programmes
Imperial College London Featured PhD Programmes
University of Dundee Featured PhD Programmes

Designing Efficient Algorithms for Big Data

   School of Computer Science

This project is no longer listed on and may not be available.

Click here to search for PhD studentship opportunities
  Dr Rajesh Chitnis  No more applications being accepted  Funded PhD Project (UK Students Only)

Birmingham United Kingdom Data Analysis Data Science

About the Project

Designing and implementing efficient algorithms are at the very heart of computer science. Typically, the efficiency of an algorithm is determined by how much resource the algorithm consumes as a function of its input size. The traditional resource which researchers have focused on is the algorithm's running TIME. However, in the last two decades, the advent of Big Data has led to different challenges in the design of efficient algorithms. The datasets arising from network traffic, call records, traffic signals, social networks, etc. are so massive that storing them fully in memory is too costly and or even outright impossible. Hence, the focus in the quest for efficient algorithms has turned to the consumption of memory, or SPACE. Most standard algorithmic techniques fail if one does not have access to (or cannot store) the whole input. The paradigm of streaming algorithms [1] helps us design efficient algorithms for Big Data: the input arrives as a stream of bits/items, and at each timestamp one has to make a (fast) decision whether or not to store the current bit/item in memory. The memory storage of streaming algorithms is typically required to be sublinear in the input size (polylogarithmic is even more desirable).

A PhD position is available in the area of "Designing Efficient Algorithms for Big Data" via the paradigm of streaming algorithms. The first goal of this project is to design novel algorithms for fundamental mathematical problems with theoretical guarantees on the performance, and show (tight) lower bounds whenever possible. The second goal is to then apply these new, efficient algorithms to real-world problems arising in areas such as bioinformatics, clustering, privacy, social networks, databases, etc. A particular focus on the theoretical aspect of the project will be exploring possible connections to methodologies for coping with NP-hard problems such as parameterized algorithms, kernelization, etc. [2,3]. There will also be opportunities to work on other algorithmic paradigms for dealing with Big Data such as distributed algorithms, parallel algorithms, dynamic algorithms, external-memory algorithms etc.

There will also be opportunities to develop collaborations with other academics at Birmingham, the Alan Turing Institute, UK and University of Melbourne, Australia.

Eligibility: First or Upper Second Class Honours undergraduate degree and/or postgraduate degree with Distinction (or an international equivalent). We also consider applicants from diverse backgrounds that has provided them with equally rich relevant experience and knowledge. Full-time and part-time study modes are available.

We seek an ambitious and motivated PhD candidate with excellent problem solving abilities, especially in algorithms and complexity. Prior research experience and good programming skills are also highly desirable. We expect the student to have an undergraduate degree in Mathematics or Computer Science, and familiarity with graph theory & algorithms, theory of computation, discrete mathematics, writing proofs, etc. During the course of this studentship, the successful candidate will develop skills in algorithmic techniques (sketching, sampling, kernelization, etc.) and lower bound methodologies (communication complexity, information complexity, etc). There will also be opportunities to develop skills in writing, presentation and teaching.

If your first language is not English and you have not studied in an English-speaking country, you will have to provide an English language qualification.

We want our PhD student cohorts to reflect our diverse society. UoB is therefore committed to widening the diversity of our PhD student cohorts. UoB studentships are open to all and we particularly welcome applications from under-represented groups, including, but not limited to BAME, disabled and neuro-diverse candidates. We also welcome applications for part-time study.

Funding Notes

The position offered is for three and a half years full-time study. The value of the award is stipend; £15,285 pa; tuition fee: £4,407. Awards are usually incremented on 1 October each year.


[1] Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. In J. Comput. Syst. Sci. 58(1): 137-147 (1999)
[2] Rajesh Chitnis, Graham Cormode: Towards a Theory of Parameterized Streaming Algorithms. In IPEC 2019
[3] Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, Morteza Monemizadeh: Parameterized Streaming: Maximal Matching and Vertex Cover. In SODA 2015
Search Suggestions
Search suggestions

Based on your current searches we recommend the following search filters.