Algorithms and Lower Bounds for Problems in the Data Streaming Model

本项目通过解决数据流模型中的相应图问题，研究回答和证明大规模数据集规模不断增加的问题的不可能性结果的新技术。它福尔斯EPSRC的信息和通信技术主题，更确切地说，属于他们的理论计算机科学研究领域。数据处于人类发展的最前沿，主要应用于广告，金融和人工智能等领域。在许多这样的情况下，数据可以以数学图的形式解释，对数据的问题可以表示为经过充分研究的图问题;例如，双方之间的金融交易可以建模为两个节点之间的加权边，而寻找最活跃的一方等问题可以解释为寻找图中度最大的节点。这些问题（即最大匹配或最小顶点覆盖）对于小的静态图是最优和有效的，但在现实情况下，这些图是巨大的和动态的。以在线支付系统PayPal为例。每天有数百万笔交易发生，反过来，数百万条新边被添加到图中。解决像这样的大规模图（在空间需求上可证明是线性的）上的问题的最佳算法将需要比超级计算机的RAM上通常可用的内存多得多的内存。这些类型的问题，类似于那些面临的大型社会

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