Systems and Foundations For Massive-Scale Data Management

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

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.**