Algorithms and Lower Bounds for Problems in the Data Streaming Model

点击翻译按钮获取中文摘要

This project researches novel techniques for answering and proving impossibility results of questions posed to the ever-increasing size of massive datasets by tackling its corresponding graph problem in the data streaming model. It falls within EPSRC's Information and Communication Technologies theme, and more precisely under their Theoretical Computer Science research area.Data is at the forefront of human development with major applications in areas like advertising, finance and artificial intelligence. In many of these contexts, the data can be interpreted in the form of a mathematical graph and questions to the data can be represented as well-researched graph problems; for example, financial transactions between two parties can be modelled as a weighted edge between two nodes, and questions such as finding the most active party can be interpreted as finding the node with largest degree in the graph. These problems (i.e. maximal matching or minimum vertex cover) are optimally and efficiently solvable for small static graphs, but in realistic cases, these graphs are massive and dynamic. Consider the online payment system PayPal. Millions of transactions are made every day, and in turn, millions of new edges are added to the graph. Optimal algorithms for solving problems on a massive graph like this one (which are provably linear in space requirement) would require far more memory than what is typically available on the RAM of a super-computer. These types of problems, similar to those faced in large social