Systems and Foundations For Massive-Scale Data Management

随着数据量的增长和新数据生成速度的提高，许多应用程序在高度并行的分布式数据管理系统上处理数据。这项建议的目标是研究分布式数据管理系统，重点放在两个领域：(1)大规模数据管理系统的理论基础；(2)用于处理大规模图形数据的系统。*在理论基础上，我的重点是理解分布式算法在回答关系数据查询方面的基本限制，并评估它们的“好”程度。分布式算法在并行度、通信和计算成本以及它们所需的计算轮数(即机器同步)方面有所不同。我的目标是得出在数据上执行任务的算法的成本下限或上限。具体地说，我打算研究两个问题：*1.同步的能力：回答一个查询需要多少轮计算？*2.并行的限制：可以用来回答一个查询的最大机器数量是多少？*关于大规模图形处理，我的重点是通用的分布式图形系统。大型图表是许多应用程序的核心，例如网络搜索、社交网络和遗传分析。一般而言，这些应用程序在图上执行以下任务：(1)批处理图算法；(2)机器学习算法；(3)寻找子图；以及(4)实时分析图是否在演化。现有系统支持其中的一到两项任务。我的目标是构建一个支持所有这些任务并基于实时数据流(TD)执行模型的系统。TD是一种固有的流模型，可以支持实时分析，但具有支持同步和异步计算的机制，可以支持批处理图算法、机器学习算法和子图查找。具体来说，我打算研究以下几个问题：*1.通用图形系统的TD算子。*2.高效编译到这些TD算子的查询语言和API。*3.有限集群内存下高效的存储模型。*4.运行在TD上的图形应用程序的测试和调试工具。*这项工作将为大规模数据处理奠定理论基础，并产生一个开源的原型系统，推动大规模图形处理的发展。**

As the volume of data grows, and the speed of new data generation increases, many applications process their data on highly-parallel distributed data management systems. The objective of this proposal is to study distributed data management systems with a focus on two areas: (1) theoretical foundations of massive-scale data management systems; and (2) systems for processing large-scale graph data.***On theoretical foundations, my focus is on understanding the fundamental limitations of distributed algorithms for answering queries over relational data and evaluate how "good" they are. Distributed algorithms differ in their parallelism levels, communication and computation costs, and the number of rounds of computation, i.e., machine synchronizations, they require. My goal is to derive lower or upper bounds on the costs of algorithms that perform a task over data. Specifically, I intend to study two questions:*** 1. Power of synchronization: How many rounds of computation are needed to answer a query?*** 2. Limits of parallelism: What is the maximum number of machines that can be utilized to answer a query?***On large-scale graph processing, my focus is on general-purpose distributed graph systems. Large-scale graphs are at the core of many applications, such as web search, social networks, and genetic analysis. Broadly, these applications perform the following tasks on graphs: (1) batch graph algorithms; (2) machine-learning algorithms; (3) finding subgraphs; and (4) real-time analysis if the graph is evolving. Existing systems support one or two of these tasks. My goal is to build a system that supports all of these tasks and is based on the timely dataflow (TD) execution model. TD is an inherently streaming model, which can support real-time analysis, but has mechanisms to support synchronous and asynchronous computations, which can support batch graph algorithms, machine-learning algorithms and subgraph finding. Specifically, I intend to study the following issues:*** 1. TD operators of a general-purpose graph system.*** 2. Query languages and APIs that efficiently compile to these TD operators.*** 3. Storage models that are efficient under limited cluster memory.*** 4. Tools for testing and debugging graph applications running on TD.***This work will establish theoretical foundations for massive-scale data processing, and produce an open-source prototype system advancing the state of the art in large-scale graph processing.**