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