Systems and Foundations For Massive-Scale Data Management

大规模数据管理的系统和基础

• 批准号: RGPIN-2016-03877
• 负责人: Salihoglu, Semih
• 金额: $ 2.26万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708882
• 关键词: Systems; Foundations; Massive; Scale; Data

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.

随着数据量的增长和新数据生成速度的提高，许多应用程序在高度并行的分布式数据管理系统上处理数据。本文主要从两个方面对分布式数据管理系统进行研究：(1)大规模数据管理系统的理论基础；(2)处理大规模图形数据的系统。